Proof that the largest eigenvalue of a stochastic matrix is $1$

Here's a really elementary proof (which is a slight modification of Fanfan's answer to a question of mine). As Calle shows, it is easy to see that the eigenvalue $1$ is obtained. Now, suppose $Ax = \lambda x$ for some $\lambda > 1$. Since the rows of $A$ are nonnegative and sum to $1$, each element of vector $Ax$ is a convex combination of the components of $x$, which can be no greater than $x_{max}$, the largest component of $x$. On the other hand, at least one element of $\lambda x$ is greater than $x_{max}$, which proves that $\lambda > 1$ is impossible.

Say $A$ is a $n \times n$ row stochastic matrix. Now: $$A \begin{pmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{pmatrix} = \begin{pmatrix} \sum_{i=1}^n a_{1i} \\ \sum_{i=1}^n a_{2i} \\ \vdots \\ \sum_{i=1}^n a_{ni} \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{pmatrix} $$ Thus the eigenvalue $1$ is attained.

To show that the this is the largest eigenvalue you can use the Gershgorin circle theorem. Take row $k$ in $A$. The diagonal element will be $a_{kk}$ and the radius will be $\sum_{i\neq k} |a_{ki}| = \sum_{i \neq k} a_{ki}$ since all $a_{ki} \geq 0$. This will be a circle with its center in $a_{kk} \in [0,1]$, and a radius of $\sum_{i \neq k} a_{ki} = 1-a_{kk}$. So this circle will have $1$ on its perimeter. This is true for all Gershgorin circles for this matrix (since $k$ was taken arbitrarily). Thus, since all eigenvalues lie in the union of the Gershgorin circles, all eigenvalues $\lambda_i$ satisfy $|\lambda_i| \leq 1$.

If we can show that $A$ doesn't increase the 1-norm, i.e., $$\|Ax\|_1\leq\|x\|_1$$ Then $$\|Ax\|_1=\|\lambda x\|_1=|\lambda|\|x\|_1\leq\|x\|_1$$ which is $|\lambda|\leq 1$, we are done, but how to show above inequality? For convenience, let's set stochastic matrix $$A=\begin{pmatrix}a_{11}& a_{12}\\a_{21}& a_{22}\end{pmatrix}$$ Then \begin{eqnarray*}\|Ax\|_1&=&|a_{11}x_1+a_{12}x_2|+|a_{21}x_1+a_{22}x_2|\\&\leq& a_{11}|x_1|+a_{12}|x_2|+a_{21}|x_1|+a_{22}|x_2|\\&=&|x_1|+|x_2|\\&=&\|x\|_1\end{eqnarray*} For n-dimensional matrix, it can be shown in same manner.