Is there any bounds for the norm of substochastic matrix? (But it's not doubly stochastic matrix, I mean only the row sum is less than 1, while the column sum may not.
$\begingroup$
$\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 substochastic matrix $A$ you have $\A\ := \sup\limits_{\x\ =1}\Ax\ \leq 1$. Further bounds depend on the structure of $A$. $\endgroup$– SBFCommented Sep 4, 2012 at 12:00

$\begingroup$ I mean spectral norm. $\endgroup$– hayuCommented Sep 4, 2012 at 12:18
Add a comment

1 Answer
$\begingroup$
$\endgroup$
A useful and easy to compute bound is given by the reasonably wellknown 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 rowstochastic, then $\A\ \le \sqrt{\A\_1}$.
Note For some refinements of the first inequality mentioned above, please refer to this paper by V. Nikiforov.