Vector and matrix norms - Fundamentals of Numerical Computation

The manipulations on matrices and vectors so far in this chapter have been algebraic, much like those in an introductory linear algebra course. In order to progress to the analysis of the algorithms we have introduced, we need a way to measure the size of vectors and matrices—size in the sense of magnitude or distance, not the number of rows and columns.

2.7.1Vector norms¶

For vectors, we use a norm $\| \cdot \|$ , which is a function from $\real^n$ to $\real$ with the following properties for all $n$ -vectors $\mathbf{x},\mathbf{y}$ and scalars α:^[1]

\begin{align*} \norm{\mathbf{x}} &\ge 0, \\ \norm{\mathbf{x}} &=0 \;\Leftrightarrow \; \mathbf{x}=\boldsymbol{0}, \\ \norm{\alpha \mathbf{x}} &= \abs{\alpha}\, \norm{\mathbf{x}}, \\ \norm{\mathbf{x}+\mathbf{y}} & \le \norm{\mathbf{x}} + \norm{\mathbf{y}}. \end{align*}

(2.7.1)

The last of these properties is known as the triangle inequality. It is natural to interpret $\| \mathbf{x} \|=\| \mathbf{x}-\boldsymbol{0} \|$ as the distance from $\mathbf{x}$ to the origin and $\| \mathbf{x}-\mathbf{y} \|$ as the distance from $\mathbf{x}$ to $\mathbf{y}$ . We will be using only the three most important vector norms, defined as follows.

The 2-norm corresponds to ordinary Euclidean distance.

In any norm, we refer to a vector $\mathbf{x}$ satisfying $\| \mathbf{x} \|=1$ as a unit vector. For any nonzero vector $\mathbf{v}$ we can find a unit vector through the normalization $\mathbf{x}=\mathbf{v}/\|\mathbf{v}\|$ . Thus, we can interpret

\mathbf{v} = \| \mathbf{v} \| \,\cdot\, \frac{\mathbf{v}}{\| \mathbf{v} \|}

(2.7.2)

as writing a nonzero vector $\mathbf{v}$ in magnitude–direction form.

Example 2.7.1

Given the vector $\mathbf{x}= \bigl[ 2 ,\, -3 ,\, 1 ,\, -1 \bigr]^T$ , we have

\begin{align*} \| \mathbf{x} \|_2 &= \sqrt{ 4 + 9 + 1 + 1 } = \sqrt{15}, \\[1ex] \| \mathbf{x} \|_\infty &= \max\{ 2,3,1,1 \} = 3,\\[1ex] \| \mathbf{x} \|_1 &= 2 + 3 + 1 + 1 = 7. \end{align*}

(2.7.3)

Julia

MATLAB

Python

Vector norms

In Julia the LinearAlgebra package has a norm function for vector norms.

x = [2, -3, 1, -1]
twonorm = norm(x)         # or norm(x,2)

infnorm = norm(x, Inf)

onenorm = norm(x, 1)

There is also a normalize function that divides a vector by its norm, making it a unit vector.

normalize(x, Inf)

Vector norms

The norm function from numpy.linalg computes vector norms.

from numpy.linalg import norm
x = array([2, -3, 1, -1])
print(norm(x))       # 2-norm by default

print(norm(x, inf))

print(norm(x, 1))

We say that a sequence of vectors $\mathbf{x}_1,\mathbf{x}_2,\ldots$ converges to $\mathbf{x}$ if

\lim_{k\rightarrow\infty} \norm{\mathbf{x}_k - \mathbf{x}} = 0.

(2.7.4)

By definition, a sequence is convergent in the infinity norm if and only if it converges componentwise. The same is true for a convergent sequence in any norm.

2.7.2Matrix norms¶

Although we view matrices as two-dimensional, we can also interpret them as vectors: simply stack the columns on top of one another.^[2] Hence we can define matrix norms via vector norms. This is sometimes done with the vector 2-norm and leads to the matrix Frobenius norm:

\| \mathbf{A} \|_F = \left( \sum_{i,j} |A_{ij}|^2 \right)^{1/2}.

(2.7.5)

However, it often proves to be more useful to define matrix norms differently.

The last equality above follows from linearity (as shown in Exercise 5). It is derived from the interpretation of a matrix as a linear operator between $\real^n$ and $\real^m$ . Thus in the 2-norm, for instance,

\| \mathbf{A} \|_2 = \max_{\| \mathbf{x} \|_2=1} \| \mathbf{A}\mathbf{x} \|_2.

(2.7.7)

For the rest of this section we will continue to omit subscripts when we want to refer to an unspecified induced norm; after this section, an unsubscripted norm is understood to be the 2-norm.

The definition of an induced matrix norm may seem oddly complicated. However, there are some key properties that follow directly from the definition.

Proof 2.7.1

The first result is trivial if $\mathbf{x}=\boldsymbol{0}$ ; otherwise,

\frac{ \| \mathbf{A}\mathbf{x} \| }{\| \mathbf{x} \|} \le \max_{\mathbf{x}\neq \boldsymbol{0}} \frac{\| \mathbf{A}\mathbf{x} \|}{\| \mathbf{x} \|} = \| \mathbf{A} \|.

(2.7.11)

Inequality (2.7.9) then follows because

\| \mathbf{A}\mathbf{B}\mathbf{x} \| =\| \mathbf{A}(\mathbf{B}\mathbf{x}) \|\le \| \mathbf{A} \|\cdot\| \mathbf{B}\mathbf{x} \| \le \| \mathbf{A} \|\cdot\| \mathbf{B} \|\cdot\| \mathbf{x} \|,

(2.7.12)

and then

\| \mathbf{A}\mathbf{B} \| = \max_{\mathbf{x}\neq \boldsymbol{0}} \frac{\| \mathbf{A}\mathbf{B}\mathbf{x} \|}{\| \mathbf{x} \|} \le \max_{\mathbf{x}\neq \boldsymbol{0}} \| \mathbf{A} \|\cdot\| \mathbf{B} \| = \| \mathbf{A} \|\cdot\| \mathbf{B} \|.

(2.7.13)

Finally, (2.7.10) results from repeated application of (2.7.9).

One can interpret the definition of an induced norm geometrically. Each vector $\mathbf{x}$ on the unit “sphere” (as defined by the chosen vector norm) is mapped to its image $\mathbf{A}\mathbf{x}$ , and the norm of $\mathbf{A}$ is the radius of the smallest “sphere” that encloses all such images.

In addition, two of the vector norms we have encountered lead to equivalent formulas that are easy to compute from the matrix elements.

A mnemonic for these is that the ∞ symbol extends horizontally while the 1 character extends vertically, each indicating the direction of the summation in its formula. Also, both formulas give the same result for $m\times 1$ matrices as the vector norm. In both cases you must take absolute values of the matrix elements first.

Example 2.7.2

Julia

MATLAB

Python

Matrix norms

A = [ 2 0; 1 -1 ]

In Julia, one uses norm for vector norms and for the Frobenius norm of a matrix, which is like stacking the matrix into a single vector before taking the 2-norm.

Fronorm = norm(A)

Most of the time we want to use opnorm, which is an induced matrix norm. The default is the 2-norm.

twonorm = opnorm(A)

You can get the 1-norm as well.

onenorm = opnorm(A, 1)

According to (2.7.15), the matrix 1-norm is equivalent to the maximum of the sums down the columns (in absolute value).

Use sum to sum along a dimension of a matrix. You can also sum over the entire matrix by omitting the dims argument.

The maximum and minimum functions also work along one dimension or over an entire matrix. To get both values at once, use extrema.

# Sum down the rows (1st matrix dimension):
maximum( sum(abs.(A), dims=1) )

Similarly, we can get the ∞-norm and check our formula for it.

infnorm = opnorm(A, Inf)

 # Sum across columns (2nd matrix dimension):
maximum( sum(abs.(A), dims=2) )

Next we illustrate a geometric interpretation of the 2-norm. First, we will sample a lot of vectors on the unit circle in $\mathbb{R}^2$ .

You can use functions as values, e.g., as elements of a vector.

# Construct 601 unit column vectors.
θ = 2π * (0:1/600:1)   # type \theta then Tab
x = [ fun(t) for fun in [cos, sin], t in θ ];

To create an array of plots, start with a plot that has a layout argument, then do subsequent plot! calls with a subplot argument.

plot(aspect_ratio=1, layout=(1, 2),
    xlabel=L"x_1",  ylabel=L"x_2")
plot!(x[1, :], x[2, :], subplot=1, title="Unit circle")

The linear function $\mathbf{f}(\mathbf{x}) = \mathbf{A}\mathbf{x}$ defines a mapping from $\mathbb{R}^2$ to $\mathbb{R}^2$ . We can apply A to every column of x by using a single matrix multiplication.

Ax = A * x;

The image of the transformed vectors is an ellipse.

plot!(Ax[1, :], Ax[2, :], 
    subplot=2, title="Image under x → Ax")

That ellipse just touches the circle of radius $\|\mathbf{A}\|_2$ .

plot!(twonorm*x[1, :], twonorm*x[2, :], subplot=2, l=:dash)

Matrix norms

A = [ 2 0; 1 -1 ]

The default matrix norm is the 2-norm.

twonorm = norm(A)

You can get the 1-norm as well.

onenorm = norm(A, 1)

According to (2.7.15), the matrix 1-norm is equivalent to the maximum of the sums down the columns (in absolute value).

Use sum to sum along a dimension of a matrix. The max and min functions also work along one dimension.

% Sum down the rows (1st matrix dimension):
max( sum(abs(A), 1) )

Similarly, we can get the ∞-norm and check our formula for it.

infnorm = norm(A, Inf)

% Sum across columns (2nd matrix dimension):
max( sum(abs(A), 2) )

Next we illustrate a geometric interpretation of the 2-norm. First, we will sample a lot of vectors on the unit circle in $\mathbb{R}^2$ .

You can use functions as values, e.g., as elements of a vector.

theta = linspace(0, 2*pi, 601);
x = [ cos(theta); sin(theta) ];    % 601 unit column vectors
clf
subplot(1, 2, 1)
plot(x(1, :), x(2, :)), axis equal
title('Unit circle in 2-norm')
xlabel('x_1')
ylabel('x_2')

Ax = A * x;

The image of the transformed vectors is an ellipse that just touches the circle of radius $\|\mathbf{A}\|_2$ :

subplot(1,2,2), plot(Ax(1,:), Ax(2,:)), axis equal
hold on, plot(twonorm * x(1,:), twonorm * x(2,:), '--')
title('Image of Ax, with ||A||')
xlabel('x_1')
ylabel('x_2')

Matrix norms

from numpy.linalg import norm
A = array([ [2, 0], [1, -1] ])

The default matrix norm is not the 2-norm. Instead, you must provide the 2 explicitly.

print(norm(A, 2))

You can get the 1-norm as well.

print(norm(A, 1))

The 1-norm is equivalent to

print(max( sum(abs(A), axis=0)) )  # sum down the rows

Similarly, we can get the ∞-norm and check our formula for it.

print(norm(A, inf))

print(max( sum(abs(A), axis=1)) )  # sum across columns

Here we illustrate the geometric interpretation of the 2-norm. First, we will sample a lot of vectors on the unit circle in $\mathbb{R}^2$ .

theta = linspace(0, 2*pi, 601)
x = vstack([cos(theta), sin(theta)])  # 601 unit columns

The linear function $\mathbf{f}(\mathbf{x}) = \mathbf{A}\mathbf{x}$ defines a mapping from $\mathbb{R}^2$ to $\mathbb{R}^2$ . We can apply A to every column of x simply by using a matrix multiplication.

y = A @ x

We plot the unit circle on the left and the image of all mapped vectors on the right:

subplot(1,2,1)
plot(x[0, :], x[1, :])
axis("equal")
title("Unit circle")
xlabel("$x_1$")
ylabel("$x_2$")

subplot(1,2,2)
plot(y[0, :], y[1, :])
plot(norm(A, 2) * x[0, :], norm(A,2) * x[1, :],"--")
axis("equal")
title("Image under map")
xlabel("$y_1$")
ylabel("$y_2$");

As seen on the right-side plot, the image of the transformed vectors is an ellipse that just touches the circle of radius $\|\mathbf{A}\|_2$ .

The geometric interpretation of the matrix 2-norm shown in Demo 2.7.2, as the radius of the smallest circle (or sphere or hypersphere in higher dimensions) containing the images of all unit vectors, is not a practical means of computing the norm. Nor is there a simple formula like (2.7.14) or (2.7.15) for it. The computation of the matrix 2-norm is discussed further in Chapter 7.

2.7.3Exercises¶

✍ Why is the vector 1-norm also called the taxicab norm?
✍ (a) Draw the unit “circle” in the ∞-norm, i.e., the set of all vectors $\mathbf{x}\in\real^2$ such that $\| \mathbf{x} \|_\infty=1$ .
(b) Draw the unit “circle” in the 1-norm.
✍ Prove that for all vectors $\mathbf{x}\in\real^n$ ,
(a) $\| \mathbf{x} \|_\infty \le \| \mathbf{x} \|_2; \qquad$ (b) $\| \mathbf{x} \|_2 \le \| \mathbf{x} \|_1$ .
✍ Prove that for any vectors $\mathbf{x}$ , $\mathbf{y}$ in $\real^n$ , $|\mathbf{x}^T\mathbf{y}| \le \| \mathbf{x} \|_1\| \mathbf{y} \|_\infty$ .
✍ Prove using Definition 2.7.2 that for any induced matrix norm, matrix $\mathbf{A}$ , and scalar $c$ , $\| c\mathbf{A} \| = |c|\cdot \| \mathbf{A} \|$ .
✍ Let $\mathbf{A} = \displaystyle \begin{bmatrix} -1 & 1 \\ 2 & 2 \end{bmatrix}.$
(a) Find all vectors satisfying $\|\mathbf{x}\|_\infty=1$ and $\| \mathbf{A}\mathbf{x} \|_\infty=\| \mathbf{A} \|_\infty$ .
(b) Find a vector satisfying $\|\mathbf{x}\|_1=1$ and $\| \mathbf{A}\mathbf{x} \|_1=\| \mathbf{A} \|_1$ .
(c) Find a vector satisfying $\|\mathbf{x}\|_2=1$ such that $\| \mathbf{A}\mathbf{x} \|_2=\| \mathbf{A} \|_2$ . (Hint: A unit two-dimensional vector is a function only of its angle with the $x_1$ -axis. Use the definition of $\|\mathbf{A}\|_2$ as the maximum of $\|\mathbf{A}\mathbf{x}\|_2$ , which is a also a function of the angle.)
✍ Prove the equivalence of the two formulas for a matrix norm in (2.7.6).
✍ Prove that for any induced matrix norm and nonsingular matrix $\mathbf{A}$ , $\| \mathbf{A}^{-1} \| \ge (\| \mathbf{A} \|)^{-1}$ . (Hint: Apply Theorem 2.7.2.)
✍ (a) Prove that for any $\mathbf{v}\in \real^n$ ,
$\| \mathbf{v} \|_p \ge \max_{i=1,\ldots,n} |v_i|,$
(2.7.16)
where $p=1$ , 2, or ∞.
(b) Prove that for any $\mathbf{A}\in\real^{n \times n}$ ,
$\| \mathbf{A} \|_p \ge \max_{i,j=1,\ldots,n} |A_{ij}|,$
(2.7.17)
where $p=1$ , 2, or ∞. (Hint: For $p=2$ , rearrange (2.7.8) for a well-chosen particular value of $\mathbf{x}$ .)
✍ Prove using Definition 2.7.2 that if $\mathbf{D}$ is a diagonal matrix, then $\|\mathbf{D}\|_2 = \max_{i} |D_{ii}|$ . You may assume the matrix is real and square, but that does not affect the result or the proof in any significant way. (Hint: Let $M=\max_{i} |D_{ii}|$ . Proceed in two stages, showing that $\|\mathbf{D}\|_2\ge M$ and separately that $\|\mathbf{D}\|_2\le M$ .)
✍ Suppose that $\mathbf{A}$ is ${n\times n}$ and that $\| \mathbf{A} \|<1$ in some induced matrix norm.
(a) Show that $(\mathbf{I}-\mathbf{A})$ is nonsingular. (Hint: Use the definition of an induced matrix norm to show that if $(\mathbf{I}-\mathbf{A})\mathbf{x}=\boldsymbol{0}$ for all nonzero $\mathbf{x}$ , then $\| \mathbf{A} \|\ge 1$ .)
(b) Show that $\lim_{m\rightarrow \infty} \mathbf{A}^m = \boldsymbol{0}$ . (For matrices as with vectors, we say $\mathbf{B}_m \rightarrow \mathbf{L}$ if $\| \mathbf{B}_m-\mathbf{L} \| \rightarrow 0$ .)
(c) Use (a) and (b) to show that we may obtain the geometric series
$(\mathbf{I}-\mathbf{A})^{-1} = \sum_{k=0}^\infty \mathbf{A}^k.$
(2.7.18)
(Hint: Start with $\left(\sum_{k=0}^m \mathbf{A}^k\right)(\mathbf{I}-\mathbf{A})$ and take the limit.)

Footnotes¶

The same statements work for vectors with complex entries, with complex modulus in place of absolute values.
↩
Column stacking is actually how matrices are stored in memory within Julia and is known as column-major order. MATLAB and FORTRAN also use column-major order, while C and Python use row-major order, in which the rows are stacked.
↩

Preface

Row pivoting

Preface

Conditioning of linear systems