Spectra of matrices $A$ and $A^\top A$ For a square matrix $A$, I see that $\lambda$ is an eigenvalue of $A$ then $\lambda^2$ is an eigenvalue of $A^2$ since $A x = \lambda x \Rightarrow A^2 x = A(\lambda x) =\lambda^2 x$. But for a non-symmetric $A$, can we say anything about the spectrum of $A^\top A$ relating to the spectrum of $A$? For example, if $\lambda_{\max}$ is the maximum eigenvalue of $A$, will the spectrum of $A^\top A$ be bounded by $\lambda_{\max}^2$ somehow (and vice versa)? I ask this because of a remark (page 4, footnote 3) in this paper.
In the footnote, it claims that the eigenvalues of $(W-\frac{1}{n} {\bf 1} {\bf 1}^\top)$ are less than 1 since the eigenvalues of $(W W^\top - \frac{1}{n} {\bf 1}{\bf 1}^\top)=(W-\frac{1}{n} {\bf 1} {\bf 1}^\top)(W-\frac{1}{n} {\bf 1} {\bf 1}^\top)^\top$ are less than 1. Their claim seems to be correct, but I don't see the rationale of that.
 A: This is a bit complicated. You have misunderstood the authors' intent. Meanwhile, the authors have overlooked the fact that $W$ is symmetric. Although one can simply consider $W-\frac1n\mathbf1\mathbf1^T$, the authors had opted to consider $(W-\frac1n\mathbf1\mathbf1^T)(W-\frac1n\mathbf1\mathbf1^T)^\top$ unnecessarily.
First, you wrote

In the footnote, it claims that the eigenvalues of $(W-\frac{1}{n} {\bf 1} {\bf 1}^\top)$ are less than 1 since the eigenvalues of $(W W^\top - \frac{1}{n} {\bf 1}{\bf 1}^\top)=(W-\frac{1}{n} {\bf 1} {\bf 1}^\top)(W-\frac{1}{n} {\bf 1} {\bf 1}^\top)^\top$ are less than 1.

That wasn't what the authors meant. What they wanted to prove is not that the eigenvalues of $A=W-\frac{1}{n}\mathbf1\mathbf1^\top$ are less than $1$ in size, but that the spectral norm of $A$ is less than $1$. In other words, they wanted to prove that the eigenvalues of $AA^\top$ are strictly less than $1$.
However, by definition (see sec. II A on p.3), the doubly stochastic matrix $W\in\mathbb R^{n\times n}$ in the paper is a weight matrix of an undirected connected graph $E$ such that $w_{ii}>0$ for each $i$. Hence it is necessarily symmetric and irreducible. The eigenvalues of $AA^\top$ are just the squares of the eigenvalues of $A$. So, it does suffice to prove that the eigenvalues of $A$ are less than $1$ in sizes. Although you have misunderstood the authors' intent, your (mis)interpretation of their strategy also works.
At any rate, since $W$ is a symmetric irreducible doubly stochastic matrix with a positive diagonal, so is $WW^\top$. (In general, $WW^T$ is not necessarily irreducible, even if $W$ is primitive, but in our case, $W$ is an irreducible matrix with a positive diagonal. Therefore $WW^T$ is primitive and hence irreducible.) We want to show that all eigenvalues of $S-\frac1n\mathbf1\mathbf1^\top$ are less than $1$ in sizes when $S=WW^\top$ (the authors' intent) or when $S=W$ (your interpretation).
Since $S$ is irreducible and doubly stochastic, by Perron-Frobenius theorem, $1$ is a simple eigenvalue of $S$ and the moduli of all other eigenvalues of $S$ are strictly less than $1$. Thus we can arrange the eigenvalues of $S$ as $\lambda_1(\,=1)>\lambda_2\ge\cdots\ge\lambda_n\,(>-1)$. Since $S$ is also symmetric, we can pick an orthogonal eigenbasis $\{v_1=\mathbf1,v_2,\ldots,v_n\}$ with $Sv_i=\lambda_iv_i$. Then $\mathbf1^\top v_j=v_i^\top v_j=0$ when $j\ge2$ and
\begin{cases}
(S-\frac1n\mathbf1\mathbf1^\top)v_1=S\mathbf1-\mathbf1=0,\\
(S-\frac1n\mathbf1\mathbf1^\top)v_j=Sv_j=\lambda_jv_j\text{ when } j\ge2.
\end{cases}
Hence the eigenvalues of $S-\frac1n\mathbf1\mathbf1^\top$ are $0,\lambda_2,\ldots,\lambda_n$, which are strictly less than $1$ in moduli.
A: Yes, thanks for the reply. I see my problem now. I have mistaken the definition of spectral norm of a matrix as the maximum eigenvalue, but it is the maximum singular value instead. So everything works perfectly. Btw, I don't think $W$ needs to be symmetric though. But it needs to be doubly stochastic and irreducible.
Since a product of stochastic matrices is stochastic, we have $W^n$ to be stochastic for any $n$. So its eigenvalue is bounded by 1 (otherwise, we have $\lim_{n\rightarrow \infty} W^n x = \lambda^n x$, where elements on the LHS are bounded and that on the RHS can be unbounded and this leads to a contradiction). And the eigenvector with eigenvalue 1 exists, as it is just the all-one vector $\bf 1$.
Now, since $W W^\top$ is also stochastic, it also has maximum eigenvalue of 1. Moreover, since $W$ is doubly stochastic, we have $W W^\top {\bf 1} = W ({\bf 1}^ \top W)^\top= W {\bf 1}= 1 \cdot {\bf 1}$. So the eigenvector of $W W^\top$ with eigenvalue 1 is also $\bf 1$. Since we also assume $W$ to be irreducible,

(Update: the irreducibility of $WW^\top$ is not guaranteed even if $W$ is irreducible as many here have kindly pointed out. So I guess we have to assume $W W^\top$ to be irreducible here.)

by Perron-Frobenius Theorem, the eigenvector with the maximum eigenvalue is distinct. Therefore, we have $W W^\top - 1 \frac{{\bf 1}}{\sqrt{n}} \frac{{\bf 1}^\top}{\sqrt{n}}=W W^\top -\frac{{\bf 1 1}^\top}{n}$ (with the largest component removed) having the its eigenvalues less than 1.
And as $\underset{A}{\underbrace{(W-\frac{{\bf 1 1}^\top}{n})}}(W-\frac{{\bf 1 1}^\top}{n})^\top =W W^\top -\frac{{\bf 1 1}^\top}{n}$, the maximum singular value of $A$ has to be less than 1 since the set of singular value of $A$ is equal to the set the square rooted eigenvalues of $A A^\top$.
