MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is there any bounds for the norm of sub-stochastic matrix? (But it's not doubly stochastic matrix, I mean only the row sum is less than 1, while the column sum may not.

share|cite|improve this question
Which norm are you interested in? If talking about the norm induced by the infinity norm over the state space ($\|x\| = \max\limits_{i}|x_i|$) then in general you can only say that for the sub-stochastic matrix $A$ you have $\|A\| := \sup\limits_{\|x\| =1}\|Ax\| \leq 1$. Further bounds depend on the structure of $A$. – Ilya Sep 4 '12 at 12:00
I mean spectral norm. – hayu Sep 4 '12 at 12:18
up vote 3 down vote accepted

A useful and easy to compute bound is given by the reasonably well-known relation (see e.g., this Wikipedia section) \begin{equation*} \|A\| \le \sqrt{\|A\|_\infty \|A\|_1} \end{equation*} between the spectral norm, and the induced $1$ and $\infty$ norms of an arbitrary matrix $A$.

Corollary: If $A$ is elementwise nonnegative and row-stochastic, then $\|A\| \le \sqrt{\|A\|_1}$.

Note For some refinements of the first inequality mentioned above, please refer to this paper by V. Nikiforov.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.