4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$
    – SBF
    Commented Sep 4, 2012 at 12:00
  • $\begingroup$ I mean spectral norm. $\endgroup$
    – hayu
    Commented Sep 4, 2012 at 12:18

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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