From all square matrices with entries $1,...,n^2$, I am only interested in ones which have different rows or columns.
Since for $n=3$ we already have $9!=362880$ matrices I do not want to sieve through them all and compare the rows and colums for even higher $n$. I wanted to develop an algorithm that would fill blank spaces in the matrix such that it would generate only representatives of different classes.
As an example \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} \begin{pmatrix} 1 & 3 \\ 2 & 4 \end{pmatrix}
both have the rows and colums $\{\{1,2\},\{1,3\},\{3,4\},\{2,4\}\}$, so they would be equivalent.
Matrices with same rows and colums can be generated by
- rotating ($4$ results)
- flipping by the main diagonals ($2$ results)
- swapping non-overlapping pairs of rows or pairs of colums
We can maximally swap $\lfloor(n/2)\rfloor$ pairs at one time. We have ${n \choose 2}$ $1$-pair swaps. After picking the first pair, we can pick another pair from the remaining $n-2$ entries, we get ${n \choose 2}{n-2 \choose 2}$ 2-pair swaps. Iterating, we get ${n \choose 2}{n-2 \choose 2}...{n-2(k-1) \choose 2}$ $k$-pair swaps and overall we have the number of swaps
$$S(n)=\sum_{k=0}^{\lfloor(n/2)\rfloor-1}\prod_{j=0}^k{n-2j \choose 2}$$
A total of $6+2S(n)$ members per class.
For $n=2$ it is quite easy to generate the representatives by hand. We have $4!=24$ matrices, so we expect $3$ classes.
We set $1$ into the upper left corner. From the other three numbers we pick two for the antidiagonal, we have ${3 \choose 2} =3$ possibilities, which are $\{2,3\},\{2,4\},\{3,4\}$, the number which is left lands in the bottom right corner.
Overall we get the representatives
\begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}
\begin{pmatrix} 1 & 2 \\ 4 & 3 \end{pmatrix} \begin{pmatrix} 1 & 3 \\ 4 & 2 \end{pmatrix}
For $n=3$ first I thought about reusing the solution for $n=2$, but this did not make it simpler.
Then I thought about picking the main diagonal first, then the second diagonal, and then the third, like this:
\begin{pmatrix} 1 & 2 &3 \\ 2 & 1 &2 \\ 3 & 2 & 1 \end{pmatrix}
Where the numbers are the pick order.
But in $3 \times 3$ matrices this fails as we can also swap the middle row/colum with outer ones and I do not see how to adress this.
I expect each class to have $12$ elements. However then I would get $9!/12=30240$ classes, and I expect the algorithm to be a little complicated. But then I cannot verify reliably that my algorithm is correct due to sheer number of classes.