Bounding a Matrix-Vector Product
When a matrix acts on a vector, the entries of the output can combine contributions from many entries of the input. An induced matrix norm gives a way to control the size of that output using two quantities: the size of the matrix and the size of the input vector. The central estimate is simple, but its usefulness depends on matching the matrix norm to the vector norm being used.
We work over \(\mathbb{R}\). For \(\mathbf{x}=(x_1,\dots,x_n)^{\top}\in\mathbb{R}^n\), the vector 1-norm and infinity norm are
For an \(m\times n\) matrix \(\mathbf{A}\), the induced matrix norm uses the chosen vector norm on both the input in \(\mathbb{R}^n\) and the output in \(\mathbb{R}^m\). Thus a 1-norm bound compares 1-norms, and an infinity-norm bound compares infinity norms.
The norm on the output and the norm on the input in this definition are the same chosen norm, applied in their respective spaces. The matrix dimensions need not be square. For the 1-norm, the induced matrix norm is the largest absolute column sum; for the infinity norm, it is the largest absolute row sum. These formulas make the bounds practical to calculate.
The Induced Norm Inequality
Proof. If \(\mathbf{x}=\mathbf{0}\), then \(\mathbf{A}\mathbf{x}=\mathbf{0}\), so both sides of the inequality are zero. If \(\mathbf{x}\ne\mathbf{0}\), the quotient \(\|\mathbf{A}\mathbf{x}\|/\|\mathbf{x}\|\) is one of the values over which the supremum defining \(\|\mathbf{A}\|\) is taken. Hence \(\|\mathbf{A}\mathbf{x}\|/\|\mathbf{x}\|\le\|\mathbf{A}\|\). Multiplying by \(\|\mathbf{x}\|>0\) proves the stated inequality. Moreover, if a constant \(C\) satisfies \(\|\mathbf{A}\mathbf{x}\|\le C\|\mathbf{x}\|\) for all \(\mathbf{x}\ne\mathbf{0}\), division by \(\|\mathbf{x}\|\) gives every quotient in the supremum at most \(C\), so \(\|\mathbf{A}\|\le C\). This proves the least-constant claim in the definition as well. \(\square\)
For example, writing \(\|\mathbf{A}\|_1\) means the matrix norm induced by the vector 1-norm. It gives \(\|\mathbf{A}\mathbf{x}\|_1\le\|\mathbf{A}\|_1\|\mathbf{x}\|_1\), not an inequality with arbitrary, independently chosen norms on the two vectors.
Computing the 1-Norm and Infinity Norm of a Matrix
Proof. First consider the 1-norm. For any \(\mathbf{x}\in\mathbb{R}^n\), the triangle inequality gives \(\|\mathbf{A}\mathbf{x}\|_1=\sum_{i=1}^m|\sum_{j=1}^n a_{ij}x_j|\le\sum_{i=1}^m\sum_{j=1}^n|a_{ij}||x_j|\). Rearranging the finite sums and bounding each column sum by its maximum gives \(\|\mathbf{A}\mathbf{x}\|_1\le(\max_j\sum_i|a_{ij}|)\sum_j|x_j|\). Thus the induced norm is no larger than the largest absolute column sum. Choose a column index \(k\) attaining that maximum and let \(\mathbf{x}=\mathbf{e}_k\), the vector with entry \(1\) in position \(k\) and \(0\) elsewhere. Then \(\|\mathbf{x}\|_1=1\), and \(\mathbf{A}\mathbf{e}_k\) is column \(k\) of \(\mathbf{A}\), so \(\|\mathbf{A}\mathbf{e}_k\|_1=\sum_i|a_{ik}|\). The induced norm is therefore at least that maximum, proving the 1-norm formula.
For the infinity norm, for each row \(i\) and every \(\mathbf{x}\), \(|\sum_j a_{ij}x_j|\le\sum_j|a_{ij}||x_j|\le(\sum_j|a_{ij}|)\|\mathbf{x}\|_{\infty}\). Taking the maximum over the rows proves that \(\|\mathbf{A}\mathbf{x}\|_{\infty}\le(\max_i\sum_j|a_{ij}|)\|\mathbf{x}\|_{\infty}\). Now choose a row \(k\) with largest absolute row sum. Set \(x_j=1\) if \(a_{kj}\ge0\), and \(x_j=-1\) if \(a_{kj}<0\). Then \(\|\mathbf{x}\|_{\infty}=1\), and \(\sum_j a_{kj}x_j=\sum_j|a_{kj}|\). The \(k\)th entry of \(\mathbf{A}\mathbf{x}\) therefore has absolute value equal to the largest absolute row sum. This gives the reverse inequality for the induced norm and proves the infinity-norm formula. \(\square\)
The formulas offer a direct comparison: the 1-norm measures the largest total absolute contribution in a column, while the infinity norm measures the largest total absolute contribution in a row. In each case the result is a bound that works for every input vector in the corresponding norm.
Comparing Bounds on Examples
Worked Example: Two Bounds for the Same Product
Let \(\mathbf{A}=\begin{bmatrix}1&-2\\3&1\end{bmatrix}\) and \(\mathbf{x}=\begin{bmatrix}2\\-1\end{bmatrix}\). Compute \(\mathbf{A}\mathbf{x}\) and compare the bounds from the 1-norm and infinity norm.
Multiply row by column:
The absolute column sums are \(|1|+|3|=4\) and \(|-2|+|1|=3\), so \(\|\mathbf{A}\|_1=4\). The absolute row sums are \(|1|+|-2|=3\) and \(|3|+|1|=4\), so \(\|\mathbf{A}\|_{\infty}=4\). The input norms are \(\|\mathbf{x}\|_1=|2|+|-1|=3\) and \(\|\mathbf{x}\|_{\infty}=\max(2,1)=2\). Therefore the two estimates are
Check: the product is \((4,5)^{\top}\), as obtained by the two row calculations above; its 1-norm is \(9\) and its infinity norm is \(5\). Both claimed bounds hold, and neither bound is an equality for this input.
Worked Example: An Exact Infinity-Norm Bound
Let \(\mathbf{A}=\begin{bmatrix}1&1\\0&2\end{bmatrix}\) and \(\mathbf{x}=\begin{bmatrix}1\\1\end{bmatrix}\). Compare the two induced norm bounds.
The product is
The absolute column sums are \(1\) and \(3\), so \(\|\mathbf{A}\|_1=3\). The absolute row sums are \(2\) and \(2\), so \(\|\mathbf{A}\|_{\infty}=2\). Since \(\|\mathbf{x}\|_1=2\) and \(\|\mathbf{x}\|_{\infty}=1\), the estimates are
Check: the first component of the product is \(2\), and the second is \(2\), so the calculated output norms are \(4\) and \(2\). The infinity-norm bound is exact for this vector, while the 1-norm bound is not.
Worked Example: A Rectangular Matrix
Let \(\mathbf{A}=\begin{bmatrix}1&-1\\2&0\\-1&3\end{bmatrix}\) and \(\mathbf{x}=\begin{bmatrix}1\\-2\end{bmatrix}\). Find the product and both bounds. This example has a three-component output, so \(\mathbf{A}\) need not be square for either estimate to apply.
Multiplication gives
The absolute column sums are \(1+2+1=4\) and \(1+0+3=4\), so \(\|\mathbf{A}\|_1=4\). The absolute row sums are \(2\), \(2\), and \(4\), so \(\|\mathbf{A}\|_{\infty}=4\). Also, \(\|\mathbf{x}\|_1=3\) and \(\|\mathbf{x}\|_{\infty}=2\). Hence
Check: direct row calculations give \(3\), \(2\), and \(-7\), so the output norms are \(12\) and \(7\). The 1-norm estimate is exact here; the infinity-norm estimate leaves a gap of \(1\).
What the Bounds Do and Do Not Say
The induced norm inequality is a guarantee for every input, not a prediction of the exact output size for a particular vector. A bound can be exact for one vector and loose for another, as the examples show. Its value is that the matrix norm can be computed once from the entries of \(\mathbf{A}\), then used to bound the product for any input measured with the matching vector norm.
It is also possible for one of the two estimates to be tighter than the other. In the second example the infinity-norm estimate is exact, while the 1-norm estimate is \(6\) for an output 1-norm of \(4\). In the third example the 1-norm estimate is exact, while the infinity-norm estimate is \(8\) for an output infinity norm of \(7\). Neither norm is automatically the better choice in every problem; the input and output quantities of interest determine which is relevant.
Common Pitfall: Mixing Norms
A tempting but unjustified step is to use \(\|\mathbf{A}\|_1\) with \(\|\mathbf{x}\|_{\infty}\) and claim a bound on \(\|\mathbf{A}\mathbf{x}\|_1\). For a concrete failure, take \(\mathbf{A}=\mathbf{I}_2\) and \(\mathbf{x}=\begin{bmatrix}1\\1\end{bmatrix}\). The incorrect calculation would say \(\|\mathbf{A}\mathbf{x}\|_1\le\|\mathbf{A}\|_1\|\mathbf{x}\|_{\infty}=1\cdot1=1\). But \(\mathbf{A}\mathbf{x}=\begin{bmatrix}1\\1\end{bmatrix}\), so \(\|\mathbf{A}\mathbf{x}\|_1=2\), which contradicts that claim.
The correction is to keep the norms matched. Here \(\|\mathbf{A}\|_1=1\) and \(\|\mathbf{x}\|_1=2\), giving the valid estimate \(\|\mathbf{A}\mathbf{x}\|_1\le1\cdot2=2\). Alternatively, the infinity-norm inequality gives \(\|\mathbf{A}\mathbf{x}\|_{\infty}\le\|\mathbf{A}\|_{\infty}\|\mathbf{x}\|_{\infty}=1\cdot1=1\), also valid for this product. The two estimates concern different output sizes.
Check Your Understanding
For each question, identify which vector norm is being used on the output and use the matching induced matrix norm.
- For \(\mathbf{A}=\begin{bmatrix}2&-1\\1&3\end{bmatrix}\), compute \(\|\mathbf{A}\|_1\) and \(\|\mathbf{A}\|_{\infty}\).
- For the matrix in Question 1 and \(\mathbf{x}=\begin{bmatrix}1\\-2\end{bmatrix}\), calculate both induced norm bounds and the two norms of \(\mathbf{A}\mathbf{x}\).
- For a \(3\times2\) matrix, which sums determine its induced 1-norm: row sums or column sums?
- Explain why the induced norm inequality also holds when \(\mathbf{x}=\mathbf{0}\).
- Give a reason the 1-norm and infinity-norm bounds for one product might have different sizes.
