1
$\begingroup$

Conjecture: Let $A$ be a $4 \times 4$ row-stochastic, primitive matrix. Let $p_{i}$ be four probabilities such that $p_1 + p_2 + p_3 + p_4 = 1$. Let \begin{align} V &= \text{diag}_i\{p_{i + 1} + p_{i + 3} - p_i \} \\ &= \text{diag}\{p_2 + p_4 - p_1, p_1 + p_3 - p_2, p_2 + p_4 - p_3, p_1 + p_3 - p_4\}. \end{align} Then, $$\rho(A + V) > \rho(A) = 1$$ where $\rho(X)$ denotes the spectral radius of matrix $X$.

Some notes:

  • $\rho(A) = 1$ follows directly from Perron-Frobenius.
  • $\text{Tr}(V) = 1$.
  • $\rho(A + V)$ is a convex function of $V$ (see Cohen 1981.)
  • If $p_{i + 1} + p_{i + 3} - p_i > 0$ for all $i$ then the conjecture is true since the derivative of the Perron root with respect to any element is positive (see Theorem 2 of Vahrenkamp 1976).
  • If $A$ is doubly-stochastic, the conjecture is true, in fact we have the stronger bound $\rho(A + V) > 1.25$. The proof is the same idea as Lemma 1 of Johnson 1994. I can't quite see how it would generalize to the row-stochastic case since the right-Perron eigenvector will be $\mathbf{1}$, but not necessarily the left-Perron eigenvector.

I have some numerical evidence to support the conjecture, but that's about it.

$\endgroup$
1
$\begingroup$

This is not true. Let $$ B=\pmatrix{1&0&0&0\\ 1&0&0&0\\ 1&0&0&0\\ 1&0&0&0\\ }, \ V=\pmatrix{2s-1\\ &1-2s\\ &&s\\ &&&1-s}, $$ where $V$ is generated from the probability vector $p=(1-s,\,s,0,0)$ where $0<s<\frac12$. Then $\rho(B+V)=\max\{2s,\,1-2s,\,s,\,1-s\}<1$. It follows that if $A$ is a positive (hence primitive) stochastic matrix that is close to $B$, then $\rho(A+V)<1$. A more concrete counterexample can be obtained by putting $A=(1,1,1,1)^T(0.97,\,0.01,\,0.01,\,0.01)$ and $s=0.1$. Numerically we have $\rho(A+V)=0.92865$.

$\endgroup$
1
  • $\begingroup$ Thanks. I thought I tried the "one big column" counter-example but apparently not. $\endgroup$
    – Mr. G
    May 28 '19 at 14:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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