Hello,

Given a row-stochastic matrix $M$ with singular values $\sigma_{1}\geq\ldots\geq\sigma_{n}$, I am looking for an upper bound on the expression: $\min_{\alpha}\parallel M- \frac{\alpha}{n}J_{n}\parallel_{2} $ where $J_{n}$ is the matrix with all ones.

It is not hard to see that if $M$ is doubly stochastic, the above expression is exactly $\sigma_{2}$ (as the singular vector of the largest singular values is the vector of all ones), for $\alpha =1$. Can you find a similar bound when $M$ is only row stochastic?

Thank you.

Edit: Suppose we take $a,b$ to be the left and right singular vectors corresponding to the largest singular value $\sigma_{1}$. Then, $\parallel M- \frac{\alpha}{n}J_{n}-\sigma_{1}ab^T+\sigma_{1}ab^T\parallel_{2}$ is smaller than $\sigma_{2}+\sigma_{1}\left(\sqrt{1-\frac{\left< a,e\right> ^{2}\left< b,e\right> ^{2}}{N^{2}}}\right)$ for $\alpha = \frac{\sigma_{1}\left< a,e\right> ^{2}\left< b,e\right>^{2}}{N^{2}}$. For a doubly stochastic matrix, this bound is tight (as the first singular vectors are $\frac{1}{\sqrt{N}}e$). What can we say, for example, of $\left< a,e\right> \left< b,e\right>$, when $\sigma_{1}$ is not 1, but very close to it?