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 $\alpha$ :^[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.

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 (Vector norms)

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

Example 2.7.1

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

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

3.872983346207417

infnorm = norm(x, Inf)

3.0

onenorm = norm(x, 1)

7.0

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

normalize(x, Inf)

4-element Vector{Float64}:
  0.6666666666666666
 -1.0
  0.3333333333333333
 -0.3333333333333333

Example 2.7.1

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

3.872983346207417

print(norm(x, inf))

3.0

print(norm(x, 1))

7.0

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 a matrix norm via the vector 2-norm.

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

The last equality above follows from linearity (as shown in Exercise 2.7.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)

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.

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

Proof

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} \|.

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} \|,

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} \|.

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

Two of the vector norms we have encountered induce matrix norms that are easy to compute from the matrix elements.

Despite the lack of a simple formula for it, the 2-norm is the default choice for many applications and theorems.

Example 2.7.3 (Matrix norms)

Julia

MATLAB

Python

Example 2.7.3

A = [ 2 0; 1 -1 ]

2×2 Matrix{Int64}:
 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)

2.449489742783178

The default for opnorm is the 2-norm.

twonorm = opnorm(A)

2.2882456112707374

You can get the 1-norm as well.

onenorm = opnorm(A, 1)

3.0

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

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

3

Similarly, we can get the $\infty$ -norm and check our formula for it.

infnorm = opnorm(A, Inf)

2.0

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

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$ .

# 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)

Example 2.7.3

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.12), the matrix 1-norm is equivalent to the maximum of the sums down the columns (in absolute value).

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

Similarly, we can get the $\infty$ -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$ .

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'));

Example 2.7.3

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))

2.2882456112707374

You can get the 1-norm as well.

print(norm(A, 1))

3.0

The 1-norm is equivalent to

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

Similarly, we can get the $\infty$ -norm and check our formula for it.

print(norm(A, inf))

2.0

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$ .

2.7.3Exercises¶

Exercise 2.7.6

✍ 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: Use the definition of $\|\mathbf{A}\|_2$ as the maximum of $\|\mathbf{A}\mathbf{x}\|_2$ over unit vectors, and parameterize the unit vectors as $(\cos(\theta),\sin(\theta))$ . Then $\twonorm{\mathbf{A}\mathbf{x}}^2$ is a function of $\theta$ that is easy to maximize.)

Exercise 2.7.11

✍ 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 $\displaystyle \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.15)

(Hint: Start with $\left(\displaystyle\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