Here $\lvert \lvert P \rvert \rvert_\infty$ is the maximum absolute row sum of the matrix $P$, which is $1$ when $P$ is row stochastic. While the hypothesis in the title seems to hold when tested, I have not been able to improve on the trivial bound \begin{eqnarray*} \left| \left| (2Q-I)(2P-I)\right| \right|_\infty &\leq &\lvert \lvert 2Q - I \rvert \rvert_\infty \lvert \lvert 2P-I \rvert \rvert_\infty \\ &\leq & \left(2\lvert \lvert Q \rvert \rvert_\infty+\lvert \lvert I \rvert \rvert_\infty \right)\left(\lvert \lvert P \rvert \rvert_\infty+2\lvert \lvert I \rvert \rvert_\infty \right) \\ & = & 3 \cdot 3 =9, \end{eqnarray*} and anything better would be useful. The assumptions in the title imply that the matrix $(2Q-I)(2P-I)$ has rows summing to one and eigenvalues in $[-1,1]$.

The claim clearly holds for scalars. In two dimensions, define \begin{eqnarray} Q=\left( \begin{array}{cc} q_1 & 1- q_1 \\ 1-q_2 & q_2 \end{array} \right) \qquad P=\left( \begin{array}{cc} p_1 & 1- p_1 \\ 1-p_2 & p_2 \end{array} \right), \end{eqnarray} and since $Q$ is stochastic, it has the eigenvalue $1$. The other eigenvalue is $1-q_1-q_2$ because the trace equals the sum of the eigenvalues. Requiring the eigenvalues to be nonnegative then implies $q_1+q_2\geq 1$ and similarly for $P$.

The bound is achieved for $q_1=0$, $q_2=1$, $p_1=\frac{1}{2}$ $p_2=\frac{1}{2}$, as we have \begin{eqnarray} \left(2Q-I\right)\left(2P-I\right) &=& \left(\begin{array}{rr} -1 & 2 \\ 0 &1 \end{array} \right) \left(\begin{array}{rr} 0 & 1 \\ 1 & 0 \end{array}\right) =\left( \begin{array}{rr} 2 & -1 \\ 1 & 0 \end{array} \right), \end{eqnarray} where the maximum absolute row sum is 3. In the above we may also confirm that increasing $q_1$, $p_1$ or $p_2$ marginally reduces the $\infty$-norm, while reducing $p_1$ or $p_2$ increases the $\infty$-norm beyond 3 but violates the assumption that the eigenvalues of $P$ are nonnegative.

Any help is appreciated. The purpose of this is to bound the Jacobian of a particular map.

EDIT: A stronger hypothesis is $\lvert \lvert (2Q-I)(2P-I) \rvert \rvert_\infty\leq \max \left( \lvert \lvert (2Q-I) \rvert \rvert_\infty,\lvert \lvert (2P-I) \rvert \rvert_\infty \right)$


Your conjecture is false for every $n\ge2$. Let $Q=ee_1^T$ and $P=ee_n^T$, where $\{e_1,\ldots,e_n\}$ is the standard basis of $\mathbb R^n$ and $e=e_1+\cdots+e_n$ is the all-one vector. Then \begin{aligned} (2Q-I)(2P-I)&=(2ee_1^T-I)(2ee_n^T-I)\\ &=4ee_n^T-2ee_1^T-2ee_n^T+I\\ &=2ee_n^T-2ee_1^T+I. \end{aligned} Therefore $\|(2Q-I)(2P-I)\|_\infty=5>3=\|2Q-I\|_\infty=\|2P-I\|_\infty$.

  • $\begingroup$ Thank you for the counterexample. Do you think the 5 is an upper bound? Like I mentioned, any bound that's better than 9 would be very useful. It seems like your construction maximizes the norm. $\endgroup$ – Asco Sep 6 '19 at 16:41
  • $\begingroup$ @Asco I don't know. To be frank, I have no idea what a generic row stochastic matrix with nonnegative spectrum looks like. $\endgroup$ – user1551 Sep 6 '19 at 17:18

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.