[seqfan] Inequivalent matrices
M. F. Hasler
oeis at hasler.fr
Wed Apr 27 20:52:56 CEST 2022
Dear sequence fans,
I was looking for the number of inequivalent matrices with entries in Z/mZ
(or {0,...,m-1}, or 1...m), modulo permutations or rows and columns.
I think for m=2 this is given in Ron Hardin's oeis.org/A180985
(although I may have overlooked something, and the definition using
lexicographic monotonicity of rows and columns might not be completely
equivalent to having a canonical representative of a class modulo the
permutations I mentioned...?).
It was easy to write a program that constructs the inequivalent
{0,1}-matrices explicitly to enumerate them, and it should not be too
difficult to find a recursive formula for their number.
But the case m>2 (e g., "ternary" matrices etc.) seems slightly more
complicated.
Did someone already investigate on this?
(The requirement of lexicographic order of rows and columns seems no more
sufficient, since e.g., the 2×2 ternary matrix
02
10 would satisfy this, but it is equivalent to the matrix
01
20. How can the former be "excluded" in a simple manner?
I wrote a program that gives the canonical (lexicographically smallest)
representative of any matrix, and it recognizes the equivalence in the
above case, but I have not yet fixed my enumeration program so that it
wouldn't even "produce" the former candidate.
(It seems one can't just require the min or max of the rows/cols to be
nondecreasing since the matrix [02;11] should be produced as a canonical
representative, not equivalent to [01;21], for instance.) Also, for larger
sizes and/or m, I'm not yet sure where my program would catch all possible
equivalences.
I think some "dynamical programmers" might compute these counts without too
much difficulty, and it would definitely be worth while having these tables
in the OEIS.
Please don't hesitate to contact me if you could be interested in that or
if you found this already in the OEIS or elsewhere in the literature.
Thanks,
- Maximilian
More information about the SeqFan
mailing list