[Numpy-discussion] matrix multiply

Anne Archibald peridot.faceted@gmail....
Sun Apr 6 20:35:01 CDT 2008


>  > 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.

This is actually a limitation of the whole linear algebra subsystem:
we only support floating-point linear algebra (apart from dot()).
There are algorithms for doing integer linear algebra, which might be
interesting to implement. But that's a big job. Boolean matrices as
you use them are another step again: because they are not a group
under "+", almost all of linear algebra has to be reinterpreted. For
example it's not obvious that matrix multiplication is associative; it
turns out to be, because you can replace the matrices by integer
matrices containing ones for True and zeros for False, then do the
math, then interpret any nonzero integer as True, and zero as False.

As an aside, if you use "+" to mean xor (which I am not suggesting!)
all of linear algebra continues more or less unchanged; you're just
working over the field of integers modulo 2. If you want eigenvalues
you can pass to an algebraic closure.

>  > 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.

Well, as it stands, since we have no integer linear algebra, inverses
are always floating-point. When you do that, you find that, for
example,
([[True,False],[True,True]]**(-1))**2 = [[1.,0.],[-2.,1.]]
but
([[True,False],[True,True]]**2)**(-1) = [[1.,0.],[-1.,1.]]

I am not aware of any algorithm for finding inverses, or even
determining which matrices are invertible, in the peculiar Boolean
arithmetic we use.

Anne


More information about the Numpy-discussion mailing list