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

137 Views Asked by At

$\| \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$?

1

There are 1 best solutions below

0
On BEST ANSWER

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