# How much can I perturb a symmetric stochastic matrix and keep positive solutions?

Suppose $A$ is a symmetric stochastic $n \times n$ matrix with least eigenvalue $\lambda_n>0$. Consider real symmetric perturbations $\widehat{A}$.

How large can I take $\epsilon$ such that $\widehat{A}$ is invertible with $\widehat{A}^{-1} \mathbf{1} > \mathbf{0}$ for all $\widehat{A}$ with $||A-\widehat{A}||_\infty< \epsilon$? For sure we have $\epsilon \le \lambda_n$ just for the inverse to exist.

I expect the answer depends on $\kappa:=||A^{-1}||_\infty$. I have a preliminary bound $\epsilon \ge 1/2\kappa$, but my proof is elementary and ridiculous... it uses a series expansion. I don't think this lower bound on $\epsilon$ is best possible. Can Perron-Frobenius do better somehow?

PS: As an added challenge, I wonder if one gets a bigger $\epsilon$ with an assumption on the sign pattern of either $A^{-1}$ or $A-\widehat{A}$.

• I now have a more direct argument for $\epsilon \ge 1/2\kappa$. Neither proof uses that $A-\widehat{A}$ is symmetric. Dropping this assumption probably means $1/2\kappa$ is (close to) the truth. Mar 11, 2014 at 6:13

It depends on what you mean by real symmetric perturbation. Let me assume that $A$ is a symmetric stochastic $n\times n$ matrix with first eigenvalue $\lambda=1$ of multiplicity $1.$ Define $\hat{A}_{S,\epsilon}=A+\epsilon S,$ where $S$ is a real symmetric $n\times n$ matrix and $\epsilon>0.$ Then it is easy to obtain an unbounded example. Indeed take $A=\begin{pmatrix} 1/2&1/2&0\\1/2&1/4&1/4\\0& 1/4 &3/4 \end{pmatrix}$ and $S=\begin{pmatrix} 1&1&0\\1&0&0\\0& 0 &1 \end{pmatrix}.$ Consider $\hat{A}_{S,\epsilon}=A+\epsilon S.$ You can prove in this case that $\hat{A}_{S,\epsilon}$ is invertible and $\hat{A}^{-1}_{S,\epsilon}1>0$ for $\epsilon>0.$
Therefore the answer is: $\epsilon$ can be unbounded under no extra hypotheses.
• Sorry. My "whenever" was an unclear way of quantifying over all such perturbations. I realize I discussed $\widehat{A}$ before $\epsilon$, but I meant for $\epsilon$ to depend on $A$ only. So in particular $\epsilon \le \lambda_n$. I'll adjust my question. (Still, your answer is helpful... thanks!) Mar 10, 2014 at 16:20