3 edited tags
2 edited tags
1

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

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?