Conference rusure::math

> (1)  Find an efficient way to determine whether two matrices are equivalent.

    Well, I feel that efficient 'practical' solutions are qualitativly
    different for the boolean vs. general cases.  I will therefore describe
    a general solution that is 'theoreticaly' efficient for all cases,
    but is practice will only be useful and efficient for the boolean
    cases.
    
    Note, however, that a slight modification of this solution can serve
    as a very useful and efficient first pass for a practical general
    solution.
    
Given:  matrices A, and B, of order (m x n), consisting of elements 
    from the set E.
    
Determine:  some operation 'S' called the 'sum' on (e1,e2,...ek) where
    (ex is an element of E), such that S returns a positive integer
    that is the same regardless of the order of e's, but is unique for 
    any combination of e's.  Further S must be efficient to calculate.
    (ie. O( k*Log(k) ) or less)
    
    When E = {0,1} (ie. the boolean set), define the S to be the arithmetic
    sum of all the e's.  Thus (1,0,0) = 1, (0,1,0,0)=1, (0,0,1,1,1)=3,
    etc.  Note that S takes O( k ) to calculate in this case.
    
    ( This is the principle departure of theory with practice.  In theory
    an efficient S always exists.  In practice, an S that returns integers
    greater than an architecturaly determined size (2^32 for a VAX)
    will rapidly detiriorate in efficiency.  (I welcome opposing views
    and insights on this.)  The boolean case provides a special situation
    where the theoretical maps well to the practical.)
    
Procedure:
    
    1. Calculate S for all rows and columns in both A and B, giving
    the lists of integers SrA (row sums of A), ScA(column sums of A), 
    SrB, and ScB.
    
    2. Sort SrA, ScA, SrB, and ScB.

    3. Compare (SrA to SrB) and (ScA to ScB), If both are equal,
    	then ( A = B ).
    
Efficiency:
    
    For the boolean case, Time 	= O( 4*(m*n) + 2*(m+n) + m+n )
    			      	= O( m*n )
    
    For the general case, Time	= O( 2*(m*n*Log(m*n)) + 2*(nLog(n)+mLog(m)
    						      + m+n )
    				= O( m*n * Log(m*n) )
    
    --  Barry

re .1:
    So far so good.

>Determine:  some operation 'S' called the 'sum' on (e1,e2,...ek) where
>    (ex is an element of E), such that S returns a positive integer
>    that is the same regardless of the order of e's, but is unique for 
>    any combination of e's.  Further S must be efficient to calculate.
>    (ie. O( k*Log(k) ) or less)

    Instead of a sum, or sum of squares, ..., you can let 'S' be the
    elements in sorted order, and straight-forwardly compare these sorted
    elements, element by element.  In some sense, this 'S' is optimal.

>Procedure:

    The procedure doesn't distinguish between:

	7 3 1		3 7 1
	1 3 7		3 1 7
	1 7 3    and	1 3 7
	3 1 7		7 1 3
	7 1 3		7 3 1
	3 7 1		1 7 3

> (2)  Find an efficient way to 'visit' all non-equivalent boolean matrices.

    Note that the approach of 1010.1 is to produce a 'canonical' form for
    the matrices.  For visiting all non-equivalent matrices, it'd be useful
    if "A(m,n) is in canonical form" implies "A(m-1,n) is in canonical form"
    (or nearly so).

>> (1)  Find an efficient way to determine whether two matrices are equivalent.
>
>    When E = {0,1} (ie. the boolean set), define the S to be the arithmetic
>    sum of all the e's.  Thus (1,0,0) = 1, (0,1,0,0)=1, (0,0,1,1,1)=3,
>    etc.  Note that S takes O( k ) to calculate in this case.
>    
>Procedure:
>    1. Calculate S for all rows and columns in both A and B, giving
>    the lists of integers SrA (row sums of A), ScA(column sums of A), 
>    SrB, and ScB.
>    2. Sort SrA, ScA, SrB, and ScB.
>    3. Compare (SrA to SrB) and (ScA to ScB), If both are equal,
>    	then ( A = B ).
    
	Eh?

	Try:
		( 1 0 1 )		( 1 0 1 )
	A  =  	( 0 1 0 )	B =	( 0 0 1 )
		( 1 0 1 )		( 1 1 0 )

	SrA = SrB = [ 2, 1, 2 ] = ScA = ScB.

	But A and B are not the same (B has no submatrix ( 1 1 ) for
	example).					 ( 1 1 )

> 3. For any m and n, how many of these chaps are there?

	(Well, that was something like Peter's phraseology.)

	Counting questions are notoriously elusive when it comes to finding a
closed form for the number of objects modulo various symmetries.   Generally,
asymptotic solutions are the most useful anyway.

	But if accuracy is what you want, then the place to start is
Burnside's Lemma, which says in its simplest form:

	N = (1/|G|).sum(� in G)|F(�)|

where:

	X and Y are finite sets.   Here, X = {1..m} x {1..n}, Y = { 0, 1 } 

	N is what were looking for, the number of orbits of Y^X under...

	... G,  the permutation group of X, which induces a permutation group
	on Y^X.   Here G = Sm x Sn.

	F(�) = {x in X | �(x) = x}.


	My first pass at applying this theorem is:

	N = (1/(m!n!)) . sum(i=1..m)sum(j=1..n)(T(m,i).T(n,j).2^(i.j))

	where T(p,k) = the number of permutations of a set of size p, such
	that there are exactly k non-empty cycles.

	Thus suppose m = n = 5.

	T(5,1) = 24
	T(5,2) = 50
	T(5,3) = 35
	T(5,4) = 10
	T(5,5) =  1

	From which I suppose one could compute N.   See how fiddly it's
	getting already.

	Random graph theory is the sort of technology which is going to give
	you the appropximate answer that you yearn for.   I would guess that
	the sort of answer you're going to get is that as m,n -> infinity,
	almost all matrices have no symmetries, so that:

		N -> 2^(nm)/n!m!

	Suppose that n = m, then if we recall Stirling's formula.

	n! ~= (n/e)^n . sqrt(2.pi.n)   when n is large.

	So N ->  e^d, where d = (ln2).n^2 - 2n.ln(n) + 2n + ln(2.pi.n)

	(Remember that this is a guess though!)

Good hunting,
Andrew.

     re .2
     
>>    The procedure doesn't distinguish between:
>>
>>	7 3 1		3 7 1
>>	1 3 7		3 1 7
>>	1 7 3    and	1 3 7
>>	3 1 7		7 1 3
>>	7 1 3		7 3 1
>>	3 7 1		1 7 3
     
     The example of (e1,e2,...,ek) --> e1 + e2 + ... + ek was for
     Boolean matrices, not arbitrary integer matrices.
     
     Dan

    Re .2,.3:
    
    	Oops.	:-(
    
    Re.5:
    
    	Peter is refering (I assume) to the fact that my algorthim sees
    all rows as <7,3,1> and all columns as <7,7,3,3,1,1>.
    
    Hmmm.... I still think theres something here.

    Re .2:
    
>    The procedure doesn't distinguish between:
>
>	7 3 1		3 7 1
>	1 3 7		3 1 7
>	1 7 3    and	1 3 7
>	3 1 7		7 1 3
>	7 1 3		7 3 1
>	3 7 1		1 7 3

    I thought that there was something wrong with your counter-example,
    Peter, so I took a closer look at it.  The procedure does not
    distinguish between them because they are equivilent.
    
    Ie:
    
    	Sort the rows and both give:
    
    		7 3 1
    		7 1 3
    		3 7 1
    		3 1 7
    		1 7 3
    		1 3 7
    
    In fact, it is a tenet of my theory that all matrices whose Row
    Sums all equal the same integer X and whose Column Sums all equal
    the same integer Y, are all equivilent to each other.
    
    Thus for say, all 7x13 matrices, all the matrices whose Row sums
    are all 123 (for some suitably defined sum) and whose Column sums
    are all 225, are then equivilent.

Yes, sorry about that.  I misread the algorithm, thinking that it
*permuted* the matrices into a canonical form, whereas it actually
computes a *characterization* of the matrices.

>    In fact, it is a tenet of my theory that all matrices whose Row
>    Sums all equal the same integer X and whose Column Sums all equal
>    the same integer Y, are all equivilent to each other.

	How about

	1 1 0 0		1 1 0 0
	1 1 0 0		0 1 1 0
	0 0 1 1		0 0 1 1
	0 0 1 1 	1 0 0 1

Andrew

Let G(n) be the number of non-equivalent nxn boolean matrices that have
exactly two 1s in each row and each column.  Then

	G(n) = G(n,1)

		     [m/2]
	G(n,s) = 1 +  Sum  G(i) * G(m-i,i-1)
	             i=n+1

G(n,s) is roughly the number of nxn solutions that don't contain an sxs
(or smaller) solution matrix within them.  G(n,1) seems to grow like 2^(n/2).

The derivation of this recurrence is a very pleasing exercise, because of
the patterns involved.

Let G3(n) be the number of non-equivalent nxn boolean matrices that have
exactly three 1s in each row and each column.  Then

	G3(3) = 1
	G3(4) = 1
	G3(5) = 2
	G3(6) = 7, viz:

	111000	111000	111000	111000	111000	111000	111000
	111000	111000	111000	110100	110100	110100	110100
	111000	110100	100110	110010	101010	101010	100011
	000111	001011	010101	001101	010101	010011	010011
	000111	000111	001011	001011	001011	001101	001110
	000111	000111	000111	000111	000111	000111	001101

.2>	My first pass at applying this theorem is:
.2>	N = (1/(m!n!)) . sum(i=1..m)sum(j=1..n)(T(m,i).T(n,j).2^(i.j))

	For m=n=5, this yields 36, which is far too low.  I suspect the sum
	-- the sum in the theory is over the m!n! elements of G, while the
	above sum is over m.n elements.

Re: .12:	Gasp, but I've bollocks'd it up, as Shakespeare would say.
And that's the second time, as I smart still from Topher Cooper's statistical
rebuff.

	Let me try to repair the discredited .4, which is still basically on
the right track...


>	But if accuracy is what you want, then the place to start is
> Burnside's Lemma, which says in its simplest form:
>
>	N = (1/|G|).sum(� in G)|F(�)|
>
>where:
>
>	X and Y are finite sets.   Here, X = {1..m} x {1..n}, Y = { 0, 1 } 
>
>	N is what were looking for, the number of orbits of Y^X under...
>
>	... G,  the permutation group of X, which induces a permutation group
>	on Y^X.   Here G = Sm x Sn.

OK so far, but...

>	F(�) = {x in X | �(x) = x}.

Wrong!	F(�) = {z in Y^X | �(z) = z}.

	Let's play with a simple example to show the distinction between these
two fellows, and to get our confidence back...

	I have a necklace with 5 beads on it, each bead can be a pearl or a
gallstone.   How many different necklaces are there, if rotation is permited,
but not turning the necklace over.

	My necklaces are PPPPP, PPPPG, PPPGG, PPGPG, GGGGG, GGGGP, GGGPP, GGPGP
that's eight.

	G is C5.   If � is I, then there are 2^5 = 32 necklaces which are
invariant under it.   Otherwise, for the four els of C5 which aren't 0, the
only fixed necklaces are PPPPP and GGGGG, ie. 2.

	So N = (1/5).(32 + 4.2) = 8.


>	My first pass at applying this theorem is:

	entirely bogus, since I built the wrong formula.

>	N = (1/(m!n!)) . sum(i=1..m)sum(j=1..n)(T(m,i).T(n,j).2^(i.j))

	drivel

	It's more fiddly than this.   We examine the interaction of
each cycle of Sm and each cycle of Sn, which together make up � in G.
If the two cycles have order a and b, then the number of different colorations
(of the ab elements) fixed under � is 2^(lcd(a,b)) [lowest common denominator].

	Now the cycles types of S5, with frequency, is the vector, v =

	1^5		 1
	1^3,2		10
	1^2,3		20
	1,2^2		15
	1,4		30
	2,3		20
	5		24

	sum(lcd(a,b)) for each with each is the matrix, M,

	( 25	20	15	15	10	10	 5 )
	( 20	17	12	14	 9	 9	 4 )
	( 15	12	11	 9	 6	 7	 3 )
	( 15	14	 9	13	 8	 8	 3 )
	( 10	 9	 6	 8	 7	 5	 2 )
	( 10	 9	 7 	 8	 5	 7	 2 )
	(  5	 4	 3	 3	 2	 2	 5 )
			

	I currently allege that v'.(2^M).v , divided by 120^2, is the answer.

	I'll check it some time.

Andrew.

    Well work and getting cut off from the Enet has kept me out for
    a week now (sorry), but...

    Re .9:
    
    Right, my 'tenet' is not true, but its (approximate) converse IS
    true for boolean matrices:
    
    	THEOREM:  Any boolean matrix whose row sums are all distinct
    	and whose column sums are all distinct is equivilent to any other
    	boolean matrice with the same set of row sums and column sums.
    
    I have proven this one, but I will leave for an exercise (unless
    you don't think its true ;-)
    
    I feel that this theorem can serve as a strong starting point towards
    developing an efficient comparision algorithim for boolean matrices.

    There is a similar, though much much weaker theorem for the general
    case.  
    
    --  Barry

re .14:
	For 3x3 matrices, we have:

	3		2
	2,1		3
	1,1,1		1

	(2+3+1 = 3!, as it should)

	sum(gcd(a,b)) for each is:

		(3)	(2,1)	(1,1,1)
	(3)	3	2	3
	(2,1)	2	5	6
	(1,1,1)	3	6	9

	We allege the answer is the sum of the following, divided by (3!)^2

		2.2.2^3	3.2.2^2	1.2.2^3
		2.3.2^2	3.3.2^5	1.3.2^6
		2.1.2^3	3.1.2^6	1.1.2^9

	So this is: 81.2^4 / (3!)^2 = 36, which is easily validated by hand.


	The above frequency table may seem a bit 'fiddly', but it's not too
	hard to create a formula for it.  As in .14, let the cycle type (over
	n values) be written as:

		  n_c1    n_c2          n_ci
		c1    , c2    , ... , ci    , ...
		
	Where the c's are distinct, the n_ci are >= 0, and (of course)
	sum(n_ci * ci) = n.  That is, there are n_ci cycles of length ci.

	Then the frequency is:

			n!
		---------------------
		  --           n_ci
		  || (n_ci)! ci
		  --

This table shows the number of distinct MxN boolean matrices for small M,N:

      1   2    3      4         5          6         7          8         9
   +------------------------------------------------------------------------
 1 :  2   3    4      5         6          7         8          9        10
 2 :  3   7   13     22        34         50        70         95       125
 3 :  4  13   36     87       190        386       734       1324      2284
 4 :  5  22   87    317      1053       3250      9343      25207     64167
 5 :  6  34  190   1053      5624      28576    136758     613894   2583164
 6 :  7  50  386   3250     28576     251610   2141733   17256831 130237768
 7 :  8  70  734   9343    136758     141733  33642660  508147108
 8 :  9  95 1324  25207    613894   17256831 508147108 1800728800
 9 : 10 125 2284  64167   2583164  130237768
10 : 11 161 3790 155004  10208743  917558397
11 : 12 203 6080 357009  38013716 1743775184
12 : 13 252 9473 787586 133872584

    				  2
    			     3         3
    		        4         7         4
    		   5        13        13         5
    	       6       22        36        22        6
    	   7      34        87        87        34       7
       8      50      190       317       190       50       8
   9      70     386      1053      1053       386      70       9
   
   Anybody see anything?