Find the minimum and maximum rank of $n\times n$ matrices consisting exactly $1,2,\dots,n^2$

Question

A problem that just popped into my head. I wrote a Python program to run some tests, and according to the results, I believe the answer is

$$ \min_A\operatorname{rank}(A)=2, \qquad \max_A\operatorname{rank}(A)=n $$ but I can't manage to prove it. Is there a way to solve this?

Answer 1

Let us consider that $n \ge 3$.

The minimal rank can be (much) less than $n$ by taking column vectors obtained by segmenting the sequence $1,2,3 \cdots n^2$ by like this for the case $n=4$:

$$M_4=\begin{pmatrix} 1 & 5 & 9 & 13\\ 2 & 6 & 10 & 14\\ 3 & 7 & 11 & 15\\ 4 & 8 & 12 & 16 \end{pmatrix}$$

which has rank $2$.

Indeed, one can exhibit the following independent elements of the kernel of $M_4$:

$$\begin{pmatrix} 1 \\ -2\\ 1\\ 0 \end{pmatrix} \ \text{and} \ \begin{pmatrix} 0 \\1 \\ -2\\ 1 \end{pmatrix}$$

As the kernel has dimension $d \ge 2$, by rank-nullity theorem, one has

$$rank{M_4} \le 4-2 = 2$$

In fact, the rank of $M_4$ is exactly $2$ because we can exhibit $2$ non proportional elements of the range of $M_4$, i.e.,

$$M_4\begin{pmatrix} 1 \\ 0\\ 0\\ 0 \end{pmatrix} = \begin{pmatrix} 1 \\ 2\\ 3\\ 4 \end{pmatrix} \ \text{and} \ M_4\begin{pmatrix} 0 \\ 1\\ 0\\ 0 \end{pmatrix} = \begin{pmatrix} 5 \\ 6\\ 7\\ 8 \end{pmatrix}$$

This type of rank-$2$ matrix can immediately be extended to any $M_n$ built on the same model.

Therefore the minimal rank is at most $2$. I think that having a rank 1 is impossible, for a general value of $n$, but I haven't established it.

Just seen this connected question.

Answer 2

Suppose you have $n$ distinct numbers, and you want to arrange them into an $n$-dimensional vector so that they are not in the span of $n-1$ other vectors, $A$.

If this is impossible, it means all arrangements of them are in span$A$, hence all linear comninations of arrangements of them are in span$A$ are in span$A$. Consider $2$ arrangements, $u$ and $v$ which differ only by swapping the $i$ and $j$th elements. Then their difference is $$v-u = (v_i-u_i) e_i - (v_i-u_i) e_j$$ And $v_i-u_i \ne 0$ so this is a nonzero scalar multiple of $e_i-e_j$, so $e_i-e_j$ must be in span$A$.

The span of $e_i-e_j$ for all $i,j$, and some vector $w$ whose elements don't sum to $0$ is the entire vector space. So if the sum of the $n$ numbers is not $0$, we get a vector with nonzero sum which is also in span$A$, so span$A$ must be the whole space. But that is impossible, as dim(span$A$) = $n-1 < n$. So we can always find some arrangement of the numbers which works.

This means we can also find an arrangement which works if $A$ contains less than $n-1$ vectors. This means we can build a matrix of full rank by repeatedly choosing $n$ of the $n^2$ numbers, then arranging them into a vector which isn't in the span of the previous vectors. As the squares are all positive, their sum cannot be $0$, so it will always be possible to keep doing this until you get a full rank matrix.

So the maximum rank is $n$. Others have pointed out the minimum rank is $2$ (for $n \ge 2$).

Answer 3

With $A_{i,j}=(j-1)n+i$ and $n>1$, $\mathrm{rank}(A)=2$, with the following rank factorization:

$U$ has dimensions $n\times2$, $V$ has dimensions $2\times n$, and let $$A_{i,j}=n\times(j-1)+i\times1=U_{i,1}V_{1,j}+U_{i,2}V_{2,j}$$ Matching coefficients yields $U_{i,1}=n, U_{i,2}=i, V_{1,j}=j-1,V_{2,j}=1$. Then $A=UV$.

Note that this $A$ is the matrix filled with values $1\dots n^2$ column by column.

Therefore the minimum rank among the considered matrices is $\le2$, for $n>1$.