Upper bound on the largest singular value of a stochastic matrix A stochastic matrix is a positive matrix whose columns sum to one. The largest eigenvalue of a stochastic matrix is one. But the largest singular value can exceed one. Are there any known bounds on this largest singular value? 
(Note, when the matrix is doubly stochastic---with both rows and columns summing to one---then the largest singular equals one.)
 A: We can get a quick upper bound as follows: let $\|x\|$ denote the norm (Euclidean length) of a vector, and denote
$$
\|(x_1,\dots,x_n)\|_\infty = \max_{i=1,\dots,n}|x_n|
$$
It is well known that 
$$
\max_{x \neq 0} \frac{\|Ax\|_\infty}{\|x\|_\infty} = \max_{i=1,\dots,n}\sum_{j=1}^n |a_{ij}| 
$$
Thus, for a stochastic matrix $A$, we have
$$
\sigma_1(A) = \max_{x \neq 0} \frac{\|Ax\|}{\|x\|} \leq \max_{x \neq 0} \frac{\sqrt{n} \|Ax\|_\infty}{\frac 1{\sqrt{n}}\|x\|_\infty} = n \max_{i=1,\dots,n}\sum_{j=1}^n |a_{ij}|  = n
$$
I'm not sure if this bound is tight.

We can see that it is possible to get a maximum singular value of at least $\sqrt{n}$.  In particular, it suffices to consider $A = \mathbf 1 e_1^T$
where $\mathbf 1$ is the column-vector of $1$s and $e_1$ is the standard basis vector $(1,0,\dots,0)^T$. 
A: The largest singular value $\sigma_1(A)$ is equal to its spectral norm $\|A\|_2$, and for any matrix  $A \in \mathbb{R} ^{n \times n}$, it is known  that $\|A\|_2\le\sqrt{n}\|A\|_\infty$ (see bottom of Wikipedia page for other examples of norm equivalences)
Now, for a stochastic matrix $A$, it is always the case by definition that actually $\|A\|_\infty = 1$, so that $\|A\|_2\le\sqrt{n}$.
Combining this fact with Omnomnomnom's construction, this upper bound cannot be generally improved.
