3
$\begingroup$

Suppose we have $n\times n$ matrix that contains numbers from $1$ to $n^2$. How many matrices are there that their $n$ columns, $n$ rows and $2n$ diagonals contain given numbers?

For example $3\times 3$ matrix: \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ \end{pmatrix} Its rows are $(1,2,3),(4,5,6),(7,8,9)$.

Its columns are $(1,4,7),(2,5,8),(3,6,9)$.

Its diagonals are $(1,5,9),(2,6,7),(3,4,8),(1,6,8),(2,4,9),(3,5,7)$.

If we join them all together sorted inside and sorted overall we get:

$$\big((1,2,3),(1,4,7),(1,5,9),(1,6,8),(2,4,9),(2,5,8),(2,6,7),$$$$(3,4,8),(3,5,7),(3,6,9),(4,5,6),(7,8,9)\big)$$

Question is how many $3\times 3$ matrices there are with the same sorted set?

I brute-forced it for $n=3$. And the number is $432$. But I am not able to figure out a formula for it. The number $432$ is divisible by $9$ which is of course because the original matrix can be shifted to $3\cdot 3=9$ different positions preserving the ordered set. And also by $16$ as we can rotate whole matrix $4$ times by $90$ degrees and there are $4$ mirror images for each one. $432/9/16=3$ so there must be $3$ fundamental matrices from which we can generate all $432$ by shifting, rotating and mirroring. (If I am not mistaken.)

Just one example out of $432$ that has the same sorted set as original matrix:

\begin{pmatrix} 4 & 2 & 9 \\ 1 & 8 & 6 \\ 7 & 5 & 3 \\ \end{pmatrix}

...and perhaps additional question: How to produce all the required matrices algorithmically one by one?

$\endgroup$
6
  • $\begingroup$ You can permute the columns in $n!$ ways, then permute the rows in $n!$ ways, and flip it on the main diagonal in $2$ ways. This gives$ 2(n!)^2=72$ We are still missing a factor $6$, which will probably be $n!$, but I don't see where it comes from. $\endgroup$ Feb 19, 2019 at 0:38
  • 1
    $\begingroup$ can you explain the factor of 16? i understand the 4 rotations, but what do you mean "there are 4 mirror images for each [rotation]"? if you take a matrix and reflect it left-to-right and then upside-down, you actually get the 180-degree rotated version, i think... $\endgroup$
    – antkam
    Feb 19, 2019 at 8:18
  • 1
    $\begingroup$ Aren't you looking for matrices with the same unordered set of rows, columns and diagonals? Given the three rows, the three columns, and the six diagonals, there are only $18$ matrices having these as their rows, columns and diagonals, respectively (if any at all, of course). $\endgroup$ Feb 19, 2019 at 8:57
  • 1
    $\begingroup$ Not voting to close because the answer by @Servaes below wonderfully clarifies the misleading use of the word "ordered" in the OP. $\endgroup$ Feb 19, 2019 at 17:44
  • 1
    $\begingroup$ @darij grinberg: Yes, my fault, but it was not because I do not know what is difference between ordered and unordered sets but because of my English, that sometimes I wrongly use words "sorted" and "ordered" as synonyms which here lead to misunderstanding. But that is why I added an explicit example to help to understand what I meant if there were some doubts. $\endgroup$ Feb 19, 2019 at 18:16

5 Answers 5

2
$\begingroup$

TL;DR (or for those unfamiliar with group theory) A brief summary of the results, without proofs.

Any pair of such $n\times n$-matrices with the same unordered set of rows, columns, diagonals and antidiagonals differ by a permutation of their entries, and hence by a permutation of the index set $$\{(i,j):\ 1\leq i,j\leq n\}.$$ It turns out that any permutation that preserves the set of rows, columns, diagonals and antidiagonals is in fact an affine map, i.e. it is some combination of a rotation, reflection, stretching and translation${}^{\ast}$, but in general not all affine maps preserve the set of rows, columns, diagonals and antidiagonals.

You had already found that the translations, reflections and rotations by a quarter turn preserve the set of rows, columns, diagonals and antidiagonals; that's almost everything! What remains are sometimes more rotations, and a lot of stretchings. The stretching of a matrix $M=(m_{ij})_{1\leq i,j\leq n}$ by a factor $1\leq c\leq n$ is the matrix $$N=(n_{i,j})_{1\leq i,j\leq n}\qquad\text{ with }\qquad n_{i,j}:=m_{ci,cj},$$ where we take $ci$ and $cj$ modulo $n$. For example, for $n=5$ and $c=2$ the matrix $$\begin{pmatrix} 1&2&3&4&5\\ 6&7&8&9&10\\ 11&12&13&14&15\\ 16&17&18&19&20\\ 21&22&23&24&25 \end{pmatrix} \qquad\text{ becomes }\qquad \begin{pmatrix} 13&11&14&12&15\\ 3&1&4&2&5\\ 18&16&19&17&20\\ 8&6&9&7&10\\ 23&21&24&22&25 \end{pmatrix}. $$ Such a stretching is well-defined only if $c$ is coprime to $n$, i.e. if $\gcd(c,n)=1$. It turns out that all such stretching with $\gcd(c,n)$ preserve the set of rows, columns, diagonals and antidiagonals.

The question then remains; which rotations preserve the set of rows, columns, diagonals and antidiagonals? The results are fundamentally different depending on whether $n$ is even or odd.

  1. If $n$ is even then these are the repeated rotations by a quarter turn.
  2. If $n$ is odd then these are the repeated rotations by a one-eighth turn.

While it is clear what a quarter turn of a matrix is, I should clarify a one-eighth turn. The one-eighth turn of a matrix $M=(m_{ij})_{1\leq i,j\leq n}$ by a factor $1\leq c\leq n$ is the matrix $$N=(n_{i,j})_{1\leq i,j\leq n}\qquad\text{ with }\qquad n_{i,j}:=m_{i+j,-i+j},$$ where again we take $i+j$ and $-i+j$ modulo $n$. For example, the one-eighth turn of the matrix $$\begin{pmatrix} 1&2&3&4&5\\ 6&7&8&9&10\\ 11&12&13&14&15\\ 16&17&18&19&20\\ 21&22&23&24&25 \end{pmatrix} \qquad\text{ is }\qquad \begin{pmatrix} 21&9&17&5&13\\ 14&22&10&18&1\\ 2&15&23&6&19\\ 20&3&11&24&7\\ 8&16&4&12&25 \end{pmatrix}. $$ Combining all these symmetries quickly becomes confusing, some group theory is essential to get a clear picture. But it turns out the symmetries go together quite well; only rotations and stretching get mixed up, because a half-turn is the same as stretching by a factor $-1$.

To generate all matrices with the same set of rows, columns, diagonals and antidiagonals as a given matrix $M$, simply apply all the symmetries as follows:

  1. Take the transpose of $M$; this is a reflection. Now you have two matrices.
  2. Take all stretchings of these two matrices; i.e. stretch every matrix by a factor $c$ for every $1\leq c\leq n$ with $\gcd(c,n)=1$. Now you have $2\varphi(n)$ matrices, where $n$ denotes the Euler totient function.
  3. Take all rotations of these $2\varphi(n)$ matrices up to a half turn. For even $n$ this means only the quarter turn, for odd $n$ this means the one-eighth, the one-quarter and the three-eighths turns. Now you have either $2\times2\varphi(n)=4\varphi(n)$ or $4\times2\varphi(n)=8\varphi(n)$ matrices, depending on whether $n$ is even or odd.
  4. Finally, take all $n^2$ translations of these $4\varphi(n)$ or $8\varphi(n)$ matrices. This yields a total of either $4\varphi(n)n^2$ or $8\varphi(n)n^2$ matrices, depending on whether $n$ is even or odd, and these are all matrices with the same set of rows, columns, diagonals and antidiagonals.

$\ast$ There are also the shear maps, but these preserve the set of rows, columns, diagonals and antidiagonals only if these are all lines in the $n\times n$-plane, which is the case if and only $n\leq3$.


Here follows the original proof for odd $n$.

Observation: Any two rows, columns, diagonals or antidiagonals that are not in the same category (e.g. that are not both rows) meet in precisely one point if and only if $n$ is odd.

I will use this observation throughout the proof without mention, as the proof concerns only odd $n$. Because this fails for even $n$ the geometry is significantly less intuitive, so I will not consider this case for now.

Observation: The set of $n\times n$-matrices whose entries are precisely the integers from $1$ to $n^2$ inclusive, is naturally in bijection group of symmetries of the affine $n$-plane $\Bbb{A}_2(n):=(\Bbb{Z}/n\Bbb{Z})^2$.

The question then becomes

Which symmetries of $\Bbb{A}_2(n)$ preserve the set of horizontal, vertical, diagonal and antidiagonal lines?

Proposition 1. For odd $n>3$ the set of horizontal, vertical, diagonal and antidiagonal lines is preserved by all symmetries of the form $$\Bbb{A}_2(n)\ \longrightarrow\ \Bbb{A}_2(n):\ \binom{i}{j}\ \longmapsto\ uA\binom{i}{j}+B,$$ with $u\in(\Bbb{Z}/n\Bbb{Z})^{\times}$, $B\in(\Bbb{Z}/n\Bbb{Z})^2$ and $A\in\langle\rho,\mu\rangle$ where $$\rho:=\begin{pmatrix} \hphantom{-}1&1\\ -1&1 \end{pmatrix} \qquad\textit{ and }\qquad \mu:=\begin{pmatrix} 1&\hphantom{u}0\\ 0&-1 \end{pmatrix}. $$

Proof. It is clear that translation by any element of $(\Bbb{Z}/n\Bbb{Z})^2$ sends rows to rows, columns to columns, diagonals to diagonals and antidiagonals to antidiagonals. To see that the same is true for multiplication by any $u\in(\Bbb{Z}/n\Bbb{Z})^{\times}$, note that any line in $\Bbb{A}_2(n)$ is of the form $$L_{a,b,c}:=\{ax+by=c:\ x,y\in\Bbb{Z}/n\Bbb{Z}\},$$ and so multiplication by $u\in(\Bbb{Z}/n\Bbb{Z})^{\times}$ maps this line to the line $L_{a,b,uc}$; in particular the slope of the line is preserved, so this scaling also sends rows to rows, columns to columns, diagonals to diagonals and antidiagonals to antidiagonals. It remains to show that $\rho$ and $\mu$ preserve the set of rows, columns, diagonals and antidiagonals.

Geometrically, multiplication by $\mu$ is a reflection in the first row. This sends rows to rows and columns to columns, and swaps diagonals and antidiagonals. Similarly, multiplication by $\rho$ is a rotation around the point $(0,0)$ over an angle of $-\tfrac{\pi}{4}$. This sends rows to diagonals, diagonals to columns, columns to antidiagonals, and antidiagonals to rows. $\hspace{20pt}\square$

Theorem 2. For odd $n>3$, every symmetry of $\Bbb{A}_2(n)$ that preserves the set of rows, columns, diagonals and antidiagonals is of the form described in Proposition 1.

Proof. See below.

Corollary 3. For any $n\times n$-matrix whose entries are precisely the integers from $1$ to $n^2$ inclusive, there are precisely $8\varphi(n)n^2$ such matrices with the same set of rows, columns, diagonals and antidiagonals, where $\varphi(n)$ denotes Eulers totient function.

Lemma 1: Let $n$ be an odd positive integer. Let $\sigma$ be a symmetry of $\Bbb{A}_2(n)$ that preserves the set of rows, columns, diagonals and antidiagonals such that $\sigma((0,0))=(0,0)$ and $\sigma((0,1))$ is on the first row. Then there exists some $d\in(\Bbb{Z}/n\Bbb{Z})^{\times}$ such that $$\forall k\in\Bbb{Z}/n\Bbb{Z}:\qquad\sigma((0,k))=(0,dk).$$

Proof. Let $d\in\Bbb{Z}/n\Bbb{Z}$ be such that $\sigma((0,1))=(0,d)$, and note that $d\neq0$. Because $\sigma$ preserves the set of rows, columns, diagonals and antidiagonals, there are at most six candidates for $\sigma((1,1))$. After all, the point $(1,1)$ is in the same column as $(0,1)$ and on the same diagonal as $(0,0)$, and $\sigma$ maps these to a column, diagonal or antidiagonal through $(0,d)$ and $(0,0)$. The following picture clarifies the situation:

enter image description here

This picture shows the points $(0,0)$ and $(0,d)$ in black, their columns, diagonals and antidiagonals in blue, and the possible positions of $\sigma((1,1))$ also in blue.

The point $(0,2)$ is the unique point on the line through $(0,0)$ and $(0,1)$ that is on a line with $(1,1)$, and that is distinct from $(0,0)$ and $(0,1)$. For each candidate point for $\sigma((1,1))$ this unique point and corresponding line are shown in red in the picture above. Some elementary algebra shows that these points are $(0,-d)$, $(0,\tfrac{d}{2})$ and $(0,2d)$, just as the picture suggests, where $(0,\tfrac{d}{2})=(0,\frac{n+1}{2}d)$ and $(0,-d)=(0,(n-1)d)$.

We will prove that $\sigma((0,2))=(0,2d)$. Note that for $n=3$ we have $2d=-d=\frac{n+1}{2}d$ and so there is nothing to prove. So suppose $n>3$.

Consider the possible positions for $\sigma((1,2))$. Note that $(1,2)$ is the unique point that is on a line with $(0,1)$, $(0,2)$ and $(1,1)$ but not on a line with any pair of them. Also note that $(1,2)$ is not on a line with $(0,0)$ because $n>3$, and it is on the unique line through $(1,1)$ that does not contain $(0,0)$, $(0,1)$ or $(0,2)$.

If $\sigma((1,1))=(d,0)$, which is the bottom left blue point in the picture above, then $\sigma((0,2))=(0,-d)$. Then $\sigma((1,2))$ is on the unique line through $\sigma((1,1))=(d,0)$ that does not contain $(0,0)$, $(0,d)$ and $(0,-d)$, and it is on one of the two lines through $(0,-d)$ that does not contain $(0,0)$ , $(0,d)$ or $(d,0)$. These lines are shown in green in the following picture:

enter image description here

Because $\sigma((1,2))$ is not on a line with $\sigma((0,0))=(0,0)$, we must have $\sigma((1,2))=(-2d,d)$. This point is shown in green in the picture above. But for $n>3$ this point is not on a line with $\sigma((0,1))=(0,d)$, a contradiction. This proves that $\sigma((1,1))\neq(d,0)$, and by symmetry also that $\sigma((1,1))\neq((-d,0))$. This implies that $\sigma((0,2))\neq(0,-d)$, as the first picture shows.

A similar geometrical argument shows that if $\sigma((1,1))=(\pm\tfrac{d}{2},\tfrac{d}{2})$ then the point $(-1,1)$ has nowhere to go, from which it follows that $\sigma((0,2))\neq(0,\tfrac{d}{2})$. I omit the details.

This proves that $\sigma((0,2))=(0,2d)$, and a simple induction argument then shows that $\sigma((0,k))=(0,dk)$ for all $k\in\Bbb{Z}/n\Bbb{Z}$. Because $\sigma$ is injective we have $d\in(\Bbb{Z}/n\Bbb{Z})^{\times}$.$\hspace{20pt}\square$

Corollary: In the situation above we have $\sigma((1,1))=(\pm d,d)$.$\hspace{20pt}\square$

Lemma 2: Let $n$ be an odd positive integer. Let $\sigma$ be a symmetry of $\Bbb{A}_2(n)$ that preserves the set of rows, columns, diagonals and antidiagonals that is the identity on $(0,0)$, $(0,1)$ and $(1,1)$. Then $\sigma$ is the identity on $\Bbb{A}_2(n)$.

Proof. To be supplied; similar geometrical arguments as before.$\hspace{20pt}\square$

Proof of Theorem 1. Let $\sigma$ be a symmetry of $\Bbb{A}_2(n)$ that preserves the set of rows, columns, diagonals and antidiagonals. Let $(i,j)=\sigma((0,0))$ and let $\tau$ denote the translation by $(-i,-j)$. Then the permutation $\tau\sigma$ fixes the point $(0,0)$, and $\tau$ is the unique translation for which this holds.

Because $\tau\sigma$ preserves lines we know that $\tau\sigma((0,1))$ is on a horizontal, vertical or diagonal line through $\tau\sigma((0,0))=(0,0)$. Then there is a unique $k\in\{0,1,2,3\}$ such that $\rho^k\tau\sigma((0,1))$ is on the horizontal line through $(0,0)$, and hence by Lemma 1 the restriction of $\rho^k\tau\sigma$ to the first row is given by multiplication by some $d\in(\Bbb{Z}/n\Bbb{Z})^{\times}$. Let $\gamma_d(i,j):=(di,dj)$ denote the scaling by $d$, which preserves the sets of rows, columns, diagonals and antidiagonals. Then $\gamma_d\rho^k\tau\sigma$ is the identity on the first row, and by the Corollary we have $$\gamma_d\rho^k\tau\sigma((1,1))=(\pm1,1).$$ Then there is a unique $l\in\{0,1\}$ such that $$\mu^l\gamma_d\rho^k\tau\sigma((1,1))=(1,1).$$ Now it follows from Lemma 2 that this map is the identity, and hence $$\sigma((x,y))=(\tau^{-1}\rho^{-k}\gamma_d^{-1}\mu^{-l})(x,y)=d^{-1}\rho^{-k}\mu^l\binom{x}{y}-\binom{i}{j},$$ for all $(x,y)\in\Bbb{A}_2(n)$. This shows that $\sigma$ is a symmetry of the form described in Theorem 1.$\hspace{20pt}\square$

$\endgroup$
3
  • 1
    $\begingroup$ This is beyond me. So I can not confirm nor deny. Anyway I give you up point for that it must have taken you too much time. $\endgroup$ Feb 21, 2019 at 21:23
  • $\begingroup$ @azerbajdzan I'm sorry it is beyond you. And thank you, it did take me too much time indeed. $\endgroup$ Feb 21, 2019 at 22:10
  • $\begingroup$ @azerbajdzan I have also solved the problem for even $n$, to my surprise it is simpler! I have written up a brief simplified version of the results without proofs. Maybe I will write up the proof for even $n$ tomorrow. +1 to you for a very interesting question too. $\endgroup$ Feb 22, 2019 at 0:07
2
$\begingroup$

I have answered your question both in its literal interpretation, which has a trivial answer, and I've tried to interpret your actual question on the basis of your example, and your finding of $432$ matrices for $n=3$. For the latter, continue reading from the second horizontal line onward.


Literal interpretation, trivial answer:

Taking your question literally, the answer is $1$ for all $n$. After all, if the ordered sets $$(\text{rows},\ \text{columns},\ \text{diagonals},\ \text{antidiagonals}),$$ of two matrices are the same, then in particular their sets of rows and columns are the same. Of course the $i,j$-th entry of a matrix is in the $j$-th place in some row and the $i$-th place in some column, so its sets of rows and columns together determine the matrix. If we consider the unordered sets $$\{\text{rows},\ \text{columns},\ \text{diagonals},\ \text{antidiagonals}\},$$ then there are more options; transposing a matrix swaps the sets of rows and columns, but preserves the sets of diagonals and antidiagonals. Similarly, reflecting a matrix along a horizontal (or vertical) axis preserves the sets of rows and columns, but preserves the sets of diagonals and antidiagonals. In this way we already find $4$ matrices with the same unordered sets.

Proposition: For every square matrix are either $4$ or $8$ matrices with the same unordered set.

Proof. Given two matrices $M$ and $N$ with the same unordered set, the first row $M$ is either a row, column, diagonal or antidiagonal of $N$. The other rows of $M$ are precisely the $n$-tuples in the unordered set of $M$ that do not share a coordinate with the first row. Hence they correspond to the same type (row, column, diagonal or antidiagonal) as the first row. So the matrix $N$ induces a permutation of the set $$\{\{\text{rows of }M\},\{\text{columns of }M\},\{\text{diagonals of }M\},\{\text{antidiagonals of }M\}\}.\tag{1}$$ As noted before, a matrix is determined by its sets of rows and columns. So given $M$, the matrix $N$ is determined by whether the first row and first column of $M$ are rows, columns, diagonals or antidiagonals. This shows that conversely $N$ is uniquely determined by the permutation of $(1)$ it induces, and moreover that $N$ is determined by where it maps the rows and columns of $N$. This shows that the set of matrices with the same unordered set are in bijection with a subgroup of $S_4$ of order at most $4\times3=12$. As noted before, transposing and reflecting $M$ preserves the set $(1)$. This show that this subgroup contains a subgroup isomorphic to $\langle(1\ 2),(3\ 4)\rangle$, and hence it is isomorphic either $V_4$ or $D_8$. Hence there are either $4$ or $8$ matrices with the same unordered set. $\hspace{10pt}\square$

The proposition could be improved by determining whether there are $4$ or $8$ such matrices, and what this depends on, if anything. But given that you found $432$ matrices with the same 'ordered set', you must mean something else. My best guess is that you take the rows, columns, diagonals and antidiagonals as unordered sets as well.


Different interpretation, interesting answer:

Given a matrix $M$, let $X$ its unordered set of unordered sets. For you example $3\times3$-matrix, this is $$X=\left\{\begin{array}{lll}\{1,2,3\},&\{4,5,6\},&\{7,8,9\},\\ \{1,4,7\},&\{2,5,8\},&\{3,6,9\},\\ \{1,5,9\},&\{2,6,7\},&\{3,4,8\},\\ \{3,5,7\},&\{2,4,9\},&\{1,6,8\} \end{array}\right\}.$$ In general, if $M$ is an $n\times n$-matrix then $|X|=4n$ (if $n\geq3$)${}^1$, and each element of $X$ is an $n$-element subset of $\{1,\ldots,n^2\}$. Moreover, the relation on the set $X$ consisting of the pairs $$(x,y)\in X\times X\qquad\text{ with }\qquad x\cap y=\varnothing,$$ is an equivalence relation that partitions $X$ into $4$ subsets of $n$ elements each (if is odd)${}^2$, say $X_1$, $X_2$, $X_3$ and $X_4$. These correspond to the sets of rows, columns, diagonals and antidiagonals of $M$.

As noted above (in the first part of my answer to the literal interpretation), any ordering of the rows and columns determines the matrix entirely. So any choice of $X_i$ and $X_j$ for the rows and columns, and any ordering of $X_i$ an $X_j$ determines a matrix with the same unordered set as $M$. This yields a total of $4\times3\times n!\times n!=12(n!)^2$ matrices with the same unordered set as $M$.

Of course, different choices of $X_i$ and $X_j$ yield different matrices, as their rows and columns will differ. Similarly, different orderings of $X_i$ and $X_j$ yield different matrices, as the orders of their rows and/or columns will differ. This shows that there are precisely $12(n!)^2$ matrices with the same unordered set, and this characterisation gives you a way to construct them all explicitly.

Note that in particular, for $n=3$ this gives $12\times(3!)^2=432$ matrices, in agreement with your finding.


More explicit description of algorithm to generate all solutions:

To generate all matrices with the same unordered set $X$ as some given $n\times n$-matrix $M$, where $n\geq3$ is odd,

  1. Define $X_1$, $X_2$, $X_3$ and $X_4$ as the sets of rows, columns, diagonals and antidiagonals.
  2. Choose distinct sets $X_a$ and $X_b$ for the rows and columns.
  3. Choose orderings of $X_a$ and $X_b$, and denote them by $$X_a=(X_a[1],\ldots,X_a[n]) \qquad\text{ and }\qquad X_b=(X_b[1],\ldots,X_b[n]).$$
  4. For each integer $k\in\{1,\ldots,n^2\}$, determine $i$ and $j$ such that $k\in X_a[i]$ and $k\in X_b[j]$.
  5. Define $n_{ij}:=k$.
  6. Define $N:=(n_{ij})_{1\leq i,j\leq n}$.

The matrix $N$ now has the same unordered set $X$ as $M$, and going through every choice of $X_a$ and $X_b$ and every ordering of $X_a$ and $X_b$ yields all matrices with the same unordered set $X$.

Below is my first attempt at writing some sort of pseudo-code. In stead of making the $X_i$ sets and choosing orderings, I make the $X_i$ lists and choose permutations of them.

Input matrix M
Define X_1 = list of rows of M        
Define X_2 = list of columns of M
Define X_3 = list of diagonals of M
Define X_4 = list of antidiagonals of M
For each {integer a in {1,2,3,4}}{               // X_a is the set of rows
   For each {integer b in {1,2,3,4} with b!=a}{  // X_b is the set of columns
      For each {permutation s in S_n}{           // s is an ordering of X_a
         For each {permutation t in S_n}{        // t is an ordering of X_b 
            For each {integer k in {1,...,n^2}}{
               Define i such that k in X_a[s(i)]
               Define j such that k in X_b[t(j)]
               Define n_ij = k
            }
            Output matrix N_{a,b,s,t} = (n_ij).
         }
      }
   }
}

This outputs all matrices with the the same unordered set $X$ as $M$.


Footnotes:

$1$: If $n\leq2$ then the sets of rows, columns, diagonals and antidiagonals are not all distinct; for $n=1$ all four sets coincide and so $|X|=1$, for $n=2$ the sets of diagonals and antidiagonals coincide and so $|X|=6$.

$2$: If $n$ is odd, then every diagonal and antidiagonal have precisely one entry in common. If $n$ is even this is not the case, and the relation is not an equivalence relation.

$\endgroup$
21
  • $\begingroup$ I thought my question was stated correctly. The order of numbers in rows, columns and diagonals does not matter. And also the order of rows, columns and diagonals themselves does not matter. And also it does not matter whether it is column or row or diagonal. We can call them all, say, "lines". Each $n\times n$ matrix has $4*n$ such lines. But if you want to compare two different matrices in a "order-does-not-matter" way you have to do it by comparing ordered sets of ordered lines. Where does "3" come from in your $4\times3\times n!\times n!$ formula? $\endgroup$ Feb 19, 2019 at 12:44
  • $\begingroup$ I mean that if you want to compare, say, (1,4,3,2) with (3,4,2,1) and order does not matter then you have to order then. You get (1,2,3,4) in both cases and you now know the the two sets are identical if order does not matter. $\endgroup$ Feb 19, 2019 at 12:49
  • 1
    $\begingroup$ Your formula does not seem to work. For n=2 we have 8 different matrices with same ordered set, but your formula gives: $12(n!)^2=12(2!)^2=48$. Notice that it is even bigger than all possible $n\times n$ matrices since $4!=24$. $\endgroup$ Feb 19, 2019 at 13:05
  • 1
    $\begingroup$ if i understand correctly, this argument hinges on the claims that (A) the 12 sets-of-3 can be partitioned into 4 equivalence classes (of 3 sets each), and (B) you can pick any 2 classes to be rows and columns of the "new" matrix. this is a very ingenious argument! however, while (A) is certainly true, i dont see an immediate proof that (B) is true. (in fact i believe it is true for $n=3$ but not e.g. $n=5$. but i dont see a proof either way.) can you comment on this? $\endgroup$
    – antkam
    Feb 19, 2019 at 19:10
  • 1
    $\begingroup$ @Servaes: The algorithm has $n^2 \left(n^2-3 n+2\right) (n!)^2$ cycles and outputs $\left(n^2-3 n+2\right) (n!)^2$ possible solutions out of which you have to select $8\phi(n)n^2$ correct ones. For $n=5$ it is $4320000$ cycles, $172800$ possible solutions out of which only $800$ are correct. For $n=7$ it is $37340352000$, $762048000$, and according to your new formula only $8\phi(7)7^2=2352$ correct. So it becomes computationally infeasible. Nevertheless I can not do it better than you. Do you see any possible improvements in your algorithm? $\endgroup$ Feb 21, 2019 at 21:20
2
$\begingroup$

I am adding a new answer because this takes a drastically different viewpoint, which gives a very simple solution, but works only for the case of $n=3$.

After mulling over the insightful answer from @Servaes, I realized the $3\times 3$ case is a finite affine plane: https://en.wikipedia.org/wiki/Affine_plane_(incidence_geometry)#Finite_affine_planes

In particular this means any 2 points (2 cells in the matrix) defines a line (row / column / main diagonal / anti-main diagonal). Obviously this is true only for $n=3$.

Based on this observation the counting becomes super simple:

  • There are 9 places for 1.

  • After that, there are 8 places for 2.

  • After 1 & 2, they together determine 3's location. (1 & 2 define a line, and 3 must be the remaining place in that line.)

  • There are 6 places left for 4.

  • After 1, 2, 3 & 4, all other numbers are determined: 1 & 4 determine 7's location, 2 & 4 determine 9's location, 3 & 4 determine 8's location, 3 & 9 determine 6's location, and 2 & 8 determine 5's location.

So the total number of such matrices $= 9 \times 8 \times 6 = 432$.

This proof is not quite complete because, technically speaking, I have to show that the assignments above do not create a contradiction. E.g. 2 & 8 determine 5's location, but 1 & 9 also determine 5's location, and I have not shown that those two location-assignments agree. However, if you can see why the matrix is analogous to the finite affine plane, then the symmetry between all lines would argue that the assignments must agree. Or to use the words of lazy professors everywhere, "It's obvious." :) (Sorry!)

$\endgroup$
5
  • $\begingroup$ I can produce the 432 matrices from 6 "fundamental" matrices by shifting (9 possibilities), rotating (4 possibilities) and transposing (2 possibilities). So it is $6*9*4*2=432$. But I can not figure out what relations are among those 6 "fundamentals". A good question might be if the set of "fundamental" matrices can be reduced, ideally to only one matrix, and then to produce the rest by simple operations like shifting, rotating, transposing, mirroring (maybe there are other operations). $\endgroup$ Feb 20, 2019 at 12:19
  • $\begingroup$ @Antkam I have made similar observations in my attempts, though the details are quite involved. For $n=3$ you indeed get the full affine group and hence the number of matrices is $(n^2-1)(n^2-n)n^2=8\times6\times9=432$. For odd $n>3$ this is not the case, and you get a subgroup of the affine group of order $8\phi(n)n^2$, where $\phi(n)$ denotes Eulers totient function. $\endgroup$ Feb 21, 2019 at 9:11
  • $\begingroup$ @azerbajdzan - one operation thats different from shifting, rotating, transposing, is the "shearing" in my other answer. but i have trouble with the group theory aspects of what happens when operations are combined. you can certainly use just shearing to get several different matrices, but are they equivalent under further shifting, etc? i dont know how to track that. $\endgroup$
    – antkam
    Feb 21, 2019 at 14:25
  • 1
    $\begingroup$ @Servaes - there is no question in my mind that your answer, based on choosing which of 4 classes to be the new rows and which other of the 4 classes to be the new columns, is valid for $n=3$. however, i didnt see how to argue its correctness until i realize we're looking at the entire finite affine plane, and once i realize that then i can present this (IMHO) simpler counting method. it is also clear that for other $n$ the affine plane analogy needs much more modifications. i am not familiar with group theory enough to understand your more detailed arguments about subgroups, sorry... :( $\endgroup$
    – antkam
    Feb 21, 2019 at 14:29
  • $\begingroup$ @antkam I have added a summary of the results of my answer, without proofs. I have tried to avoid going into group theory, and in stead to stay closer to the geometric ideas and the explicit calculations involved. However, group theory is essential to the proofs and to the structure of the problem. I hope it is of some help anyway. $\endgroup$ Feb 22, 2019 at 0:14
1
$\begingroup$

Too long & messy for a comment...

As usual we will call the diagonal from top-left to bottom-right as the main diagonal.

One operation you didn't include (which works for $n=3$ only, I think) is swap any 2 columns (or rows). This would maintain the row-sets and column-sets, while the main-diagonal-sets (main diagonal and parallel lines) would become the anti-main-diagonal sets (perpendicular to main diagonal), and vice versa.

Another operation you didn't include is a kind of "shear" (my term) - keep the first column the same, shift the 2nd column down by 1, and shift the 3rd column down by 2 (equivalent to up by 1). This maintains the column-sets, but the old row-sets become the new main-diagonal sets, the old main-diagonal-sets become the new anti-main-diagonal-sets, and the old anti-main-diagonal-sets become the new row sets. E.g.

\begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ \end{pmatrix}

becomes

\begin{pmatrix} 1 & 8 & 6 \\ 4 & 2 & 9 \\ 7 & 5 & 3 \\ \end{pmatrix}

which can be further transformed into your 2nd matrix by swapping the first 2 rows.

However, I get quite confused when I think of how these combine with your other operations (especially reflections). So I can't correctly count to 432 yet.

$\endgroup$
2
  • 1
    $\begingroup$ Swapping two rows is the same as a reflection about the third row. Similarly, the shear is a reflection about a diagonal composed with a quarter turn. $\endgroup$ Feb 19, 2019 at 8:54
  • $\begingroup$ @Servaes nice observations! i am simply saying these arent in the OP (as the OP meant different things when mentioning "reflections"). anyway, your answer has a much better approach, as my approach eventually leads to questions of what sequences of operations are equivalent. $\endgroup$
    – antkam
    Feb 19, 2019 at 19:13
1
$\begingroup$

I believe the previous answers have sufficiently addressed the $3\times3$ matrix. In this post I will consider the $4\times4$ matrix below.

\begin{pmatrix} 0&1&2&3\\ 4&5&6&7\\ 8&9&A&B\\ C&D&E&F \end{pmatrix}

Consider first the groups containing $0$: $$(0,1,2,3),(0,4,8,C),(0,5,A,F),(0,7,A,D)$$ We see that $A$ appears in two of these groups. As such, there is only one position (relative to the position of $0$) in which $A$ can be placed, as shown here with $0$ in the upper left corner, where it will be fixed for the purpose of counting: \begin{pmatrix} 0&?&?&?\\ ?&?&?&?\\ ?&?&A&?\\ ?&?&?&? \end{pmatrix} Now there are $8$ ways to complete the two diagonals containing both $0$ and $A$: \begin{matrix} \begin{pmatrix} 0&?&?&?\\ ?&5&?&7\\ ?&?&A&?\\ ?&D&?&F \end{pmatrix} & \begin{pmatrix} 0&?&?&?\\ ?&5&?&D\\ ?&?&A&?\\ ?&7&?&F \end{pmatrix} & \begin{pmatrix} 0&?&?&?\\ ?&7&?&5\\ ?&?&A&?\\ ?&F&?&D \end{pmatrix} & \begin{pmatrix} 0&?&?&?\\ ?&7&?&F\\ ?&?&A&?\\ ?&5&?&D \end{pmatrix} \\[2ex] \begin{pmatrix} 0&?&?&?\\ ?&D&?&5\\ ?&?&A&?\\ ?&F&?&7 \end{pmatrix} & \begin{pmatrix} 0&?&?&?\\ ?&D&?&F\\ ?&?&A&?\\ ?&5&?&7 \end{pmatrix} & \begin{pmatrix} 0&?&?&?\\ ?&F&?&7\\ ?&?&A&?\\ ?&D&?&5 \end{pmatrix} & \begin{pmatrix} 0&?&?&?\\ ?&F&?&D\\ ?&?&A&?\\ ?&7&?&5 \end{pmatrix} \end{matrix} Next we will take one of these and fill in the remaining elements, first noting that the column containing both $D$ and $5$ must also contain both $1$ and $9$, and that $9$ does not appear in any group with $0$, so this column must be $(1,D,9,5)$. Likewise, the column $(?,F,?,7)$ must be $(3,F,B,7)$. The second and fourth rows can also be completed in this manner, and this leads to exactly one solution for each of the eight partial solutions: \begin{matrix} \begin{pmatrix} 0&?&?&?\\ ?&D&?&F\\ ?&?&A&?\\ ?&5&?&7 \end{pmatrix} &\implies& \begin{pmatrix} 0&1&2&3\\ C&D&E&F\\ 8&9&A&B\\ 4&5&6&7 \end{pmatrix} \end{matrix} With $8$ solutions for each of the $4^2$ possible positions for the $0$, there are a total of $8\cdot4^2=128$ qualifying matrices.

$\endgroup$
3
  • $\begingroup$ My counts for $5\times5$ and $6\times6$ are $32\cdot5^2=800$ and $8\cdot6^2=288$ respectively. $\endgroup$ Feb 20, 2019 at 17:58
  • $\begingroup$ I found 128 for $n=4$ and 800 for $n=5$ too, but I take it as a lower bound for now until a proof is provided. $\endgroup$ Feb 20, 2019 at 18:14
  • $\begingroup$ @azerbajdzan I have managed a brute-force confirmation of our counts for $n<6$. For greater values of $n$ I expect $8n^2$ for even $n>2$ and $8n^2(n-1)$ for odd $n>3$ $\endgroup$ Feb 22, 2019 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.