Vector Norms

Definition

In order to create a notion of the "size" of a vector, we introduce norms. The scalar concepts of magnitude, absolute value, or modulus is generalized to norms for vectors (and matrices).

A common type of norm for vectors is a p-norm, which for an integer \(p\) and an \(n \times 1\) vector \(\mathbf{x}\) is defined as:

\[ ||\mathbf{x}||_{p} = \left(\sum ^{n}_{i=1} |x_{i}|^{p}\right)^{1/p}. \]

The important special cases are:

• 1-norm (or Manhattan norm):

\[ ||\mathbf{x}||_{1} = \sum_{i=1}^{n}|x_{i}| \]

• 2-norm (or Euclidean distance):

\[ ||\mathbf{x}||_{2} = \sqrt{ \sum ^{n}_{i=1}|x_{i}|^{2} } \]

• \(\infty\)-norm:

\[ ||\mathbf{x}||_{\infty} = \text{max}_{1\leq i\leq n} |x_{i}| \]

All of the norms give similar qualitative results, but in certain circumstances a particular norm can be easier to work with analytically or computationally. Either the 1-norm or \(\infty\)-norm is usually used in analyzing the sensitivity of solutions to linear systems.

---

In general, for any vector \(n \times 1\) vector \(\mathbf{x}\), we have

\[ ||\mathbf{x}||_{1} \geq ||\mathbf{x}||_{2} \geq ||\mathbf{x}||_{\infty} \]

On the other hand we have

\[ ||\mathbf{x}||_{1} \leq \sqrt{ n }||\mathbf{x}||_{2}, \ \ \ \ \ ||\mathbf{x}||_{2} \leq \sqrt{ n }||\mathbf{x}||_{\infty}, \ \ \ \ \ ||\mathbf{x}||_1 \leq n||\mathbf{x}||_{\infty} \]

Notice that the norms only differ by a given constant \(n\), which means if one norm is small, the others will be proportionately small. Thus, we can choose whichever norm to compute for convenience.

---

Properties of p-norms

For any vector p-norm, the following properties hold for vectors \(\mathbf{x}, \mathbf{y}\).

1. \(||\mathbf{x}|| > 0\) if \(\mathbf{x \neq 0}\)
2. \(||\gamma \mathbf{x}|| = |\gamma| \cdot ||\mathbf{x}||\) for any scalar \(\gamma\)
3. \(||\mathbf{x+y}|| \leq ||\mathbf{x}|| +||\mathbf{y}||\) (triangle inequality)

A useful variation of the triangle inequality is:

\[ |\ ||\mathbf{x}|| - ||\mathbf{y}||\ | \leq ||\mathbf{x-y}|| \]