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!

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ No wonder I couldn't find information: It is generally impossible! Thanks, Michael! $\endgroup$ – Joseph O'Rourke Oct 2 '12 at 1:01

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.