

Hi all,
Some discussion recently took place around raising a square matrices
to integer powers. See ticket #601:
http://scipy.org/scipy/numpy/ticket/601Anne 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/4968The matrix_multiply method is exposed as numpy.linalg.matrix_multiply,
and is not in the toplevel numpy namespace (it's a bit crowded there
already). I'd be glad if you would review the changeset and comment.
Thanks,
Stéfan
_______________________________________________
Numpydiscussion mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/numpydiscussion


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
_______________________________________________
Numpydiscussion mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/numpydiscussion


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 floatingpoint 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
_______________________________________________
Numpydiscussion mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/numpydiscussion


> 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 floatingpoint
> 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 semigroup 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
_______________________________________________
Numpydiscussion mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/numpydiscussion


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 floatingpoint
> 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 semigroup 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
_______________________________________________
Numpydiscussion mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/numpydiscussion


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.
_______________________________________________
Numpydiscussion mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/numpydiscussion


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
_______________________________________________
Numpydiscussion mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/numpydiscussion


> > and for negative powers some sort of floatingpoint
> > 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 floatingpoint 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 floatingpoint. 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
_______________________________________________
Numpydiscussion mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/numpydiscussion


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.3828.
_______________________________________________
Numpydiscussion mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/numpydiscussion


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
_______________________________________________
Numpydiscussion mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/numpydiscussion


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
_______________________________________________
Numpydiscussion mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/numpydiscussion


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
_______________________________________________
Numpydiscussion mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/numpydiscussion


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
_______________________________________________
Numpydiscussion mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/numpydiscussion

