# The minimal norm of a shifted stochastic matrix

Given a row-stochastic matrix $M$ with singular values $\sigma_{1} \geq \cdots \geq \sigma_{n}$, I am looking for an upper bound on the expression

$$\min_{\alpha} \left\| M- \frac{\alpha}{n}J_{n} \right\|_{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,

$$\| M- \frac{\alpha}{n}J_{n}-\sigma_{1}ab^T+\sigma_{1}ab^T \|_{2} < \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?

• A minor observation, $\alpha=1$ is the minimizer for the Frobenius norm; you are probably looking at the operator norm. – Suvrit Mar 22 '13 at 19:33
• Indeed, I am looking for the l2 norm. Thanks. – Daniel86 Mar 22 '13 at 19:57

Some experimentation led me to the following results:

1. $\alpha=1$ yields the minimum value even for the operator-2 norm (certainly provable directly too)
2. $\|M-ee^T/n\|_2$ can be larger than $\sigma_2 + \cdots + \sigma_n$
3. $\|M-2ee^T/n\|_2 = \sigma_1(M)$ (obviously, since $M$ is rs)

So the only reasonable bound is: $\|M-ee^T/n\|_2 \le c_n\sigma_1(M)$, where the constant $c_n$ depends on the dimensionality $n$. As of now, I am using $c_n=1$, but have not paid much thought to what the best constant would be (need to dig up some singular value inequalities for that).

Here is an example matrix for which $\|M-ee^T/n\|_2 \ge 0.9\sigma_1(M)$.

\begin{equation*} M = \frac{1}{1000}\begin{pmatrix} 10 & 24 & 966\\\\ 410 & 576 & 14\\\\ 529 & 362 & 109 \end{pmatrix}. \end{equation*}

• Thank you for your insights. I also figured that $\alpha = 1$ yields the minimum value also for the spectral norm. However, can you think of a matrix with a large gap between $\sigma_{1}$ and $\sigma_{2}$ (let's say, depends on $n$) for which this expression is as large as a factor of $\sigma_{1}$? I have some (maybe wrong) intuition that it decreases with the second singular values (maybe depends on $n$). – Daniel86 Mar 24 '13 at 20:57
• Try the Pascal matrix (for which the bounds should be derivable, or at least estimable analytically) --- (this matrix can be generated in Matlab using the command 'pascal'); for this matrix, it seems that $\|M-ee^T/n\|_2 > 0.5\sigma_1$, and that the gap between $\sigma_1$ and $\sigma_2$ is fairly large (of course, I scaled the matrix to be row-stochastic before testing the above claims) – Suvrit Mar 25 '13 at 1:47
• @S. Sra , your comments lead me to think that it depends on how close $\sigma_{1}$ is to 1, see my edit above. What do you think? – Daniel86 Apr 1 '13 at 11:32