Norms of vectors and matrices

Norms

Consider a linear system $Ax = b$ where $A,b$ are input.

To measure the conditioning we measure the norm of output

\[\begin{cases} |x|&\in\mathbb R\\ \sqrt{a^2+b^2} &\in \mathbb C, a+bi\\ \sqrt{\sum^n x_i^2} = \|x\|_2 &x\in\mathbb R^n \end{cases}\]

Claim $\|x\|_\infty \leq \|x\|_2\leq \sqrt n \|x\|_\infty$
proof.

\[\|x\|_\infty = \sup|x_i| = |x_k| = \sqrt{x_k^2} \leq \sqrt{\sum x_i^2} = \|x\|_2\]

\[\|x\|_2 =\sqrt{\sum x_i^2} \leq \sqrt{\sum x_k^2} = \sqrt n \sqrt{x_k^2} = \sqrt n k = \sqrt n \|x\|_\infty\]

Claim reverse triangular inequality $|\|x\| - \|y\|| \leq \|x-y\|$

\[\|x\| - \|y\| = \|y + x -y\| - \|y\|\leq \|y\| + \|x - y\| - \|y\| = \|x-y\|\]

Norm for matrices

One common way to get a matrix norm is from a vector norm $\|A\| = \max_{x\neq 0} \frac{\|A\vec x\|}{\|\vec x\|}$, i.e. how much $A$ can expand $\vec x$.

Theorem $\|A\| = \max_{x\neq 0} \frac{\|Ax\|}{\|x\|} = \max_{\|x\|=1} \|Ax\|$

proof.

\[\max_{x\neq 0} \frac{\|Ax\|}{\|x\|} = \max\frac{\|A(x/\|x\|)\|}{\|x\|/\|x\|} = \max_{\|x\|=1}\|Ax\|\]

Matrix norm is induced by / subordinate to the vector norm,

Examples Given $A_{n\times n}$

\[\|A\|_1 = \max \frac{\|Ax\|_1}{\|x\|_1} = \max_{j = 1...n} \sum_{i=1}^n |A_{ij}| = \text{max column sum}\]

\[\|A\|_\infty = \max_{i = 1 ... n} \sum_{j=1}^n |A_{ij}| = \text{max row sum}\]

\[\|A\|_2 = \max\{\sqrt \lambda\| \lambda := \text{eigenvalues of }A^TA\}\]

\[\|A\|_F = \sqrt {\sum_i\sum_j |a_{ij}|^2}\]

Note that F-norm cannot be induced by vector norm. For example $|I|_F = \sqrt n $

If a norm is subordinated from a vector norm, then - it follows triangular inequality
- $\|I\| = \max \frac{\|Ix\|}{\|x\|} = 1$

Norm Equivalence

For any vector and matrix norms $\|\cdot\|_a, \|\cdot\|_b$,

\[\forall n\in\mathbb Z^+. \exists c_{1, n}, c_{2, n} > 0. \forall x\in \mathbb R^n . c_{1, n}\|x\|_a \leq \|x\|_b \leq c_{2, n} \|x\|_a\]