Do sub-stochastic matrices reduce the 1-norm of vectors?

Question

It is well-known that "stochastic matrices preserve the 1-norm of vectors, $||\mathbf{A}\vec{v}||_1=||\vec{v}||_1$". I am thus wondering whether sub-stochastic matrices (a square matrix $\mathbf{Q}$ with nonnegative entries so that every row adds up to at most 1) reduce instead the 1-norm of a vector, $||\mathbf{Q}\vec{v}||_1\leq ||\vec{v}||_1$...is there a proof of this, and under which conditions? This should be a well-known fact (or at least easy to disprove), but I have so far failed. Many thanks.

Answer 1

Suppose $Q \in \mathbb{R}^{n\times n}$ and $v\in\mathbb{R}^n$ have non-negative entries.

Observe, $$ Qv = \begin{bmatrix} Q_{1,1}v_1 + Q_{1,2}v_2 + \cdots Q_{1,n}v_n \\ Q_{2,1}v_1 + Q_{2,2}v_2 + \cdots Q_{2,n}v_n \\ \vdots \\ Q_{n,1}v_1 + Q_{n,2}v_2 + \cdots Q_{n,n}v_n \\ \end{bmatrix} $$

Then, using the assumption that $Q_{i,j} v_j \geq 0$, $$ \| Qv \|_1 = \sum_{i} \left| \sum_j Q_{i,j} v_j \right| = \sum_{i} \sum_j Q_{i,j} v_j = \sum_j \left[ v_j \sum_{i} Q_{i,j} \right] $$ Therefore, if the columns of $Q$ sum to 1, then $\| Q v \|_1 = \|v\|_1$.

If the columns of $Q$ sum to something less than 1 (what you're asking about), what does this tell you about how this new sum compares to the sum if the columns of $Q$ summed to 1?