Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.