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?



A random walk matrix has eigenvalue 1 with multiplicty 1 - why?
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. 


