IMC 2007 · Day 1 · P2

The minimal rank is 2 and the maximal rank is $n$. To prove this, we have to show that the rank can be 2 and $n$ but it cannot be 1.

(i) The rank is at least 2. Consider an arbitrary matrix $A = [a_{ij}]$ with entries $1, 2, \dots, n^2$ in some order. Since permuting rows or columns of a matrix does not change its rank, we can assume that $1 = a_{11} < a_{21} < \dots < a_{n1}$ and $a_{11} < a_{12} < \dots < a_{1n}$. Hence $a_{n1} \ge n$ and $a_{1n} \ge n$ and at least one of these inequalities is strict. Then $$\det \begin{bmatrix} a_{11} & a_{1n} \\ a_{n1} & a_{nn} \end{bmatrix} < 1 \cdot n^2 - n \cdot n = 0$$ so $\operatorname{rk}(A) \ge \operatorname{rk} \begin{bmatrix} a_{11} & a_{1n} \\ a_{n1} & a_{nn} \end{bmatrix} \ge 2$.

(ii) The rank can be 2. Let $$T = \begin{pmatrix} 1 & 2 & \dots & n \\ n+1 & n+2 & \dots & 2n \\ \vdots & \vdots & \ddots & \vdots \\ n^2 - n + 1 & n^2 - n + 2 & \dots & n^2 \end{pmatrix}$$ The $i$th row is $(1, 2, \dots, n) + n(i-1) \cdot (1, 1, \dots, 1)$ so each row is in the two-dimensional subspace generated by the vectors $(1, 2, \dots, n)$ and $(1, 1, \dots, 1)$. We already proved that the rank is at least 2, so $\operatorname{rk}(T) = 2$.

(iii) The rank can be $n$, i.e. the matrix can be nonsingular. Put odd numbers into the diagonal, only even numbers above the diagonal and arrange the entries under the diagonal arbitrarily. Then the determinant of the matrix is odd, so the rank is complete.