3
$\begingroup$

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.

$\endgroup$
0
1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.