[Numpy-discussion] matrix multiply

Alan G Isaac aisaac@american....
Sun Apr 6 13:59:54 CDT 2008


> On 06/04/2008, Alan G Isaac <aisaac@american.edu> wrote: 
>> Just checking:
>>  it's important to me that this won't change
>>  the behavior of boolean matrices, but I don't
>>  see a test for this.  E.g., ::

>>     >>> import numpy as N
>>     >>> A = N.mat('1 0;1 1',dtype='bool')
>>     >>> A**2
>>     matrix([[ True, False],
>>             [ True,  True]], dtype=bool)

On Sun, 6 Apr 2008, Anne Archibald apparently wrote:
> I have no desire to change the behaviour of boolean matrices, and I'll 
> write a test, but what is it supposed to do with them? Just produce 
> reduce(dot,[A]*n)?

That's the part I care about.

> For zero it will give the identity,

Yes.

> and for negative powers some sort of floating-point 
> inverse.

That deserves discussion.
Not all "invertible" boolean matrices have an inverse in the algebra.
Just the orthogonal ones do.

I guess I would special case inverses for Boolean matrices.
Just test if the matrix B is orthogonal (under Boolean 
multiplication) and if so return B's transpose.

> Currently for positive powers it should produce the right 
> answer provided multiplication is associative (which 
> I think it is).

Yes; N×N boolean matrices are I believe a semi-group under multiplication.

> The inverse actually poses a problem: should it return 
> (A**(-1))**n or (A**n)**(-1)? (No, they're not the same 
> for boolean matrices.)

I think it must be the latter ... ?

By associativity, if B has an inverse A,
then B**n must have inverse A**n.
So you are observing that with boolean matrices
we might find B**n is invertible even though B is not.
Right?  So the latter will work in more cases.
So again: form B**n, test for orthogonality,
and return the transpose if the test passes.

Cheers,
Alan Isaac





More information about the Numpy-discussion mailing list