| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
Two MxN boolean matrices� are equivalent iff one can be transformed
into the other by permuting the rows and/or permuting the columns.
How many distinct MxN boolean matrices are there? Answers for small
values of M or N are welcome.
- Gilbert
P.S. I've run into this problem a few times and have never made
much headway on it.
�Boolean matrices have elements from {0,1}.
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 1587.1 | a possible reference to look at | 3D::ROTH | Geometry is the real life! | Fri Mar 27 1992 18:51 | 20 |
I wrote a simple program to enumerate such classes while playing with the light bulb game a while ago. What I did was for each conjugacy class of permutation for each row and column, generate a permutation of the M*N elements of the matrix, and then chase thru to find the cycles and use the Burnside-Frobenius lemma on orbits of a group acting on a set. Pretty childish I know, but it gave answers fairly quickly... See also M. Harrison, _On the Number of Classes of Binary Matrices_, IEEE Trans on Computers C-22 No 12, December 1973 pp 1048-1052, where in addition column complementations are allowed. What I'd really like to see, is how to handle transpositions of square matrices as well, and also to handle complementations of both rows and columns. That seems much harder. I think there are some results on counting bipartate graphs that would also apply. Anyone know if that's true? - Jim | |||||
| 1587.2 | d�j� not� | DESIR::BUCHANAN | Wed Apr 01 1992 07:50 | 3 | |
see also 1010.*
Andrew.
| |||||
| 1587.3 | I *thought* that problem sounded vaguely familiar | GAUSS::ROTH | Geometry is the real life! | Wed Apr 01 1992 23:33 | 6 |
Thanks for the pointer...
fwiw, I spot checked a few of the counts in 1010 and they agree
with my counting program.
- Jim
| |||||