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

  • $\begingroup$ 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'$. $\endgroup$ – Jihad Oct 29 '14 at 15:16
  • $\begingroup$ 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 $\endgroup$ – mvggz Oct 29 '14 at 15:18
  • $\begingroup$ I have edited the question to clarify. $\endgroup$ – ziutek Oct 29 '14 at 15:20
  • $\begingroup$ @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. $\endgroup$ – ziutek Oct 29 '14 at 15:24
  • $\begingroup$ 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? $\endgroup$ – 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. $$

| cite | improve this answer | |

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.