# Minimal rank of special matrix

Let $n\geq 2$ be an integer and $A=(a_{ij})$ an $n\times n$ matrix whose elements are $1,2,\dots,n^2$. I am supposed to find the minimal and maximal possible rank of $A$. (In this question, I'm not at all interested in the maximal rank, I want to try and figure it out myself.) I found that if I order the elements in ascending order, i.e. the first row is $(1,2,\dots,n)$, the second $(n+1,n+2,\dots,2n)$ and so on, that $r(A)=2$. However, if I want to be sure that the minimal rank is indeed $2$, I should also prove that the rank can never be $1$. (Maybe I'm wrong, and the rank $\textit{can}$ be $1$, in that case an example would be nice.) So I've tried this:

If the rank is $1$, then all rows are of the form $$\alpha_i (a_{i1},\dots,a_{in}) = (a_{11},\dots,a_{1n}), \ \alpha_i \in \mathbb{Q}, \ i=2,\dots,n.$$ So obviously $a_{ij} = \frac{1}{\alpha_i} a_{1j}$, $\forall i=2,\dots,n, j=1,\dots,n$.

Because the sum of the elements has to be equal to $\frac{n^2(n^2+1)}{2},$ this means that $$(1+\frac{1}{\alpha_2}+\cdots+\frac{1}{\alpha_n})(a_{11}+a_{12}+\cdots+a_{1n}) = \frac{n^2(n^2+1)}{2}.$$

I've tried finding some upper or lower bound for the LHS that would prove that this can't hold for any $n$, but I couldn't get anything that would actually lead to a contradiction.

Any hints are welcome.

• Hint: Consider the row containing the largest prime number less than $n^2$. Nov 6, 2015 at 20:41

The rank is at least $2$. Consider an arbitrary matrix $A=[a_{ij}]$ which $a_{ij}\in \{1,2,...,n^2\}$ are distinct. Since permuting rows or columns of a matrix does not change its rank, without last of generality, we can assume that $1= a_{11}\lt a_{21}\lt...\lt a_{n1}$ and $1= a_{11}\lt a_{12}\lt...\lt a_{1n}$. And $a_{1n}\ge n$, $a_{n1}\ge n$. Now, because of $a_{ij}$ are distinct, at least one of these inequalities is strict. Let: $$S=\begin{bmatrix} a_{11} & a_{1n} \\ a_{n1} & a_{nn} \\ \end{bmatrix}$$ Then: $det(S)\lt 1.n^2-n.n=0$. So, $det(S)\ne 0$. Now, $rank(A)\ge rank(S)=2$.