# Is it true that $\|\text{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 $\text{diag($\pi$)}$ the $n \times n$ diagonal matrix with entries from $\pi$ on the diagonal and zeros elsewhere.

Is it true that $\|\text{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.$$