# Let $Q,P$ be square row stochastic matrices with nonnegative real eigenvalues. Is $|| (2Q-I)(2P-I)||_\infty \leq 3$?

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