Re: [Numpy-discussion] matrix multiply
On Sun, Apr 6, 2008 at 10:38 PM, Alan G Isaac <[EMAIL PROTECTED]> 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 Numpy-discussion@scipy.org http://projects.scipy.org/mailman/listinfo/numpy-discussion
Re: [Numpy-discussion] matrix multiply
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 Numpy-discussion@scipy.org http://projects.scipy.org/mailman/listinfo/numpy-discussion
Re: [Numpy-discussion] matrix multiply
On Sun, Apr 6, 2008 at 8:51 PM, Alan G Isaac <[EMAIL PROTECTED]> 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 Numpy-discussion@scipy.org http://projects.scipy.org/mailman/listinfo/numpy-discussion
Re: [Numpy-discussion] matrix multiply
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 Numpy-discussion@scipy.org http://projects.scipy.org/mailman/listinfo/numpy-discussion
Re: [Numpy-discussion] matrix multiply
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 Numpy-discussion@scipy.org http://projects.scipy.org/mailman/listinfo/numpy-discussion
Re: [Numpy-discussion] matrix multiply
> > 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 Numpy-discussion@scipy.org http://projects.scipy.org/mailman/listinfo/numpy-discussion
Re: [Numpy-discussion] matrix multiply
On Sun, Apr 6, 2008 at 2:34 PM, Alan G Isaac <[EMAIL PROTECTED]> 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 Numpy-discussion@scipy.org http://projects.scipy.org/mailman/listinfo/numpy-discussion
Re: [Numpy-discussion] matrix multiply
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 Numpy-discussion@scipy.org http://projects.scipy.org/mailman/listinfo/numpy-discussion
Re: [Numpy-discussion] matrix multiply
On Sun, Apr 6, 2008 at 12:59 PM, Alan G Isaac <[EMAIL PROTECTED]> wrote:
> > On 06/04/2008, Alan G Isaac <[EMAIL PROTECTED]> 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
Numpy-discussion@scipy.org
http://projects.scipy.org/mailman/listinfo/numpy-discussion
Re: [Numpy-discussion] matrix multiply
> On 06/04/2008, Alan G Isaac <[EMAIL PROTECTED]> 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
Numpy-discussion@scipy.org
http://projects.scipy.org/mailman/listinfo/numpy-discussion
Re: [Numpy-discussion] matrix multiply
On 06/04/2008, Alan G Isaac <[EMAIL PROTECTED]> 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
Numpy-discussion@scipy.org
http://projects.scipy.org/mailman/listinfo/numpy-discussion
Re: [Numpy-discussion] matrix multiply
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
Numpy-discussion@scipy.org
http://projects.scipy.org/mailman/listinfo/numpy-discussion
