Eigenvalue of sum of two specific matrices

Question

Suppose M is a stochastic matrix. Let $\lambda$<1 be an eigenvalue of M. Is it always true that $\lambda$ is also an eigenvalue of $(M-A)$, where $A$ is a matrix full of ones?

Answer 1

Yes, it's true. Suppose $M$ is any complex square matrix whose eigenvalues are $\lambda_1,\lambda_2,\ldots,\lambda_n$. Suppose also that $u$ is a unit eigenvector of $M$ corresponding to the eigenvalue $\lambda_1$ (so that $Mu=\lambda_1u$). By Schur triangulation, we may write $M=URU^\ast$ where $R$ is an upper triangular matrix whose first diagonal element is $\lambda_1$ and $U$ is a unitary matrix whose first column is $u$. Then $Ue_1=u$, where $e_1=(1,0,\ldots,0)^\top$. It follows that for any vector $v\in\mathbb C^n$, $$ M-uv^\ast = U(R-e_1v^\ast U)U^\ast. $$ $R-e_1v^\ast U$ is upper triangular. Its eigenvalues are its diagonal entries. Hence the eigenvalues of $M-uv^\ast$ are $\lambda_1-v^\ast Ue_1\,=\lambda_1-v^\ast u$ and $\lambda_2,\ldots,\lambda_n$.

In your case, we simply have $\lambda_1=1,\,u=\frac{1}{\sqrt{n}}(1,1,\ldots,1)^\top$ and $v=nu$.