<s>[INST] Prove a $n \times n $ matrix has rank 3 I have been examining a problem dealing with finding the rank of a  $n \times n $ matrix $M$ as follows:
\begin{bmatrix} 
0&1&4&9&16&\cdots &(n-1)^2\\
1&0&1&4&9&\cdots&(n-2)^2\\
4&1&0&1&4&\cdots&(n-3)^2\\
9&4&1&0&1&\cdots&(n-4)^2\\
16&9&4&1&0&\cdots&(n-5)^2\\
\vdots&\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\
(n-1)^2&(n-2)^2&\cdots&(n-4)^2&\cdots&\cdots&0
\end{bmatrix}
That is, the matrix with $k^2$ on its $k^{th}$ super and subdiagonals.
One of my colleagues claims the matrix is of rank 3. 
I have tried to factor this matrix somehow, but have not really gotten very far. 
Can we develop a proof of the claim that the rank of $M$ is indeed 3 (assume that $n\geq3$).
 [/INST] When $n\ge4$, let $P=\pmatrix{1&-1\\ &\ddots&\ddots\\ &&\ddots&-1\\ &&&1}^3
=\pmatrix{1&-3&3&-1\\
&\ddots&\ddots&\ddots&\ddots\\
&&\ddots&\ddots&\ddots&-1\\
&&&\ddots&\ddots&3\\
&&&&\ddots&-3\\
&&&&&1}$. Then $P^TMP=\pmatrix{0&1&1\\ 1&-6&1\\ 1&1&0}\oplus 0_{(n-3)\times(n-3)}$. Hence $M$ has rank 3.

Remark.
Knowing that $M$ has rank $3$ allows us to find the eigenvalues of $M$ relatively easily. One can readily verify that $(1-n,3-n,\ldots,n-3,n-1)^T$ is an eigenvector of $M$ corresponding to the eigenvalue $-\frac{n(n^2-1)}{6}$. Since $M$ has zero trace, if we also know $\operatorname{tr}(M^2)$, the other two nonzero eigenvalues can be found. It turns out that
$$
\operatorname{tr}(M^2)=2\sum_{i=1}^{n-1} i(n-i)^4
=\frac1{30}n^2(n^2-1)(2n^2-3)
$$
(see also OEIS A101089) and the other two nonzero eigenvalues of $M$ are
$$
\frac{n(n^2-1)}{12}\pm\frac{n}{2}\sqrt{\frac{(n^2-1)(3n^2-7)}{60}}.
$$
</s>