We have to find rank of matrix $A_{nxn}$, where $a_{i,j}=(i-j)^2$, $i,j = 1..n$.
So A, would look something like that:
$ \left( \begin{array}_
0 & 1 & 4 & 9 & … & (n-1)^2 \\
1 & 0 & 1 & 4 & … & (n-2)^2 \\
… &… &… & … & … & … \\
(n-1)^2 & (n-2)^2 & (n-3)^2 & (n-4)^2 & … & 0 \end{array} \right)$
I find my problem pretty similar to that one, and answers listed there definitely gave me a clue, but thing is, they provide there two ways of solving it. While I was able to implement the first one, I am interested in understanding the second.
First approach
$(i-j)^2=i^2 – 2ij + j^2$
We will show that all rows of matrix A could be represented as linear combination of rows $R_a$, $R_{ab}$ and $R_b$, where:
$R_a = (\begin{array}_ 1 & 4 & 9 & 16 & … & n^2\end{array} )$
$R_b = (\begin{array}_ 1 & 2 & 3 & 4 & … & n\end{array} )$
$R_{ab} = (\begin{array}_ 1 & 1 & 1 & 1 & … & 1\end{array} )$
Then $R_1$ (first row of matrix A); $R_1 = R_a -2R_{ab} + R_{b}$
$R_2 = R_a -4R_{ab} + 4R_{b}$ Hence:
$R_i = R_a -2iR_{ab} + i^2R_{b}$
This equation allows us to state that $rank(A) = 3$
Second approach
rank of sum ≤ sum of ranks.
$A = M+N+K$ where: $m_{ij}= i^2$, $n_{ij}= -2ij$, $k_{ij}= j^2$
It's obvious that M,N and K have rank 1.
So, $rank(A) \le 3$
And my problem is that I don't understand how to find a lower bound of rank(A) here.
Best Answer
To show that the rank is at least 3, you must find 3 linearly independent vectors in the range space.
Hint:
$$ \det \begin{pmatrix} 0 & 1 & 4 \\ 1 & 0 & 1 \\ 4 & 1 & 0 \\ \end{pmatrix} \neq 0 $$