Why a Product Has a Controlled Norm
When a matrix acts on a vector, its induced norm measures the largest factor by which it can increase the vector’s size. A product \(\mathbf{A}\mathbf{B}\) represents two actions in sequence: \(\mathbf{B}\) acts first, then \(\mathbf{A}\). The key question is whether the size increase from the combined action can be controlled using the size increases of the two actions separately. For induced matrix norms, it can: the norm of the product is at most the product of the norms.
We work over \(\mathbb{R}\). For each vector space \(\mathbb{R}^n\), choose a vector norm \(\|\cdot\|\), using a consistent choice whenever the same space occurs as the output of one matrix and the input of another. A vector norm assigns a nonnegative size to each vector, is zero only on \(\mathbf{0}\), satisfies \(\|c\mathbf{x}\|=|c|\|\mathbf{x}\|\), and satisfies the triangle inequality. For a matrix \(\mathbf{A}\in\mathbb{R}^{m\times n}\), the induced matrix norm is the largest ratio of output size to input size over nonzero inputs.
The definition gives a useful bound for every input, including the zero vector: \(\|\mathbf{A}\mathbf{x}\|\leq\|\mathbf{A}\|\|\mathbf{x}\|\). For nonzero \(\mathbf{x}\), this follows by multiplying the ratio in the definition by \(\|\mathbf{x}\|\); for \(\mathbf{x}=\mathbf{0}\), both sides are zero. This direct consequence of the definition is the step that controls a product.
The Submultiplicative Inequality
Proof. We must bound the norm of the composite action for every input \(\mathbf{x}\in\mathbb{R}^p\). If \(\mathbf{x}=\mathbf{0}\), then \(\mathbf{A}\mathbf{B}\mathbf{x}=\mathbf{0}\), so the desired vector bound holds. If \(\mathbf{x}\ne\mathbf{0}\), apply the defining bound first to \(\mathbf{A}\), with input \(\mathbf{B}\mathbf{x}\), and then to \(\mathbf{B}\), with input \(\mathbf{x}\). The matching norm on \(\mathbb{R}^n\) allows the middle quantity to be used in both bounds: $$ \|\mathbf{A}\mathbf{B}\mathbf{x}\| \leq\|\mathbf{A}\|\,\|\mathbf{B}\mathbf{x}\| \leq\|\mathbf{A}\|\,\|\mathbf{B}\|\,\|\mathbf{x}\|. $$ Divide by \(\|\mathbf{x}\|>0\). This shows that every ratio in the supremum defining \(\|\mathbf{A}\mathbf{B}\|\) is at most \(\|\mathbf{A}\|\|\mathbf{B}\|\). Taking the supremum over all nonzero \(\mathbf{x}\) proves the inequality. \(\square\)
The dimensions and the matching norm matter. The product \(\mathbf{A}\mathbf{B}\) is defined because the number of columns of \(\mathbf{A}\) equals the number of rows of \(\mathbf{B}\). The norm on the shared space \(\mathbb{R}^n\) must also agree: otherwise the intermediate size \(\|\mathbf{B}\mathbf{x}\|\) would not be the same quantity in the two applications of the definition. With the usual choice of one vector norm, such as the infinity norm, in every dimension, this compatibility is automatic.
The inequality is an upper bound, not a claim that the two sides are always equal. The largest amplification direction for \(\mathbf{B}\) need not be sent by \(\mathbf{B}\) into a direction that \(\mathbf{A}\) amplifies maximally. The examples below illustrate both equality and strict inequality.
A Convenient Formula for the Infinity Norm
For exact computations, one common choice is the vector infinity norm, defined by \(\|\mathbf{x}\|_{\infty}=\max_j|x_j|\). Its induced matrix norm is the largest absolute row sum. We establish that formula here so the examples can compute their norms directly from their entries.
Proof. First take any \(\mathbf{x}\in\mathbb{R}^n\). For each row \(i\), the triangle inequality and the definition of \(\|\mathbf{x}\|_\infty\) give $$ |(\mathbf{A}\mathbf{x})_i| =\left|\sum_{j=1}^{n}a_{ij}x_j\right| \leq\sum_{j=1}^{n}|a_{ij}|\,|x_j| \leq\left(\sum_{j=1}^{n}|a_{ij}|\right)\|\mathbf{x}\|_\infty. $$ Taking the maximum over the rows proves that \(\|\mathbf{A}\mathbf{x}\|_\infty\leq M\|\mathbf{x}\|_\infty\), where \(M=\max_i\sum_j|a_{ij}|\). Thus the induced norm is at most \(M\). If \(M=0\), every entry of \(\mathbf{A}\) is zero, so its induced norm is zero and the formula holds. If \(M>0\), choose a row \(k\) whose absolute row sum is \(M\). Set \(x_j=1\) when \(a_{kj}\geq0\) and \(x_j=-1\) when \(a_{kj}<0\). Then \(\|\mathbf{x}\|_\infty=1\) and $$ (\mathbf{A}\mathbf{x})_k=\sum_{j=1}^{n}|a_{kj}|=M. $$ Consequently \(\|\mathbf{A}\mathbf{x}\|_\infty\geq M\), so the induced norm is at least \(M\). The two bounds prove the formula. \(\square\)
Worked Calculations
Worked Example: A Strict Inequality
Use the infinity norm to calculate \(\|\mathbf{A}\|_\infty\), \(\|\mathbf{B}\|_\infty\), and \(\|\mathbf{A}\mathbf{B}\|_\infty\) for $$ \mathbf{A}=\begin{bmatrix}1&-2\\3&0\end{bmatrix}, \qquad \mathbf{B}=\begin{bmatrix}2&1\\-1&4\end{bmatrix}. $$
The absolute row sums of \(\mathbf{A}\) are \(|1|+|-2|=3\) and \(|3|+|0|=3\), so \(\|\mathbf{A}\|_\infty=3\). For \(\mathbf{B}\), the row sums are \(|2|+|1|=3\) and \(|-1|+|4|=5\), so \(\|\mathbf{B}\|_\infty=5\). Now multiply in the stated order: $$ \mathbf{A}\mathbf{B} = \begin{bmatrix} 1\cdot2+(-2)(-1)&1\cdot1+(-2)\cdot4\\ 3\cdot2+0(-1)&3\cdot1+0\cdot4 \end{bmatrix} = \begin{bmatrix}4&-7\\6&3\end{bmatrix}. $$ The product has absolute row sums \(|4|+|-7|=11\) and \(|6|+|3|=9\), hence \(\|\mathbf{A}\mathbf{B}\|_\infty=11\). The check is $$ 11\leq 3\cdot5=15. $$ The inequality is strict in this case.
Check by multiplication: The displayed product has entries \(4,-7,6,3\), obtained by the four row-by-column dot products above. This verifies the matrix whose norm was computed.
Worked Example: Equality Can Occur
Let $$ \mathbf{A}=\begin{bmatrix}2&0\\0&1\end{bmatrix}, \qquad \mathbf{B}=\begin{bmatrix}4&0\\0&3\end{bmatrix}. $$ The absolute row sums of \(\mathbf{A}\) are \(2\) and \(1\), so \(\|\mathbf{A}\|_\infty=2\). Those of \(\mathbf{B}\) are \(4\) and \(3\), so \(\|\mathbf{B}\|_\infty=4\). Multiplication gives $$ \mathbf{A}\mathbf{B} = \begin{bmatrix}2\cdot4&0\\0&1\cdot3\end{bmatrix} = \begin{bmatrix}8&0\\0&3\end{bmatrix}. $$ Its absolute row sums are \(8\) and \(3\), so \(\|\mathbf{A}\mathbf{B}\|_\infty=8\). Therefore $$ \|\mathbf{A}\mathbf{B}\|_\infty=8 =\|\mathbf{A}\|_\infty\|\mathbf{B}\|_\infty=2\cdot4. $$
Check by multiplication: The product is diagonal, with diagonal entries \(2\cdot4=8\) and \(1\cdot3=3\); the off-diagonal entries are zero. In this example, the coordinate amplified most by \(\mathbf{B}\) is also the coordinate amplified most by \(\mathbf{A}\), so the bound is attained.
Worked Example: A Product Can Be Zero
Consider $$ \mathbf{A}=\begin{bmatrix}1&-1\\1&-1\end{bmatrix}, \qquad \mathbf{B}=\begin{bmatrix}1&1\\1&1\end{bmatrix}. $$ Each row of each matrix has absolute row sum \(2\), so \(\|\mathbf{A}\|_\infty=2\) and \(\|\mathbf{B}\|_\infty=2\). Their product is $$ \mathbf{A}\mathbf{B} = \begin{bmatrix} 1\cdot1+(-1)\cdot1&1\cdot1+(-1)\cdot1\\ 1\cdot1+(-1)\cdot1&1\cdot1+(-1)\cdot1 \end{bmatrix} = \begin{bmatrix}0&0\\0&0\end{bmatrix}. $$ Thus \(\|\mathbf{A}\mathbf{B}\|_\infty=0\), while \(\|\mathbf{A}\|_\infty\|\mathbf{B}\|_\infty=4\), and the inequality reads \(0\leq4\).
Check by multiplication: Each entry is \(1-1=0\), so the product really is the zero matrix. Both factors have positive norm, but their actions cancel when composed.
Why the Induced Definition Matters
Submultiplicativity is useful whenever a matrix product represents a sequence of transformations. For square matrices, it also controls repeated products: applying the theorem repeatedly gives \(\|\mathbf{A}^k\|\leq\|\mathbf{A}\|^k\) for each positive integer \(k\). To see this, the case \(k=1\) is equality. If the inequality holds for \(k\), then $$ \|\mathbf{A}^{k+1}\|=\|\mathbf{A}^{k}\mathbf{A}\| \leq\|\mathbf{A}^{k}\|\,\|\mathbf{A}\| \leq\|\mathbf{A}\|^{k+1}. $$ This provides a bound for the size of a long composition using the norm of one factor, without requiring a fresh calculation of every product.
Common pitfall: using an unrelated entrywise size as though it were induced. For example, define the entrywise maximum of a matrix to be the largest absolute value of any entry. For $$ \mathbf{C}=\begin{bmatrix}1&1\\1&1\end{bmatrix}, $$ this entrywise maximum is \(1\). A tempting but incorrect calculation is to treat it as a submultiplicative norm and conclude that the entrywise maximum of \(\mathbf{C}^2\) is at most \(1\cdot1=1\). In fact, $$ \mathbf{C}^2= \begin{bmatrix} 1\cdot1+1\cdot1&1\cdot1+1\cdot1\\ 1\cdot1+1\cdot1&1\cdot1+1\cdot1 \end{bmatrix} = \begin{bmatrix}2&2\\2&2\end{bmatrix}, $$ whose entrywise maximum is \(2\), not at most \(1\). The correction is to use the induced infinity norm when applying the theorem: \(\|\mathbf{C}\|_\infty=2\), and \(\|\mathbf{C}^2\|_\infty=4\leq2\cdot2=4\). The proof depends on the definition as a maximum amplification of vectors; not every way of assigning a size to matrix entries has that property.
When applying submultiplicativity, check three things: the product is defined, the norms on the intermediate vector space match, and the matrix norms are induced by those vector norms. With those conditions in place, the proof is simply the defining amplification bound applied successively to the two matrices.
Check Your Understanding
Use the definition and the submultiplicative theorem to justify each conclusion.
- For \(\mathbf{A}\in\mathbb{R}^{2\times3}\) and \(\mathbf{B}\in\mathbb{R}^{3\times4}\), state the dimensions of \(\mathbf{A}\mathbf{B}\) and the matching norm required on the intermediate space.
- Compute the infinity norms of \(\begin{bmatrix}1&-3\\2&1\end{bmatrix}\) and \(\begin{bmatrix}2&0\\-1&4\end{bmatrix}\), then state the submultiplicative upper bound for their product.
- In the proof, why must the vector \(\mathbf{x}=\mathbf{0}\) be handled separately before dividing by \(\|\mathbf{x}\|\)?
- Give an example of matrices with positive infinity norms whose product is the zero matrix, and verify the product.
- Explain why the entrywise maximum calculation for \(\mathbf{C}^2\) does not contradict submultiplicativity of induced matrix norms.
