3
$\begingroup$

I have a stochastic matrix $A \in R^{n \times n}$ whose sum of the entries in each row is $1$. When I found out the eigenvalues and eigenvectors for this stochastic matrix, it always happens that one of the eigenvalues is $1$.

Is it true that for any square row- or right-stochastic matrix (i.e. each row sums up to $1$) one of the eigenvalues is $1$? If so, how do we prove it?

$\endgroup$
1
3
$\begingroup$

The column vector with every entry $1$ is an eigenvector with eigenvalue $1$ for your matrix. It is not necessarily true that the eigenvalue $1$ occurs with algebraic multiplicity $1$ as an eigenvalue for your matrix $A$. By the Frobenius Perron-Theorem, that is the case if the entries of $A$ (or even some power of $A$) are all positive. What is true is that $x-1$ is not a repeated factor of the minimum polynomial of $A$ (using the Frobenius Perron theorem on each block).

$\endgroup$
4
  • $\begingroup$ What do you mean by "algebraic multiplicity"? What does it even mean that an eigenvalue appears with "algebraic multiplicity" for a matrix? $\endgroup$
    – nbro
    May 17 '18 at 8:55
  • $\begingroup$ By saying that an eigenvalue $\lambda$ of a matrix $A$ has algebraic multiplicity $r$, I intend to mean that $(x-\lambda)^{r}$ divides the characteristic polynomial of $A$, but $(x-\lambda)^{r+1}$ does not. With this convention, it is the case that the dimension of the $\lambda$-eigenspace of $A$ is at most $r$ (but in general it can be strictly smaller than $r$). $\endgroup$ May 17 '18 at 9:11
  • $\begingroup$ But why do you say it in your answer? $\endgroup$
    – nbro
    May 17 '18 at 9:21
  • $\begingroup$ Just because it seemed to me worthwhile to note that not every eigenvector with eigennvalue 1 of the matrix in the question needs to be a multiple of the all 1's vector in general, which might be of interest to people who know about the Frobenius-Perron theorem. $\endgroup$ May 17 '18 at 9:44
0
$\begingroup$

That is a basic and important property of stochastic matrices. It's also non-obvious, unless you are aware of the Perron-Frobenius theorem.

$\endgroup$
4
  • 3
    $\begingroup$ What is non-obvious? The property the OP asks about (that 1 is an eigenvalue) IS obvious once one notices that AU=U for U the column vector of ones... :-) $\endgroup$
    – Did
    Aug 27 '11 at 17:00
  • $\begingroup$ I'm assuming, when he says that the rows sum one, that we are dealing with a "right stochastic matrix", and hence we are speaking of "left eigenvalues" en.wikipedia.org/wiki/Stochastic_matrix If we have a "left stochastic matrix" that additionally has the property of its rows summing one, then it's a double strochastic matrix ( a very particular case) and then you're right, it's obvious. $\endgroup$
    – leonbloy
    Aug 27 '11 at 17:48
  • 3
    $\begingroup$ No particular case. Since AU=U, 1 is an eigenvalue of A (for example in the sense that ker(A-I) is not {0}), hence det(I-A)=0, hence det(I-A^T)=0 (because det(M)=det(M^T) for every matrix M), hence 1 is an eigenvalue of A^T, hence there exists a nonzero vector V such that A^TV=V, hence V^TA=V^T. $\endgroup$
    – Did
    Aug 27 '11 at 18:01
  • $\begingroup$ I don't see any proof of this important property in your answer. So I downvoted. If you want me to retract my downvote, add a step-by-step proof to your answer. $\endgroup$
    – nbro
    May 17 '18 at 9:04

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.