[seqfan] Re: Inequivalent matrices

Brendan McKay Brendan.McKay at anu.edu.au
Thu Apr 28 04:42:15 CEST 2022


A180985 (rows and columns in lexicographic order) is different
from A002724 (equivalence classes under row and column permutation).

Equivalence classes under row and column permutation for Z/Z3 is A052269.
For Z/Z4 it is A052271, for Z/Z5 it is A052272, and for Z/Z6 it is A246112.

All of these except Z/Z6 have formulas provided by Christian Bower.
A246106 is a 2-D version.

Brendan.

On 28/4/2022 4:52 am, M. F. Hasler wrote:
> 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
>
> --
> Seqfan Mailing list - https://aus01.safelinks.protection.outlook.com/?url=http%3A%2F%2Flist.seqfan.eu%2F&data=05%7C01%7Cbrendan.mckay%40anu.edu.au%7C9913ac15b7eb4ac45b8908da287f2d35%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637867041635810981%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=GkJEkwjMpHCQdJH7A7tic8w2xZlp7CwmcHkyORwucaY%3D&reserved=0



More information about the SeqFan mailing list