1
$\begingroup$

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.

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

1 Answer 1

0
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .