Norms

• 1. Vector Norms
• 2. Matrix Norms
• Reference

1. Vector Norms

Let $x = (x_1, \cdots, x_n)^t$ be an $n \times 1$ vector.

• $p$-norm: $\left\| x \right\|_p = \left(\sum_{i=1}^n \vert x_i \vert^p\right)^{\frac{1}{p}}$
• $1$-norm: $\left\| x \right\|_1 = \sum_{i=1}^n \vert x_i \vert$
• $2$-norm(Euclidean norm): $\left\| x \right\|_2 = \left(\sum_{i=1}^n \vert x_i \vert^2\right)^{\frac{1}{2}}$
• $\infty$-norm: $\left\| x \right\|_{\infty} = \max \vert x_i \vert$

$$\begin{aligned} \left\| x \right\|_{\infty} &= \lim_{p \to \infty} \left(\sum_{i=1}^n \vert x_i \vert^p\right)^{\frac{1}{p}} = \lim_{p \to \infty} \left(\vert x_j \vert^p\right)^{\frac{1}{p}} \text{ where } j = \argmax \vert x_i \vert \\ &= \max \vert x_i \vert \end{aligned}$$

• The graphs of $\left\| x \right\|_1 = \left\| x \right\|_2 = \left\| x \right\|_{\infty} = 1$ for $x \in \R^2$ are as follows.

• For any vector $\overline{x}$, $\left\| x \right\|_{\infty} \le \left\| x \right\|_2 \le \left\| x \right\|_1$. The below image shows this comparison when $\overline{x} \in \R^2$.

• Meanwhile, $\left\| x \right\|_1 \le \sqrt{n} \left\| x \right\|_2$, $\left\| x \right\|_2 \le \sqrt{n} \left\| x \right\|_{\infty}$, and $\left\| x \right\|_1 \le n \left\| x \right\|_{\infty}$.
• If $\left\| x \right\|_p > 0$, then $x \not = 0$.
• $\left\| \gamma x \right\|_p = \vert \gamma \vert \left\| x \right\|_p$ where $\gamma \in \mathbb{R}$.
• $\left\| x + y \right\|_p \le \left\| x \right\|_p + \left\| y \right\|_p$.
• $\vert \left\| x \right\|_p - \left\| y \right\|_p \vert \le \left\| x - y \right\|_p$.

2. Matrix Norms

Suppose that $A$ is an $m \times n$ matrix and $a_{ij}$ is the $(i, j)$ element of $A$. $\left\| A \right\|$ means the maximum stretching of $A$ to any vector $x$. $$\begin{aligned} \left\| A \right\| = \max_{x \not = 0} \frac{\left\| Ax \right\|}{\left\| x \right\|} \end{aligned}$$

• $\left\| A \right\|_1 = \max \sum_{i=1}^m \vert a_{ij} \vert$, which means the largest column sum of $A$.
• $\left\| A \right\|_2$ is the largest singular value of $A$, which means the square root of the largest eigenvalue of $A^tA$.
• When $A$ is symmetric, $A^tAv = A(\lambda v) = \lambda^2 v$ where $x$ and $\lambda$ are the eigenvector and eigenvalue of $A$. Then

$$\begin{aligned} \left\| A \right\|_2 = \sqrt{\lambda_{\max} (A^t A)} = \sqrt{\lambda_{\max} (A)^2} = \vert \lambda_{\max} (A) \vert \end{aligned}$$

• $\left\| A \right\|_{\infty} = \max \sum_{i=1}^n \vert a_{ij} \vert$, which means the largest row sum of $A$.
• $\left\| A \right\| > 0$, then $A \not = O$.
• $\left\| \gamma A \right\| = \vert \gamma \vert \left\| A \right\|$ where $\gamma \in \mathbb{R}$.
• $\left\| A + B \right\| \le \left\| A \right\| + \left\| B \right\|$.
• $\left\| AB \right\| \le \left\| A \right\| \left\| B \right\|$.
• $\left\| Ax \right\| \le \left\| A \right\| \left\| x \right\|$.

Reference

[1] Michael T. Heath, Scientific Computing: An Introductory Survey. 2nd Edition, McGraw-Hill Higher Education.