Skip to main content
3 of 3
edited to clarify that $\epsilon$ is to depend on $A$ only
Peter Dukes
  • 1.1k
  • 1
  • 8
  • 17

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}$.

Peter Dukes
  • 1.1k
  • 1
  • 8
  • 17