5.1 Norms of vectors and matrices
Definition 5.1.1. A vector norm on \(\mathbb R^n\) is a function \(\|\cdot \|\) with, for all \(\mathbf x,\mathbf y\in \mathbb R^n\) and \(\alpha \in \mathbb R\),
- (i)
- \(\|\mathbf x\|\geq 0\), with \(\|\mathbf x\| = 0\) only if \(\mathbf x = \mathbf 0\);
- (ii)
- \(\|\alpha \mathbf x\| = |\alpha |\,\|\mathbf x\|\);
- (iii)
- \(\|\mathbf x+\mathbf y\|\leq \|\mathbf x\|+\|\mathbf y\|\) (the triangle inequality).
The three norms used in this course are \[\|\mathbf x\|_1 = \sum _{i=1}^n|x_i|,\qquad \|\mathbf x\|_2 = \left (\sum _{i=1}^nx_i^2\right )^{1/2},\qquad \|\mathbf x\|_\infty = \max _{1\leq i\leq n}|x_i| .\]
That \(\|\cdot \|_1\) and \(\|\cdot \|_\infty \) satisfy (i)–(iii) is immediate. For the Euclidean norm \(\|\cdot \|_2\) the triangle inequality rests on the next result.
Theorem 5.1.2 (Cauchy–Schwarz inequality). For all \(\mathbf x,\mathbf y\in \mathbb R^n\), \(|\mathbf x^T\mathbf y|\leq \|\mathbf x\|_2\|\mathbf y\|_2\).
Proof. If \(\mathbf y = \mathbf 0\) there is nothing to prove. Otherwise, for every real \(t\), \[0\leq \|\mathbf x-t\mathbf y\|_2^2 = \|\mathbf x\|_2^2-2t\,\mathbf x^T\mathbf y+t^2\|\mathbf y\|_2^2 .\] A quadratic in \(t\) that is never negative has non-positive discriminant: \(4(\mathbf x^T\mathbf y)^2-4\|\mathbf x\|_2^2\|\mathbf y\|_2^2\leq 0\). □
Then \(\|\mathbf x+\mathbf y\|_2^2 = \|\mathbf x\|_2^2+2\mathbf x^T\mathbf y+\|\mathbf y\|_2^2\leq (\|\mathbf x\|_2+\|\mathbf y\|_2)^2\). The norms are also comparable: since \(\max _i|x_i|^2\leq \sum _ix_i^2\leq n\max _i|x_i|^2\), \begin {equation} \label {eq:normequiv} \|\mathbf x\|_\infty \leq \|\mathbf x\|_2\leq \sqrt n\,\|\mathbf x\|_\infty . \end {equation} A sequence of vectors \(\mathbf x^{(k)}\) converges to \(\mathbf x\) if \(\|\mathbf x^{(k)}-\mathbf x\|\longrightarrow 0\). By (5.1) this does not depend on which of the norms is used, and it is equivalent to convergence of each component.
Example 5.1.3. For \(\mathbf x = (-1,1,-2)^T\): \(\|\mathbf x\|_1 = 4\), \(\|\mathbf x\|_2 = \sqrt 6 = 2.449\), \(\|\mathbf x\|_\infty = 2\), in agreement with (5.1): \(2\leq 2.449\leq \sqrt 3\cdot 2 = 3.464\).
Definition 5.1.4. For a vector norm \(\|\cdot \|\), the natural (or induced) matrix norm is \[\|A\| = \max _{\mathbf x\neq \mathbf 0}\frac {\|A\mathbf x\|}{\|\mathbf x\|} = \max _{\|\mathbf x\| = 1}\|A\mathbf x\| .\] It measures the largest factor by which \(A\) can stretch a vector. Directly from the definition, \(\|A\mathbf x\|\leq \|A\|\,\|\mathbf x\|\) and \(\|AB\|\leq \|A\|\,\|B\|\).
Theorem 5.1.5. \(\displaystyle \|A\|_\infty = \max _{1\leq i\leq n}\sum _{j=1}^n|a_{ij}|\) (the largest row sum) and \(\displaystyle \|A\|_1 = \max _{1\leq j\leq n}\sum _{i=1}^n|a_{ij}|\) (the largest column sum).
Proof. Let \(R = \max _i\sum _j|a_{ij}|\). If \(\|\mathbf x\|_\infty = 1\) then \(|(A\mathbf x)_i| = \left |\sum _ja_{ij}x_j\right |\leq \sum _j|a_{ij}|\leq R\) for each \(i\), so \(\|A\|_\infty \leq R\). Conversely, let row \(p\) attain the maximum and put \(x_j = \sgn a_{pj}\) (or \(1\) if \(a_{pj} = 0\)). Then \(\|\mathbf x\|_\infty = 1\) and \((A\mathbf x)_p = \sum _j|a_{pj}| = R\), so \(\|A\|_\infty \geq R\). The proof for \(\|A\|_1\) is similar, with \(\mathbf x\) a suitable unit vector \(\mathbf e_q\). □
Example 5.1.6. For \(A = \begin {pmatrix}1&2&-1\\0&3&-1\\5&-1&1\end {pmatrix}\) the row sums of absolute values are \(4\), \(4\), \(7\) and the column sums \(6\), \(6\), \(3\), so \(\|A\|_\infty = 7\) and \(\|A\|_1 = 6\).
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.