How many square matrices are there with given columns, rows and diagonals

Question

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?

Answer 1

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:

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:

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$

Answer 2

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.

Answer 3

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.

Answer 4

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!)

Answer 5

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.