# Is it true that $\|\operatorname{diag}(\pi) P\|_2 \leq 1$ for $P$ stochastic and $\pi P = \pi$.

$$\| \cdot \|_2$$ is the matrix norm induced by $$L_2$$.

$$P$$ is any given real square $$n \times n$$ non-negative matrix with rows summing to one, i.e. $$P1 = 1$$, where $$1$$ is the vector of ones.

There is at least one such row vector $$\pi^\top \in \mathbb{R}^n$$ that $$\pi P = \pi$$, $$\|\pi^\top\|_1 = 1$$ and $$\pi \geq 0$$ (entry-wise). Let $$\pi$$ be any such vector.

Denote by $$\operatorname{diag}(\pi)$$ the $$n \times n$$ diagonal matrix with entries from $$\pi$$ on the diagonal and zeros elsewhere.

Is it true that $$\|\operatorname{diag}(\pi) P\|_2 \leq 1$$?

• No it is not true if you say nothing about $\|\pi\|$ because I can take $\pi' = 10000\pi$ and still it will hold condition $\pi' P = \pi'$. – Jihad Oct 29 '14 at 15:16
• You do realize that $\pi*P$ has absolutely no meaning if $\pi$ is a vector and P a matrix? As for this vector, $\pi$ is the one with 1 for each coordinate, and if you want to have its norm equal to one, you divide it by the size of your matrix – mvggz Oct 29 '14 at 15:18
• I have edited the question to clarify. – ziutek Oct 29 '14 at 15:20
• @mvggz I don't understand what you mean by saying a vector-matrix multiplication has no meaning. Also note that my question asks about the general case, not just when $\pi$ is uniform. – ziutek Oct 29 '14 at 15:24
• I'll rephrase my comment: I was under the impression that P was a square matrix, of finite size (n here) and $\pi$ a vector of $R^n$. That last point was edited by you since it's ${\pi}^T$ that is a vector of $R^n$, so you can forget about it. But you did write before the quantity $\pi*P$ while $\pi$ was still considered a vector of $R^n$, and this is not possible because it doesn't have any sense, it's $P*\pi$ that had one because this means " I evaluate the tranformation associated to P at the vector $\pi$". The other is just wrong. Do you see what I mean? – mvggz Oct 29 '14 at 15:39

I guess that this could be shown by using the inequality $\|A\|_2\leq\sqrt{\|A\|_1\|A\|_{\infty}}$ and in a more general fashion. Let $A$ be such that $\|A\|_1\leq 1$, $b$ be a vector of unit 1-norm, and let $B:=\mathrm{diag}(b)$. We have $$\|BA\|_2^2\leq\|BA\|_1\|BA\|_{\infty}.$$
Since the absolute row-sums of $A$ are bounded from above by one and the components of $b=(\beta_i)$ satisfy $|\beta_i|\leq 1$ (because $\|b\|_1=1$), the absolute row-sums of $BA$ are bounded by one as well. Hence $\|BA\|_{\infty}\leq 1$.
The $j$th column of $BA$ is $c_j:=[\beta_1 a_{1j},\ldots,\beta_n a_{nj}]^T$. Therefore, $$\|c_j\|_1=\sum_{i=1}^n|\beta_i a_{ij}|\leq\max_{1\leq i\leq n}|a_{ij}|\|b\|_1.$$ From $\|A\|_1\leq 1$, we have $|a_{ij}| \leq 1$ for all $i$ and $j$ and since $\|b\|_1=1$, $\|c_j\|_1\leq 1$. Hence $$\|BA\|_1=\max_{1\leq j\leq n}\|c_j\|_1\leq 1.$$
Putting this together gives $$\|BA\|_2\leq 1.$$