from numpy import *
from scipy import linalg
from scipy.linalg import norm
from matplotlib.pyplot import *
from prettytable import PrettyTable
from timeit import default_timer as timer
import sys
sys.path.append('fncbook/')
import fncbook as FNC

# This (optional) block is for improving the display of plots.
# from IPython.display import set_matplotlib_formats
# set_matplotlib_formats("svg","pdf")
# %config InlineBackend.figure_format = 'svg'
rcParams["figure.figsize"] = [7, 4]
rcParams["lines.linewidth"] = 2
rcParams["lines.markersize"] = 4
rcParams['animation.html'] = "jshtml"  # or try "html5"

2.7.Vector and matrix norms¶

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)

The norm function from scipy.linalg computes vector norms.

from scipy.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.

Tip

A mnemonic for (2.7.11) and (2.7.12) is that the $\infty$ 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 before summing.

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)

from scipy.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 $\real^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 $\real^2$ to $\real^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.
↩