A random walk matrix has eigenvalue 1 with multiplicty 1 - why?

Question

A random walk matrix has largest eigenvalue 1 with multiplicty 1 - why?

Let $G$ be a non-directed, regular connected graph with degree $d$. Let $A$ be its random walk matrix, i.e. it's adjacency matrix, with each entry divided by $d$.

i) It is easy to observe that $A$ is symmetric, hence normal, that it has real eigenvalues only and can be diagonalized by a pair of orthogonal matrices (at least if don't mix up something from my past course in linear algebra)

ii) Second, one can observe that the all-one vector scaled by $1/n$ is an eigenvector of $A$ for the eigenvalue $1$

iii) Furthermore, by observing that for any natural $k$, $A^k$ is doubly-stochastic, too, and applying Gelfands formula with $l^1$-norm, we can see that the spectral norm is $1$

It remains to show that $1$ has multiplicity $1$. After hours I couldn't manage to figure this out, although it seems rather simple at first sight. So probably I simply don't know the 'trick', which yields this result.

Can somebody help me?

Answer 1

Here is a simple proof.

Suppose $Ax = x$. Consider the entry of $x$ with the largest absolute value; lets use $x_k$ to denote this entry (e.g. if $x=[1,2,-4,3]^T$, then $k=3, x_k=-4$). Consider the $k$'th row of the equation $Ax=x$; it's telling you that $x_k$ is a convex combination of the $x_i$'s of its neighbors $i$ in the graph $G$. This immediately implies that $x_k=x_i$ for all neighbors $i$ of $k$ in $G$.

Now you iterate this argument and apply it to each neighbor $i$ of $k$. Using connectivity of $G$, eventually you get the conclusion that every entry of $x$ equals $x_k$. Thus the only solutions to $Ax=x$ are multiples of the all ones vector.

Observe that some of the conditions you imposed were not used: the above proof did not use the fact that $A$ is symmetric or that the graph is regular.

Answer 2

For large enough n, the matrix B = A + A² + ... + Aⁿ has positive entries since there's a path of length at most n connecting any two vertices. Thus by the Perron-Frobenius theorem B has a unique maximal eigenvalue and its multiplicity is 1.

Any eigenvector of A with eigenvalue λ is an eigenvector of B with eigenvalue f(λ)=λ+λ²+...+λⁿ, and f(λ) is maximized on [-1,1] at λ=1, so if there were two independent eigenvectors of A with λ=1 then B would have two independent eigenvectors achieving the maximal eigenvalue f(1) and this is a contradiction.

Answer 3

Another look at this: an eigenvector with eigenvalue of 1 is just an harmonic function (it's value is the average over neighbors' value). By the maximum principle (the maximum of harmonic function must be on the boundary of the set), it must be constant. Thus the eigenspace is of dimension 1.

Answer 4

I'm pretty sure if you calculate the $\ell_2$ norm of $Av$ (where $A$ is the transition matrix) you find quite easily that it is less than $\|v\|$ with equality if and only if $v$ is a constant vector.

Answer 5

Markov Chain theory shows that such a walk has a unique stationary distribution, yielding the answer to your question/