Permutations of a square matrix elements and determinant How many ways can the elements $a_{m,n}\in\mathbb{R}$ of a square matrix $N\times N$ be permuted with each other so that the value of the matrix determinant does not change? Thanks
 A: There are exactly $(N!)^2$ determinant-preserving permutations. Namely, every such permutation can be achieved by...

*

*permuting the rows arbitrarily [$N!$ ways], then


*permuting the columns, such that the sign of the column permutation equals that of the row permutation. [$N!/2$ ways], then


*possibly transposing the matrix [$2$ ways].
It is obvious all such permutations preserve the determinant. I will now prove there are no others.
Claim 1: Let $M$ be an $N\times N$ matrix with precisely $N$ zero entries. As long the zeroes of $M$ are not in one row, or not in one column, then the nonzero entries can be chosen such that $\det M\neq 0$.

Proof: First, I claim that there must exist $N$ non-zero entries in $M$ which are pairwise in different rows and columns. This can be proven with Hall's marriage theorem. Namely, consider a bipartite graph, whose $2N$ vertices are the rows and columns of $M$, such that a row is joined to a column if the entry at their intersection is nonzero. For any subset $r$ of rows, you can show there exist at least $N-\lfloor N/r\rfloor$ columns joined to at least one of those rows (since to not be joined to a column, you need $r$ zeroes in that column, but there are only $N$ zeroes to go around). You can show that $N-\lfloor N/r\rfloor\ge r$, except in the cases $r=1$ and $r=N$. When $r=1$, we know any one row has at least one neighbor because it is given that not all of the zero entries are in that row. When $r=N$, we know each column is adjacent to some row, because it is given that not all of the zero entries are in that column.
Once we have $N$ entries in pairwise different rows and columns, make each of those entries $1$, and the remaining nonzero entries of $M$ real numbers whose absolute value is strictly less than $1/N!$. You can verify that $\det M \neq 0$, using the form $\det M=\sum_\pi \prod_{i=1}^N M_{i,\pi(i)}$. When $\pi$ corresponds to the $N$ entries which were chosen to be $1$, the sum contributes $+1$. For all other $\pi$, the summands are too small to cancel out that $+1$.

Claim 2: Let $\pi$ be a $\det$-preserving permutation. Then $\pi$ must map each row of $M$ to either a row or column.

Proof: Let $\pi$ be a permutation such that there is a row which $\pi$ does not send to a row or column. Let $M$ be a matrix with all zeroes in that row. Then $\det M=0$, but using claim $1$, the nonzero entries of $M$ can be chosen so that the determinant of the permuted matrix is nonzero. Therefore, $\pi$ is not $\det$-preserving.

Claim 3: All $\det$-preserving permutations are of the form described.

Proof: If  $\pi$ is a $\det$-preserving permutation, then  $\pi$ must either send the first row of $M$ to a row or column of $M$. In the first case, all other rows must be sent to rows. Each row may then be mixed up in some way, but since all columns must be sent to columns, each row must be mixed up in the same way (i.e, the rows are mixed up by permuting the columns of $M$). The sign restriction of the column permutation follows by looking at when $M$ is the identity matrix. In the case where the first row of $M$ is mapped to a column, a similar argument applies.

