A question on Characteristic polynomial of complex $n\times n$ matrix

On one of linear algebra book i found the problem which need to determine the characteristic polynomial of the complex $n\times n$ matrix $$M=\begin{pmatrix} 0&1&1&\cdots &1\\ 1&0&1&\cdots &1\\ \vdots&\ddots &\ddots &\ddots &\vdots\\ 1&\cdots &1&0&1\\ 1&\cdots &1&1&0 \end{pmatrix}$$ I don't have any concept to find characteristic polynomial of such kind. Would you say something about it? Thank you.

• If you know the definition of characteristic polynomial, and you know about mathematical induction, that should get you started. You could also try doing a few small cases first. Another way to get there: it should be easy to find the eigenvalues. Feb 9, 2013 at 8:45

A possible approach is the following. Letting $I$ denote the $n \times n$ unit matrix, then $$M+I=\begin{pmatrix} 1&1&1&\cdots &1\\ 1&1&1&\cdots &1\\ \vdots&\ddots &\ddots &\ddots &\vdots\\ 1&\cdots &1&1&1\\ 1&\cdots &1&1&1 \end{pmatrix}.$$ Clearly the image of (the linear map associated to) this matrix is one-dimensional, so its kernel has dimension $n-1$, which means $n-1$ eigenvalues $0$. And the (row) vector $(1,1,\dots,1)$ is an eigenvector with respect to the eigenvalue $n$. So $M+I$ is similar to $$\begin{pmatrix} n&&&\cdots &\\ &0&&\cdots &\\ \vdots&\ddots &\ddots &\ddots &\vdots\\ &\cdots &&0&\\ &\cdots &&&0 \end{pmatrix}$$ (off-diagonal zeroes omitted), and $M = (M+I) - I$ is similar to $$\begin{pmatrix} n-1&&&\cdots &\\ &-1&&\cdots &\\ \vdots&\ddots &\ddots &\ddots &\vdots\\ &\cdots &&-1&\\ &\cdots &&&-1 \end{pmatrix},$$ which yields the characteristic polynomial $$(x - (n-1)) \cdot (x+1)^{n-1}.$$
• Self-comment: working out the cases $n=1, 2, 3$, as suggested by @GerryMyerson might have helped pointing in this direction. Feb 9, 2013 at 8:55
There are not many transformations of a matrix that have easily predicted effects both on matrix itself and on the characteristic polynomial (the main operation that leaves the characteristic polynomial invariant is any change of basis, i.e., conjugation by some invertible matrix, but even in the simplest cases this combines row and column operations so I wouldn't classify this as having an easily predicted effect on the matrix). However there is one such operation: adding a multiple $cI_n$ to the matrix shifts all roots of the characteristic polynomial up by $c$ by the very definition of the characteristic polynomial, in other words it substitutes $X-c$ for $X$. In this case doing this for $c=1$ is a good idea, because it gives the all-one matrix which I shall call $A_n$.
Since all columns of $A_n$ are equal, its rank is $1$, which imples that its kernel, which is the eigenspace for the eigenvalue $0$, has dimension $n-1$. The unique remaining eigenvalue must have as eigenspace the column space of $A_n$, and an immediate computation shown that the associated eigenvalue of $A_n$ is $n$. Therefore the characteristic polynomial of $A_n$ is $X^{n-1}(X-n)$. The charecteristic polynomial of $M$ is obtained from it by substituting $X+1$ for $X$, giving $$(X+1)^{n-1}(X+1-n).$$