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 |
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 |
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 |
> 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 |
On Sun, Apr 6, 2008 at 12:59 PM, Alan G Isaac <[hidden email]> 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. Chuck _______________________________________________ Numpy-discussion mailing list [hidden email] http://projects.scipy.org/mailman/listinfo/numpy-discussion |
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 |
On Sun, Apr 6, 2008 at 2:34 PM, Alan G Isaac <[hidden email]> wrote:
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 |
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 |
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 |
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 |
On Sun, Apr 6, 2008 at 8:51 PM, Alan G Isaac <[hidden email]> wrote:
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 |
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 |
On Sun, Apr 6, 2008 at 10:38 PM, Alan G Isaac <[hidden email]> wrote:
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 |
Free forum by Nabble | Edit this page |