Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
    
No wonder I couldn't find information: It is generally impossible! Thanks, Michael! –  Joseph O'Rourke Oct 2 '12 at 1:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.