linear algebra - Characteristic polynomial problem

$$\begin{pmatrix} 1 & \cdots & n \\ n+1 & \cdots & 2n \\ \vdots & \ddots & \vdots \\ n^2-n+1 & \cdots & n^2 \end{pmatrix} .$$

I am trying to find characteristic polynomial of this $n\times n$ matrix but failed. At first, by taking elementray operations (Substract $k$-th row from $k+1$-th row.), the matrix can be transformed as:
$$\begin{pmatrix} 1 & \cdots& n \\ n & \cdots & n \\ \vdots & \ddots & \vdots \\ n & \cdots & n \end{pmatrix}.$$

And taking same elementary operations give:
$$\begin{pmatrix} 1 & \cdots & n \\ n & \cdots & n \\ 0 & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & 0 \end{pmatrix}.$$

Now it is enough to calculate the characteristic polynomial of this matrix but it seems cumbersome. Can anyone help me?
Hint says: First prove that $A$ has rank 2 and that $\operatorname{span}(\{(1,1,\cdots,1),(1,2,\cdots,n)\})$ is $L_A$-invariant.

Answer

The row operations you've done are enough to deduce that your matrix has rank $2$. Note that your row-reduced matrix will not have the same eigenvalues (even though it has the same rank), so it's not enough to simply find the characteristic polynomial of that last matrix.

In terms of eigenvalues, you now know that since the matrix has rank 2, the nullity of the matrix has dimension $n-2$, which is to say that $0$ is an eigenvalue with multiplicity $n-2$. It suffices now to find the remaining two eigenvalues.

The hint about the invariant subspace tells you that two eigenvectors will be within that $L_A$ invariant subspace, and presumably those eigenvectors correspond to the non-zero eigenvalues we're looking for.

The best way for you to use this information is to find the matrix of the restriction of $L_A$ to the invariant subspace described, then find the eigenvalues of that $2\times 2$ matrix. With those two eigenvalues, you'll now have all $n$ roots of the characteristic polynomial.

---

In particular, let $v_1 = (1,1,\dots,1)$, and $v_2 = (1,2,\dots,n)$, so that $\mathcal B = \{v_1,v_2\}$ is a basis for the invariant subspace discussed. We then see that the $i$th column of $A$ is given by $(i-n)v_1 + nv_2$. With that, we have
$$Av_1 = \sum_{i=1}^n ((i-n)v_1 + nv_2) = -\frac{n(n-1)}{2} v_1 + n^2 v_2\\ Av_2 = \sum_{i=1}^n i((i-n)v_1 + nv_2) = -\frac{(n-1)n(n+1)}{6} v_1 + \frac{n^2(n+1)}2$$
Thus, we have
$$[L_A]_{\mathcal B} = n\pmatrix{-(n-1)/2 & n\\(n-1)(n+1)/6 & n(n+1)/2}$$
We compute the characteristic polynomial of this matrix to be

$$\lambda^2 - \frac n2 \left(n^2 + 1\right)\lambda - \frac{5n^3}{12}(n^2 - 1)$$
It follows that the characteristic polynomial of the original matrix should be
$$\lambda^n - \frac n2 \left(n^2 + 1\right)\lambda^{n-1} - \frac{5n^3}{12}(n^2 - 1)\lambda^{n-2}$$