matrix multiply

classic Classic list List threaded Threaded
13 messages Options
Reply | Threaded
Open this post in threaded view
|

matrix multiply

Stéfan van der Walt
Hi all,

Some discussion recently took place around raising a square matrices
to integer powers.  See ticket #601:

http://scipy.org/scipy/numpy/ticket/601

Anne Archibald wrote a patch which factored 'matrix_multiply' out of
defmatrix (the matrix power implemented for the Matrix class).  After
some further discussion on irc, and some careful footwork so that
everything imports correctly, I checked in

http://projects.scipy.org/scipy/numpy/changeset/4968

The matrix_multiply method is exposed as numpy.linalg.matrix_multiply,
and is not in the top-level numpy namespace (it's a bit crowded there
already).  I'd be glad if you would review the changeset and comment.

Thanks,
Stéfan
_______________________________________________
Numpy-discussion mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|

Re: matrix multiply

Alan G Isaac
On Sun, 6 Apr 2008, Stéfan van der Walt apparently wrote:
> I'd be glad if you would review the changeset and comment.

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)

Cheers,
Alan Isaac



_______________________________________________
Numpy-discussion mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|

Re: matrix multiply

Anne Archibald
On 06/04/2008, Alan G Isaac <[hidden email]> 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)

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)? For zero it will give the identity, and for
negative powers some sort of floating-point inverse. Currently for
positive powers it should produce the right answer provided
multiplication is associative (which I think it is).

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


Anne
_______________________________________________
Numpy-discussion mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|

Re: matrix multiply

Alan G Isaac
> On 06/04/2008, Alan G Isaac <[hidden email]> 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



_______________________________________________
Numpy-discussion mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|

Re: matrix multiply

Charles R Harris


On Sun, Apr 6, 2008 at 12:59 PM, Alan G Isaac <[hidden email]> wrote:
> On 06/04/2008, Alan G Isaac <[hidden email]> 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 boolean  algebra is a field and the correct addition is xor, which is the same as addition modulo 2. This makes all matrices with determinant 1 invertible. This isn't the current convention, however, as it was when Caratheodory was writing on measures and rings of sets were actually rings and the symmetric difference was used instead of union.

Chuck


_______________________________________________
Numpy-discussion mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|

Re: matrix multiply

Alan G Isaac
On Sun, 6 Apr 2008, Charles R Harris wrote:
> The boolean  algebra is a field and the correct addition is xor, which is
> the same as addition modulo 2. This makes all matrices with determinant 1
> invertible. This isn't the current convention, however, as it was when
> Caratheodory was writing on measures and rings of sets were actually rings
> and the symmetric difference was used instead of union.

I am not sure what you are suggesting for matrix behavior,
nor what "correct" means here.

Comment:
Standard *boolean algebra* axioms include distributivity, but
1 xor (0 and 0) = 1 xor 0 = 1
(1 xor 0) and (1 xor 0) = 1 and 1 = 1

So I guess (?) what you are saying is something like:
if we have a boolen algebra with operators 'and' and 'or',
we can generate a boolean ring with operations 'xor' and 'and'.
When we do so, the '+' is traditionally used for the 'xor' operation.

But where in the modern literature on boolean matrices is
'+' given this interpretation?

IANAM,*
Alan Isaac

* IANAM = I am not a mathematician.




_______________________________________________
Numpy-discussion mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|

Re: matrix multiply

Charles R Harris


On Sun, Apr 6, 2008 at 2:34 PM, Alan G Isaac <[hidden email]> wrote:
On Sun, 6 Apr 2008, Charles R Harris wrote:
> The boolean  algebra is a field and the correct addition is xor, which is
> the same as addition modulo 2. This makes all matrices with determinant 1
> invertible. This isn't the current convention, however, as it was when
> Caratheodory was writing on measures and rings of sets were actually rings
> and the symmetric difference was used instead of union.

I am not sure what you are suggesting for matrix behavior,
nor what "correct" means here.

Comment:
Standard *boolean algebra* axioms include distributivity, but
1 xor (0 and 0) = 1 xor 0 = 1
(1 xor 0) and (1 xor 0) = 1 and 1 = 1

So I guess (?) what you are saying is something like:
if we have a boolen algebra with operators 'and' and 'or',
we can generate a boolean ring with operations 'xor' and 'and'.
When we do so, the '+' is traditionally used for the 'xor' operation.

But where in the modern literature on boolean matrices is
'+' given this interpretation?

It's generally not. It used to be that \Sigma and + were used for set union, probably because that was what the printers had on hand and what the mathematicians were used to. Then there was the alternate desire to make boolean algebra conform to the standad ring structure which led to using the symmetric difference, \Delta. For instance, if + is 'or', then 1 has no additive inverse, whereas 1 xor 1 = 0. I'm just pointing to some of the history here that I've noticed in old papers. I prefer the modern usage myself as it is closer to the accepted logic operations, but applying algebraic manipulations like powers and matrix inverses in that context leads to strange results.

Chuck


_______________________________________________
Numpy-discussion mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|

Re: matrix multiply

Anne Archibald
In reply to this post by Alan G Isaac
>  > 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
_______________________________________________
Numpy-discussion mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|

Re: matrix multiply

Alan G Isaac
On Sun, 6 Apr 2008, Anne Archibald apparently wrote:
> I am not aware of any algorithm for finding inverses, or
> even determining which matrices are invertible, in the
> peculiar Boolean arithmetic we use.

Again, it is *not* peculiar, it is very standard for
boolean matrices.  And with this behavior, a nonnegative
integer power has an obvious graph theoretic interpretation.

Such boolean matrices are obviously invertible if they
are orthogonal.  It turn out this is a necessary condition
as well. [1]_  Orthogonality is obviously easy to test.

Cheers,
Alan Isaac

.. [1]
   Luce, D., 1952, "A Note on Boolean Matrix Theory",
   Proceeding of the Am. Math. Soc 3(3), p.382-8.



_______________________________________________
Numpy-discussion mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|

Re: matrix multiply

Alan G Isaac
In reply to this post by Charles R Harris
On Sun, 6 Apr 2008, Charles R Harris apparently wrote:
> I prefer the modern usage myself as it is closer to the
> accepted logic operations, but applying algebraic
> manipulations like powers and matrix inverses in that
> context leads to strange results.

I have not really thought much about inverses,
but nonnegative integer powers have a natural
interpretation in graph theory (with the boolean
algebra operations, not the boolean ring operations).
This is exactly what I was requesting be preserved.

Cheers,
Alan Isaac



_______________________________________________
Numpy-discussion mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|

Re: matrix multiply

Charles R Harris


On Sun, Apr 6, 2008 at 8:51 PM, Alan G Isaac <[hidden email]> wrote:
On Sun, 6 Apr 2008, Charles R Harris apparently wrote:
> I prefer the modern usage myself as it is closer to the
> accepted logic operations, but applying algebraic
> manipulations like powers and matrix inverses in that
> context leads to strange results.

I have not really thought much about inverses,
but nonnegative integer powers have a natural
interpretation in graph theory (with the boolean
algebra operations, not the boolean ring operations).
This is exactly what I was requesting be preserved.

You mean as edges in a directed graph? I suppose so, although graph algorithms tend to use different structures, lists of lists, trees, and such. I would think plain old integer matrices might actually carry more information; let me count the ways. And positive matrices have their own oddities. Hmm... I wonder what matrices over Z_2 mean in that context?

Chuck


_______________________________________________
Numpy-discussion mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|

Re: matrix multiply

Alan G Isaac
On Sun, 6 Apr 2008, Charles R Harris apparently wrote:
> You mean as edges in a directed graph?

Yes.

Naturally a boolean matrix is not the most compact
representation of a directed graph, especially a
sparse one.  However it can be convenient.

If B is a boolean matrix such that Bij=1 if there is
and edge from i to j, then B**2 has unit entries where
there is a path of length 2 from i to j.  The transitive
closure is similarly easy to represent (as a matrix power).

Cheers,
Alan Isaac



_______________________________________________
Numpy-discussion mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/numpy-discussion
Reply | Threaded
Open this post in threaded view
|

Re: matrix multiply

Charles R Harris


On Sun, Apr 6, 2008 at 10:38 PM, Alan G Isaac <[hidden email]> wrote:
On Sun, 6 Apr 2008, Charles R Harris apparently wrote:
> You mean as edges in a directed graph?

Yes.

Naturally a boolean matrix is not the most compact
representation of a directed graph, especially a
sparse one.  However it can be convenient.

I've had occasional thoughts of adding a "computer science" kit to scipy with equivalence relations, trees, tries, graphs, and other such things that come in handy for some sorts of problems.

Chuck



_______________________________________________
Numpy-discussion mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/numpy-discussion