# “Sorting” matrix entries by swapping rows and columns

Suppose one has an $n \times n$ matrix whose entries are filled with the numbers $1,2,\ldots,n^2$, but not in that order.

Q1: What is the largest number of row or column swaps ever needed to end up with the entries sorted, e.g., for $n=3$, to reach this matrix: $$\left( \begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{array} \right)$$ A row swap interchanges two rows; a column swap interchanges two columns. So I am asking for the most disordered matrix with respect to swaps.

Q2: If the $n^2$ numbers are randomly placed, what is the expected minimum number of row and column swaps needed to sort the matrix?

I have no doubt these questions have been explored and answered, but I must not be searching under the right terminology. Thanks for your help!

-

You cannot always swap into this position. For example, when $n = 2$ and $$A = \pmatrix{1 & 4 \\ 2 & 3},$$ $A$ cannot be moved into your standard form via row and column swaps. Indeed, any row or column swap will keep $1$ and $4$ in the same row (possibly in the opposite order).
In fact, the only $2 \times 2$ matrices which can be brought to your standard form are $$\pmatrix{1 & 2 \\ 3 & 4}, \pmatrix{3 & 4 \\ 1 & 2}, \pmatrix{2 & 1 \\ 4 & 3}, \text{ and } \pmatrix{4 & 3 \\ 2 & 1}.$$
In general, there are $(n^2)!$ possible matrices with the entries $1,2,\dots, n^2$ each occurring once. But there are only $(n!)^2$ row and column swaps possible.