# Eigenvalues of a special stochastic matrix

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.

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?

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.

• The OP's conjecture on the eigenvalues is indeed correct. – Rodrigo de Azevedo Dec 6 '19 at 22:42