Eigenvalues of a special stochastic matrix

Question

I'm trying to find an explicit formula of all the eigenvalues for the following $n$ by $n$ stochastic matrix (sum of each row/column is one):

\begin{bmatrix}0&\frac{1}{n-1}&\frac{1}{n-1}&\cdots&\frac{1}{n-1}\\ \frac{1}{n-1}&\frac{n-2}{n-1}&0&\cdots&0 \\ \frac{1}{n-1}&0&\frac{n-2}{n-1}&0&\cdots \\ \cdots&\cdots&\cdots&\cdots&\cdots \\ \frac{1}{n-1}&0&0&\cdots&\frac{n-2}{n-1} \\ \\ \end{bmatrix}

Since this is a stochastic matrix, it is clear that $1$ is an eigenvalue. After doing some numerical experiments, I believe there are only three distict eigenvalues of this special matrix: $1$, $\frac{-1}{n-1}$, and $\frac{n-2}{n-1}$(with multiplicity $n-2$). I want to show this conclusion formally, but I cannot really decompose the matrix into the sum of identity matrix and zero diagonal matrix, since the first element in the matrix is $0$.

Update: I just realize $e_2-e_i$ will always be an eigenvector with eigenvalue $\frac{n-2}{n-2}$. There are $n-2$ pairs of them so we are done.

Answer 1

The characteristic polynomial of this matrix seems rather straightforward to compute. If my calculations are correct, then we have $$p_A(x)=-x\Big(\frac{n-2}{n-1}-x\Big)^{n-1}-\frac{1}{(n-1)^2}\Big(\frac{n-2}{n-1}-x\Big)^{n-2}+\frac{x}{n-1}\Big(\frac{n-2}{n-1}-x\Big)^{n-3}$$ Can you calculate the eigenvalues from this?

Answer 2

Let

$$\mathrm M := \begin{bmatrix} 0 & \frac{1}{n-1} 1_{n-1}^\top\\ \frac{1}{n-1} 1_{n-1} & \frac{n-2}{n-1} \mathrm I_{n-1}\end{bmatrix}$$

whose characteristic polynomial is

$$\begin{aligned} \det \left( s \mathrm I_n - \mathrm M \right) &= \det \begin{bmatrix} s & -\frac{1}{n-1} 1_{n-1}^\top\\ -\frac{1}{n-1} 1_{n-1} & \left( s - \frac{n-2}{n-1} \right) \mathrm I_{n-1}\end{bmatrix}\\ & = \left( s - \frac{n-2}{n-1} \right)^{n-1} \cdot \left( s - \frac{1}{n-1} \left( s - \frac{n-2}{n-1} \right)^{-1} \right)\\ &= \left( s - \frac{n-2}{n-1} \right)^{n-2} \cdot \left( s \left( s - \frac{n-2}{n-1} \right) - \frac{1}{n-1} \right)\\ &= \left( s - \frac{n-2}{n-1} \right)^{n-2} \cdot \left( s^2 - \left(\frac{n-2}{n-1} \right) s - \frac{1}{n-1} \right)\\ &= \left( s - \frac{n-2}{n-1} \right)^{n-2} \cdot (s - 1) \cdot\left( s + \frac{1}{n-1} \right)\end{aligned}$$

where the Schur complement was used.