Matrix Norms for Measuring Amplification

Three Ways to Measure a Matrix

A matrix can be large in more than one sense. Its entries might have a large combined size, or it might amplify some inputs substantially. These ideas lead to different matrix norms. The induced 1-norm and induced infinity norm describe the largest possible input-to-output size ratio when input and output vectors are measured with the corresponding vector norms. The Frobenius norm instead combines the sizes of all entries. These measurements are useful in computation, but they answer different questions.

Throughout this tutorial, \(\mathbf{A}\in\mathbb{R}^{m\times n}\). For a vector \(\mathbf{x}\in\mathbb{R}^n\), the 1-norm is \(\|\mathbf{x}\|_1=\sum_{j=1}^{n}|x_j|\), and the infinity norm is \(\|\mathbf{x}\|_{\infty}=\max_{1\le j\le n}|x_j|\). For a nonzero input, the ratio \(\|\mathbf{A}\mathbf{x}\|/\|\mathbf{x}\|\) compares the output size with the input size, using the same chosen vector norm in numerator and denominator.

The supremum in an induced norm definition is the least upper bound of all the ratios over nonzero inputs. In the finite-dimensional setting here, the formulas below show that each of these suprema is attained by at least one nonzero input. Thus each induced norm gives the greatest amplification ratio possible under its chosen vector norm. The Frobenius norm is calculated directly from the entries; it is not defined as a largest input-output ratio.

Why Column Sums and Row Sums Appear

Proof. First consider the induced 1-norm. For every \(\mathbf{x}\in\mathbb{R}^n\), the triangle inequality gives \[ \|\mathbf{A}\mathbf{x}\|_1 =\sum_{i=1}^{m}\left|\sum_{j=1}^{n}a_{ij}x_j\right| \le \sum_{i=1}^{m}\sum_{j=1}^{n}|a_{ij}||x_j| =\sum_{j=1}^{n}\left(\sum_{i=1}^{m}|a_{ij}|\right)|x_j|. \] Let \(C=\max_{1\le j\le n}\sum_{i=1}^{m}|a_{ij}|\). The last expression is at most \(C\sum_{j=1}^{n}|x_j|=C\|\mathbf{x}\|_1\). Consequently every nonzero input has ratio at most \(C\). Choose a column index \(k\) whose absolute column sum is \(C\). The standard basis vector \(\mathbf{e}_k\) has \(\|\mathbf{e}_k\|_1=1\), and \(\mathbf{A}\mathbf{e}_k\) is column \(k\) of \(\mathbf{A}\), so \(\|\mathbf{A}\mathbf{e}_k\|_1=C\). This attains the bound and proves \(\|\mathbf{A}\|_1=C\).

Now consider the induced infinity norm. For every row \(i\) and every \(\mathbf{x}\in\mathbb{R}^n\), \[ |(\mathbf{A}\mathbf{x})_i| =\left|\sum_{j=1}^{n}a_{ij}x_j\right| \le\sum_{j=1}^{n}|a_{ij}||x_j| \le\left(\sum_{j=1}^{n}|a_{ij}|\right)\|\mathbf{x}\|_{\infty}. \] Let \(R=\max_{1\le i\le m}\sum_{j=1}^{n}|a_{ij}|\). Taking the maximum over rows shows \(\|\mathbf{A}\mathbf{x}\|_{\infty}\le R\|\mathbf{x}\|_{\infty}\), so every nonzero input has ratio at most \(R\). If \(R=0\), every entry of \(\mathbf{A}\) is zero and every ratio is zero. If \(R>0\), choose a row \(k\) whose absolute row sum is \(R\), and set \(x_j=1\) when \(a_{kj}>0\), \(x_j=-1\) when \(a_{kj}<0\), and \(x_j=0\) when \(a_{kj}=0\). At least one \(x_j\) is nonzero, and \(\|\mathbf{x}\|_{\infty}=1\). The \(k\)th entry of \(\mathbf{A}\mathbf{x}\) is \(\sum_{j=1}^{n}|a_{kj}|=R\), so \(\|\mathbf{A}\mathbf{x}\|_{\infty}\ge R\). Together with the upper bound, the ratio is exactly \(R\), proving the formula. \(\square\)

The proof also explains how to find inputs that attain the norms. For the 1-norm, a standard basis vector selects a column with largest absolute column sum. For the infinity norm, signs chosen to match a row with largest absolute row sum make the terms in that row add rather than cancel.

Computing All Three Norms

Proof. Write the columns of \(\mathbf{A}\) as \(\mathbf{a}_1,\dots,\mathbf{a}_n\). Each column has \(\|\mathbf{a}_j\|_2^2=\sum_{i=1}^{m}a_{ij}^2\). Summing these equalities over all columns gives \[ \sum_{j=1}^{n}\|\mathbf{a}_j\|_2^2 =\sum_{j=1}^{n}\sum_{i=1}^{m}a_{ij}^2 =\|\mathbf{A}\|_F^2. \] The transpose contains exactly the same entries, with rows and columns exchanged. Its sum of squared entries is therefore also \(\sum_{i=1}^{m}\sum_{j=1}^{n}a_{ij}^2\), so \(\|\mathbf{A}^{\top}\|_F=\|\mathbf{A}\|_F\). \(\square\)

Reading the Three Measurements

The induced norms depend on how vector size is measured. The induced 1-norm weights a matrix through its columns because a coordinate input \(\mathbf{e}_j\) isolates column \(j\). The induced infinity norm depends on row sums because the output infinity norm looks at the largest output coordinate, and a suitable input can align the signs in one row. The Frobenius norm has no chosen input vector: it aggregates all entries at once.

These distinctions matter when describing a matrix as large or when estimating its effect on data. A large induced norm means that some input can experience a large output-to-input ratio under the specified vector norm. A large Frobenius norm means that the entries, taken together, have substantial squared magnitude. One number need not determine the others, so a calculation should name the norm being used rather than simply say “the matrix norm.”

Common Mistake: Using the Wrong Sums

For \(\mathbf{D}=\begin{bmatrix}1&2\\3&4\end{bmatrix}\), a common incorrect calculation is to add the rows and report \(\|\mathbf{D}\|_1=7\), using \(1+2=3\) and \(3+4=7\). Those are row sums, so their maximum gives the induced infinity norm, not the induced 1-norm. The absolute column sums are \(1+3=4\) and \(2+4=6\), giving \(\|\mathbf{D}\|_1=6\); the row sums give \(\|\mathbf{D}\|_{\infty}=7\). Indeed, \(\mathbf{D}\mathbf{e}_2=(2,4)^{\top}\) has 1-norm \(6\), while \(\mathbf{e}_2\) has 1-norm \(1\). The correction follows both the formula and an input that attains it.

Another error is to treat the Frobenius norm as the largest row or column sum. For the same matrix, \(\|\mathbf{D}\|_F=\sqrt{1+4+9+16}=\sqrt{30}\), which is computed from squares of entries, not from either set of sums.