7
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Mar 11, 2014 at 6:13

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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!) $\endgroup$ Mar 10, 2014 at 16:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.