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

• If you down vote, at least indicate why. What do you find objectionable about the question? That way I can fix it. – Vladhagen Feb 14 '14 at 20:46

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.
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}}.$$
• @John The answer was obtained by observing that the third-order Newton difference of the sequence $0,1,4,9,16,\ldots$ is zero. – user1551 Feb 14 '14 at 20:54