3
$\begingroup$

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!

1 Answers 1

7

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.

  • 0
    No wonder I couldn't find information: It is generally impossible! Thanks, Michael!2012-10-02