An Invitation to 3-D Vision: Appendix A

09 Aug, 2026

Algebra is very generous: she often gives more than is asked for.

Jean d'Alembert

We assume that the reader already has basic training in linear algebra. $^{1}$ This appendix provides a brief review of some of the important facts that are used in this book. For a more complete introduction, the reader should resort to a book such as [Strang, 1988].

In this book, we deal mostly with finite-dimensional (typically two-, three-, or four-dimensional) linear spaces, which are also often called linear vector spaces. For generality, we consider the linear space to be $n$ -dimensional. A linear space is typically denoted by the letter $V$ (for "vector space"). Although most of the time we will deal with vectors of real numbers $ℝ$ , occasionally, we will encounter vectors of complex numbers $^{2} ℂ$ . For simplicity, our review will be conducted for linear spaces over the field $ℝ$ of real numbers with the understanding that most definitions and results generalize to the complex case with little change.

Definition A. 1 (A linear space or a vector space). A set (of vectors) $V$ is considered a linear space over the field $ℝ$ if its elements, called vectors, are closed under two basic operations: scalar multiplication and vector summation "+." That is, given any two vectors $v_{1}, v_{2} \in V$ and any two scalars $α, β \in ℝ$ , the linear combination $v = α v_{1} + β v_{2}$ is also a vector in $V$ . Furthermore, the addition is commutative and associative, it has an identity 0, and each element has an inverse,"-v," such that $v + (- v) = 0$ . The scalar multiplication respects the structure of $ℝ$ ; i.e. $α (β) v = (α β) v, 1 v = v$ and $0 v = 0$ . The addition and scalar multiplication are related by the distributive laws: $(α + β) v = α v + β v$ and $α (v + u) = α v + α u$ .

$^{1}$ Some familiarity with the numerical software Matlab is also encouraged.

$^{2}$ For instance, the eigenvalues or eigenvectors of a real matrix could be complex.

For example, $ℝ^{n}$ is a linear space over the field of real numbers $ℝ$ . To be consistent, we always use a column to represent a vector:

{[x_{1}, x_{2}, \dots, x_{n}]}^{T} = [\begin{matrix} x_{1} \\ x_{2} \\ ⋮ \\ x_{n} \end{matrix}] \in ℝ^{n}, \tag A .1

where ${[x_{1}, x_{2}, \dots, x_{n}]}^{T}$ means "the (row) vector $[x_{1}, x_{2}, \dots, x_{n}]$ transposed." Given two scalars $α, β \in ℝ$ and two vectors $v_{1} = {[x_{1}, x_{2}, \dots, x_{n}]}^{T} \in ℝ^{n}$ and $v_{2} = {[y_{1}, y_{2}, \dots, y_{n}]}^{T} \in ℝ^{n}$ , their linear combination is a componentwise summation weighted by $α$ and $β$ :

α v_{1} + β v_{2} = α {[x_{1}, x_{2}, \dots, x_{n}]}^{T} + β {[y_{1}, y_{2}, \dots, y_{n}]}^{T}

= {[α x_{1} + β y_{1}, α x_{2} + β y_{2}, \dots, α x_{n} + β y_{n}]}^{T} .

A.1 Basic notions associated with a linear space

We will now provide a brief review of basic notions and frequently used notation associated with a linear vector space $V$ (i.e. $ℝ^{n}$ ).

A.1.1 Linear independence and change of basis

Definition A. 2 (Subspace). A subset $W$ of a linear space $V$ is called a subspace if the zero vector 0 is in $W$ and $α w_{1} + β w_{2} \in W$ for all $α, β \in ℝ$ and $w_{1}, w_{2} \in W$ .

Definition A. 3 (Spanned subspace). Given a set of vectors $S = {v_{i}}_{i = 1}^{m}$ , the subspace spanned by $S$ is the set of all finite linear combinations $\sum_{i = 1}^{m} α_{i} v_{i}$ for all $α_{1}, α_{2}, \dots, α_{m} \in ℝ$ . This subspace is usually denoted by $span (S)$ .

For example, the two vectors $v_{1} = {[1, 0, 0]}^{T}$ and $v_{2} = {[1, 1, 0]}^{T}$ span a subspace of $ℝ^{3}$ whose vectors are of the general form $v = {[x, y, 0]}^{T}$ .

Definition A. 4 (Linear independence). A set of vectors $S = {v_{i}}_{i = 1}^{m}$ is linearly independent if the equation

α_{1} v_{1} + α_{2} v_{2} + \dots + α_{m} v_{m} = 0

implies

α_{1} = α_{2} = \dots = α_{n} = 0 .

On the other hand, a set of vectors ${v_{i}}_{i = 1}^{m}$ is said to be linearly dependent if there exist $α_{1}, α_{2} \dots, α_{m} \in ℝ$ not all zero such that

α_{1} v_{1} + α_{2} v_{2} + \dots + α_{m} v_{m} = 0 .

Definition A. 5 (Basis). A set of vectors $B = {b_{i}}_{i = 1}^{n}$ of a linear space $V$ is said to be a basis if $B$ is a linearly independent set and $B$ spans the entire space $V$ ; i.e. $V = span (B)$ .

Fact A. 6 (Properties of a basis). Suppose $B$ and $B^{'}$ are two bases for a linear space $V$ . Then:

$B$ and $B^{'}$ contain exactly the same number of linearly independent vectors. This number, say $n$ , is the dimension of the linear space $V$ .
Let $B = {b_{i}}_{i = 1}^{n}$ and $B^{'} = {b_{i}^{'}}_{i = 1}^{n}$ . Then each basis vector of $B$ can be expressed as a linear combination of those in $B^{'}$ ; i.e.

b_{j} = a_{1 j} b_{1}^{'} + a_{2 j} b_{2}^{'} + \dots + a_{n j} b_{n}^{'} = \sum_{i = 1}^{n} a_{i j} b_{i}^{'}, \tag A .2

for some $a_{i j} \in ℝ, i, j = 1, 2, \dots, n$ .

Any vector $v \in V$ can be written as a linear combination of vectors in either of the bases:

v = x_{1} b_{1} + x_{2} b_{2} + \dots + x_{n} b_{n} = x_{1}^{'} b_{1}^{'} + x_{2}^{'} b_{2}^{'} + \dots + x_{n}^{'} b_{n}^{'}, \tag A .3

where the coefficients ${x_{i} \in ℝ}_{i = 1}^{n}$ and ${x_{i}^{'} \in ℝ}_{i = 1}^{n}$ are uniquely determined and are called the coordinates of $v$ with respect to each basis.

In particular, if $B$ and $B^{'}$ are two bases for the linear space $ℝ^{n}$ , we may put the basis vectors as columns of two $n \times n$ matrices and also call them $B$ and $B^{'}$ , respectively:

B ≐ [b_{1}, b_{2}, \dots, b_{n}], B^{'} ≐ [b_{1}^{'}, b_{2}^{'}, \dots, b_{n}^{'}] \in ℝ^{n \times n} . \tag A .4

Then we can express the relationship between them in the matrix form $B = B^{'} A$ as

[b_{1}, b_{2}, \dots, b_{n}] = [b_{1}^{'}, b_{2}^{'}, \dots, b_{n}^{'}] [\begin{matrix} a_{11} & a_{12} & \dots & a_{1 n} \\ a_{21} & a_{22} & \dots & a_{2 n} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{n 1} & a_{n 2} & \dots & a_{n n} \end{matrix}] . \tag A .5

The role of the $n \times n$ matrix $A$ is to transform one basis $(B^{'})$ to the other $(B)$ . Since such a transformation can go the opposite way, the matrix $A$ must be invertible. So we can also write $B^{'} = B A^{- 1}$ .

If $v$ is a vector in $V$ , it can be expressed in terms of linear combinations of either basis as

v = x_{1} b_{1} + x_{2} b_{2} + \dots + x_{n} b_{n} = x_{1}^{'} b_{1}^{'} + x_{2}^{'} b_{2}^{'} + \dots + x_{n}^{'} b_{n}^{'} . \tag A .6

Thus, we have

v = [b_{1}, b_{2}, \dots, b_{n}] [\begin{matrix} x_{1} \\ x_{2} \\ ⋮ \\ x_{n} \end{matrix}] = [b_{1}^{'}, b_{2}^{'}, \dots, b_{n}^{'}] [\begin{matrix} a_{11} & a_{12} & \dots & a_{1 n} \\ a_{21} & a_{22} & \dots & a_{2 n} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{n 1} & a_{n 2} & \dots & a_{n n} \end{matrix}] [\begin{matrix} x_{1} \\ x_{2} \\ ⋮ \\ x_{n} \end{matrix}] .

Since the coordinates of $v$ with respect to $B^{'}$ are unique, we obtain the following transformation of coordinates of a vector from one basis to the other:

[\begin{matrix} x_{1}^{'} \\ x_{2}^{'} \\ ⋮ \\ x_{n}^{'} \end{matrix}] = [\begin{matrix} a_{11} & a_{12} & \dots & a_{1 n} \\ a_{21} & a_{22} & \dots & a_{2 n} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{n 1} & a_{n 2} & \dots & a_{n n} \end{matrix}] [\begin{matrix} x_{1} \\ x_{2} \\ ⋮ \\ x_{n} \end{matrix}] \tag A .7

Let $x = {[x_{1}, x_{2}, \dots, x_{n}]}^{T} \in ℝ^{n}$ and $x^{'} = {[x_{1}^{'}, x_{2}^{'}, \dots, x_{n}^{'}]}^{T} \in ℝ^{n}$ denote the two coordinate vectors. We may summarize in matrix form the relationships between two bases and coordinates with respect to the bases as

B^{'} = B A^{- 1}, x^{'} = A x . \tag A .8

Be aware of the difference in transforming bases from transforming coordinates!

A.1.2 Inner product and orthogonality

Definition A. 7 (Inner product). A function

⟨ \cdot, \cdot ⟩ : ℝ^{n} \times ℝ^{n} \to ℝ

is an inner product $^{3}$ if

$⟨ u, α v + β w ⟩ = α ⟨ u, v ⟩ + β ⟨ u, w ⟩, \forall α, β \in ℝ,$
$⟨ u, v ⟩ = ⟨ v, u ⟩$ ,
$⟨ v, v ⟩ \geq 0$ , and $⟨ v, v ⟩ = 0 \Leftrightarrow v = 0$ .

For each vector $v, \sqrt{⟨ v, v ⟩}$ is called its norm.

The inner product is also called a metric, since it can be used to measure length and angles.

For simplicity, a standard basis is often chosen for the vector space $ℝ^{n}$ as the set of vectors

e_{1} = {[1, 0, 0, \dots, 0]}^{T}, e_{2} = {[0, 1, 0, \dots, 0]}^{T}, e_{n} = {[0, 0, \dots, 0, 1]}^{T} . \tag A .9

The matrix $I = [e_{1}, e_{2}, \dots, e_{n}]$ with these vectors as columns is exactly the $n \times n$ identity matrix.

$^{3}$ In some literature, an inner product is also called a dot product, denoted by $u \cdot v$ . However, in this book, we will not use that name.

Definition A. 8 (Canonical inner product on $ℝ^{n}$ ). Given any two vectors $x = {[x_{1}, x_{2}, \dots, x_{n}]}^{T}$ and $y = {[y_{1}, y_{2}, \dots, y_{n}]}^{T}$ in $ℝ^{n}$ , we define the canonical inner product to be

⟨ x, y ⟩ ≐ x^{T} y = x_{1} y_{1} + x_{2} y_{2} + \dots + x_{n} y_{n} . \tag A .10

This inner product induces the standard 2-norm, or Euclidean norm, $∥ \cdot ∥_{2}$ , which measures the length of each vector as

∥ x ∥_{2} ≐ \sqrt{x^{T} x} = \sqrt{x_{1}^{2} + x_{2}^{2} + \dots + x_{n}^{2}} . \tag A .11

Notice that if we choose another basis $B^{'}$ related to the above standard basis $I$ as $I = B^{'} A$ , then the coordinates of the vectors $x, y$ related to the new basis are $x^{'}$ and $y^{'}$ , respectively, and they relate to $x, y$ by $x^{'} = A x$ and $y^{'} = A y$ . The inner product in terms of the new coordinates becomes

⟨ x, y ⟩ = x^{T} y = {(A^{- 1} x^{'})}^{T} (A^{- 1} y^{'}) = {(x^{'})}^{T} A^{- T} A^{- 1} (y^{'}) . \tag A .12

We denote this expression of the inner product with respect to the new basis by

{⟨ x^{'}, y^{'} ⟩}_{A^{- T} A^{- 1}} ≐ {(x^{'})}^{T} A^{- T} A^{- 1} (y^{'}) . \tag A .13

This is called an induced inner product from the matrix $A$ . Knowing the matrix $A^{- T} A^{- 1}$ , we can compute the canonical inner product directly using coordinates with respect to the nonstandard basis $B^{'}$ .

Definition A. 9 (Orthogonality). Two vectors $x, y$ are said to be orthogonal if their inner product is zero: $⟨ x, y ⟩ = 0$ . This is often indicated as $x ⊥ y$ .

A.1.3 Kronecker product and stack of matrices

Definition A. 10 (Kronecker product of two matrices). Given two matrices $A \in ℝ^{m \times n}$ and $B \in ℝ^{k \times l}$ , their Kronecker product, denoted by $A \otimes B$ , is a new matrix

A \otimes B ≐ [\begin{matrix} a_{11} B & a_{12} B & \dots & a_{1 n} B \\ a_{21} B & a_{22} B & \dots & a_{2 n} B \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{m 1} B & a_{m 2} B & \dots & a_{m n} B \end{matrix}] \in ℝ^{m k \times n l} . \tag A .14

If $A$ and $B$ are two vectors, i.e. $n = l = 1$ , the product $A \otimes B$ is also a vector but of dimension $m k$ .

In Matlab, one can easily compute the Kronecker product by using the command $C = kron (A, B)$ .

Definition A. 11 (Stack of a matrix). Given an $m \times n$ matrix $A \in ℝ^{m \times n}$ , the stack of the matrix $A$ is a vector, denoted by $A^{s}$ , in $ℝ^{m n}$ obtained by stacking its $n$ column vectors, say $a_{1}, a_{2}, \dots, a_{n} \in ℝ^{m}$ , in order:

A^{s} ≐ [\begin{matrix} a_{1} \\ a_{2} \\ ⋮ \\ a_{n} \end{matrix}] \in ℝ^{m n} . \tag A .15

As mutually inverse operations, $A^{s}$ is called $A$ "stacked," and $A$ is called $A^{s}$ "unstacked."

The Kronecker product and stack of matrices together allow us to rewrite algebraic equations that involve multiple vectors and matrices in many different but equivalent ways. For instance, the equation

u^{T} A v = 0 \tag A .16

for two vectors $u, v$ and a matrix $A$ of proper dimensions can be rewritten as

{(v \otimes u)}^{T} A^{s} = 0 . \tag A .17

The second equation is particularly useful when $A$ is the only unknown in the equation.

A.2 Linear transformations and matrix groups

Linear algebra studies the properties of the linear transformations, or linear maps, between different linear spaces. Since such transformations can be represented as matrices, linear algebra to a large extent studies the properties of matrices.

Definition A. 12 (Linear transformation). A linear transformation from a linear (vector) space $ℝ^{n}$ to $ℝ^{m}$ is defined as a map $L : ℝ^{n} \to ℝ^{m}$ such that

$L (x + y) = L (x) + L (y), \forall x, y \in ℝ^{n}$ ;
$L (α x) = α L (x), \forall x \in ℝ^{n}, α \in ℝ$ .

With respect to the standard bases of $ℝ^{n}$ and $ℝ^{m}$ , the map $L$ can be represented by a matrix $A \in ℝ^{m \times n}$ such that

L (x) = A x, \forall x \in ℝ^{n} . \tag A .18

The $i$ th column of the matrix $A$ is then nothing but the image of the standard basis vector $e_{i} \in ℝ^{n}$ under the map $L$ ; i.e.

A = [L (e_{1}), L (e_{2}), \dots, L (e_{n})] \in ℝ^{m \times n} .

The set of all (real) $m \times n$ matrices is denoted by $ℳ (m, n)$ . When viewed as a linear space, $ℳ (m, n)$ can be identified as the space $ℝ^{m n}$ . When there is little ambiguity, we refer to a linear map $L$ by its matrix representation $A$ . If $n = m$ , the set $ℳ (n, n) ≐ ℳ (n)$ forms an algebraic structure called a ring (over the field $ℝ$ ). That is, matrices in $ℳ (n)$ are closed under both matrix multiplication and summation: If $A, B$ are two $n \times n$ matrices, so are $C = A B$ and $D = A + B$ .

Linear maps or matrices that we encounter in computer vision often have a special algebraic structure called a group.

Definition A. 13 (Group). A group is a set $G$ with an operation " $\circ$ " on the elements of $G$ that:

is closed : If $g_{1}, g_{2} \in G$ , then also $g_{1} \circ g_{2} \in G$ ;
is associative: $(g_{1} \circ g_{2}) \circ g_{3} = g_{1} \circ (g_{2} \circ g_{3})$ , for all $g_{1}, g_{2}, g_{3} \in G$ ;
has a unit element $e : e \circ g = g \circ e = g$ , for all $g \in G$ ;
is invertible: For every element $g \in G$ , there exists an element $g^{- 1} \in G$ such that $g \circ g^{- 1} = g^{- 1} \circ g = e$ .

Definition A. 14 (The general linear group $G L (n)$ ). The set of all $n \times n$ nonsingular (real) matrices with matrix multiplication forms a group. Such a group of matrices is usually called the general linear group and denoted by $G L (n)$ .

Definition A. 15 (Matrix representation of a group). A group $G$ has a matrix representation or can be realized as a matrix group if there exists an injective $m a p^{4}$

ℛ : G \to G L (n); g \mapsto ℛ (g),

which preserves the group structure $^{5}$ of $G$ . That is, the inverse and composition of elements in $G$ are preserved by the map in the following way:

ℛ (e) = I_{n \times n}, ℛ (g \circ h) = ℛ (g) ℛ (h), \forall g, h \in G . \tag A .19

Below, we identify a few important subsets of $ℳ (n)$ that have special algebraic structures (as examples of matrix groups) and nice properties.

The group $G L (n)$ itself can be identified as the set of all invertible linear transformations from $ℝ^{n}$ to $ℝ^{n}$ in the sense that for every $A \in G L (n)$ , we obtain a linear map

L : ℝ^{n} \to ℝ^{n}; x \mapsto A x . \tag A .20

Notice that if $A \in G L (n)$ , then so is its inverse: $A^{- 1} \in G L (n)$ . We know that an $n \times n$ matrix $A$ is invertible if and only if its determinant is nonzero. Therefore, we have

det (A) \neq 0, \forall A \in G L (n) . \tag A .21

The general linear group, when matrices are considered to be known only up to a scalar factor, $G L (n) / ℝ$ , is referred to as the projective transformation group, whose elements are called projective matrices or homographies.

$^{4} A$ map $f (\cdot)$ is called injective if $f (x) \neq f (y)$ as long as $x \neq y$ .

$^{5}$ Such a map is called a group homomorphism in algebra.

Matrices in $G L (n)$ of determinant +1 form a subgroup called the special linear group, denoted by $S L (n)$ . That is, $det (A) = + 1$ for all $A \in S L (n)$ . It is easy to verify that if $A \in S L (n)$ , then so is $A^{- 1}$ , since $det (A^{- 1}) = det {(A)}^{- 1}$ .

Definition A. 16 (The affine group $A (n)$ ). An affine transformation $L$ from $ℝ^{n}$ to $ℝ^{n}$ is defined jointly by a matrix $A \in G L (n)$ and a vector $b \in ℝ^{n}$ such that

L : ℝ^{n} \to ℝ^{n}; x \mapsto A x + b . \tag A .22

The set of all such affine transformations is called the affine group of dimension $n$ and is denoted by $A (n)$ .

Notice that the map $L$ so-defined is not a linear map from $ℝ^{n}$ to $ℝ^{n}$ unless $b = 0$ . Nevertheless, we may "embed" this map into a space one dimension higher so that we can still represent it by a single matrix. If we identify an element $x \in ℝ^{n}$ with $[\begin{matrix} x \\ 1 \end{matrix}] \in ℝ^{n + 1},^{6}$ then $L$ becomes a map from $ℝ^{n + 1}$ to $ℝ^{n + 1}$ in the following sense:

L : ℝ^{n + 1} \to ℝ^{n + 1}; [\begin{matrix} x \\ 1 \end{matrix}] \mapsto [\begin{matrix} A & b \\ 0 & 1 \end{matrix}] [\begin{matrix} x \\ 1 \end{matrix}] . \tag A .23

Thus, a matrix of the form

[\begin{matrix} A & b \\ 0 & 1 \end{matrix}] \in ℝ^{(n + 1) \times (n + 1)}, A \in G L (n), b \in ℝ^{n}, \tag A .24

fully describes an affine map, and we call it an affine matrix. This matrix is an element in the general linear group $G L (n + 1)$ . In this way, $A (n)$ is identified as a subset (and in fact a subgroup) of $G L (n + 1)$ . The multiplication of two affine matrices in the set $A (n)$ is

[\begin{matrix} A_{1} & b_{1} \\ 0 & 1 \end{matrix}] [\begin{matrix} A_{2} & b_{2} \\ 0 & 1 \end{matrix}] = [\begin{matrix} A_{1} A_{2} & A_{1} b_{2} + b_{1} \\ 0 & 1 \end{matrix}] \in ℝ^{(n + 1) \times (n + 1)}, \tag A .25

which is also an affine matrix in $A (n)$ and represents the composition of two affine transformations.

Given $ℝ^{n}$ and its standard inner product structure, $⟨ x, y ⟩ = x^{T} y, \forall x, y \in ℝ^{n}$ , let us consider the set of linear transformations (or matrices) that preserve the inner product.

Definition A. 17 (The orthogonal group $O (n)$ ). An $n \times n$ matrix $A$ (representing a linear map from $ℝ^{n}$ to itself) is called orthogonal if it preserves the inner product, i.e.

⟨ A x, A y ⟩ = ⟨ x, y ⟩, \forall x, y \in ℝ^{n} . \tag A .26

The set of all $n \times n$ orthogonal matrices forms the orthogonal group of dimension $n$ , and it is denoted by $O (n)$ .

$^{6}$ This is the so-called homogeneous representation of $x$ . Notice that this identification does not preserve the vector structure of $ℝ^{n}$ .

Obviously, $O (n)$ is a subset (and in fact a subgroup) of $G L (n)$ . If $R$ is an orthogonal matrix, we must have $R^{T} R = R R^{T} = I$ . Therefore, the orthogonal group $O (n)$ can be characterized as

O (n) = {R \in G L (n) ∣ R^{T} R = I} . \tag A .27

The determinant $det (R)$ of an orthogonal matrix $R$ can be either +1 or -1 . The subgroup of $O (n)$ with determinant +1 is called the special orthogonal group and is denoted by $S O (n)$ . That is, for any $R \in S O (n)$ , we have $det (R) = + 1$ . Equivalently, one may define $S O (n)$ as the intersection $S O (n) = O (n) \cap S L (n)$ . In the case $n = 3$ , the special orthogonal matrices are exactly the $3 \times 3$ rotation matrices (studied in Chapter 2).

The affine version of the orthogonal group gives the Euclidean (transformation) group:

Definition A. 18 (The Euclidean group $E (n)$ ). A Euclidean transformation $L$ from $ℝ^{n}$ to $ℝ^{n}$ is defined jointly by a matrix $R \in O (n)$ and a vector $T \in ℝ^{n}$ such that

L : ℝ^{n} \to ℝ^{n}; x \mapsto R x + T . \tag A .28

The set of all such transformations is called the Euclidean group of dimension $n$ and is denoted by $E (n)$ .

Obviously, $E (n)$ is a subgroup of $A (n)$ . Therefore, it can also be embedded into a space one-dimension higher and has a matrix representation

[\begin{matrix} R & T \\ 0 & 1 \end{matrix}] \in ℝ^{(n + 1) \times (n + 1)}, R \in O (n), T \in ℝ^{n} . \tag A .29

If $R$ further belongs to $S O (n)$ , such transformations form the special Euclidean group, which is traditionally denoted by $S E (n)$ . When $n = 3, S E (3)$ represents the conventional rigid-body motion in $ℝ^{3}$ , where $R$ is the rotation of a rigid body and $T$ is the translation (with respect to a chosen reference coordinate frame).

Since all the transformation groups introduced so far have natural matrix representations, they are matrix groups. $^{7}$ To summarize their relationships, we have

S O (n) \subset O (n) \subset G L (n), S E (n) \subset E (n) \subset A (n) \subset G L (n + 1) . \tag A .30

A.3 Gram-Schmidt and the QR decomposition

A matrix in $G L (n)$ has $n$ independent rows (or columns). A matrix in $O (n)$ has orthonormal rows (or columns). The Gram-Schmidt procedure can be viewed as a map from $G L (n)$ to $O (n)$ , for it transforms a nonsingular matrix into an orthogonal one. Call $ℒ_{+} (n)$ the subset of $G L (n)$ consisting of lower triangular matrices with positive elements along the diagonal. Such matrices form a subgroup of $G L (n)$ .

$^{7}$ Since these groups themselves admit a differential structure, they belong to the Lie groups.

Theorem A.19 (Gram-Schmidt procedure). For every $A \in G L (n)$ , there exists a lower triangular matrix $L \in ℝ^{n \times n}$ and an orthogonal matrix $E \in O (n)$ such that

A = L E . \tag A .31

Proof. Contrary to the convention of the book, for simplicity in this proof all vectors indicate row vectors. That is, if $v$ is an $n$ -dimensional row vector, it is of the form: $v = [v_{1}, v_{2}, \dots, v_{n}] \in ℝ^{n}$ . Denote the $i$ th row vector of the given matrix $A$ by $a_{i}$ for $i = 1, 2, \dots, n$ . The proof consists in constructing $L$ and $E$ iteratively from the row vectors $a_{i}$ :

l_{1} ≐ a_{1} \to e_{1} ≐ l_{1} / {‖ \begin{matrix} l_{1} \end{matrix} ‖}_{2}

l_{2} ≐ a_{2} - ⟨ a_{2}, e_{1} ⟩ e_{1} \to e_{2} ≐ l_{2} / {‖ \begin{matrix} l_{2} \end{matrix} ‖}_{2}

⋮ ⋮ ⋮ ⋮

l_{n} ≐ a_{n} - \sum_{i = 1}^{n - 1} ⟨ a_{i + 1}, e_{i} ⟩ e_{i} \to e_{n} ≐ l_{n} / {‖ \begin{matrix} l_{n} \end{matrix} ‖}_{2}

Then $E = {[e_{1}^{T}, \dots, e_{n}^{T}]}^{T}$ , and the matrix $L$ is obtained as

L = [\begin{matrix} {‖ \begin{matrix} l_{1} \end{matrix} ‖}_{2} & 0 & \dots & 0 \\ ⟨ a_{2}, e_{1} ⟩ & {‖ \begin{matrix} l_{2} \end{matrix} ‖}_{2} & \dots & 0 \\ ⋮ & ⋱ & ⋱ & ⋮ \\ ⟨ a_{2}, e_{1} ⟩ & \dots & ⟨ a_{n}, e_{n - 1} ⟩ & {‖ \begin{matrix} l_{n} \end{matrix} ‖}_{2} \end{matrix}] .

By construction $E$ is orthogonal; i.e. $E E^{T} = E^{T} E = I$ .

Remark A.20. The Gram-Schmidt's procedure has the peculiarity of being causal, in the sense that the ith row of the transformed matrix $E$ depends only upon rows with index $j \leq i$ of the original matrix $A$ . The choice of the name $E$ for the orthogonal matrix above is not accidental. In fact, we will view the Kalman filter (to be reviewed in the next appendix) as a way to perform a Gram-Schmidt orthonormalization in a special Hilbert space, and the outcome $E$ of the procedure is traditionally called the innovation.

There are a few useful variations to Gram-Schmidt procedure. By transposing $A = L E$ , we get $A^{T} = E^{T} L^{T} ≐ Q R$ . Notice that $R = L^{T}$ is an upper triangular matrix. Thus, by applying Gram-Schmidt procedure to the transpose of a matrix, we can also decompose it into the form $Q R$ where $Q$ is an orthogonal matrix and $R$ an upper triangular matrix. Such a decomposition is called the $Q R$ decomposition. In Matlab, this can be done by the command $[Q, R] = qr (A)$ . Furthermore, by inverting $A^{T} = E^{T} L^{T}$ , we get $A^{- T} = L^{- T} E ≐ K E$ . Notice that $K = L^{- T}$ is still an upper triangular matrix. Thus, we can also decompose any matrix into the form of an upper triangular matrix followed by an orthogonal one. The latter one is the kind of "QR decomposition" we use in Chapter 6 for camera calibration.

A.4 Range, null space (kernel), rank and eigenvectors of a matrix

Let $A$ be a general $m \times n$ matrix that also conveniently represents a linear map from the vector space $ℝ^{n}$ to $ℝ^{m}$ .

Definition A. 21 (Range, span, null space, and kernel). Define the range or span of $A$ , denoted by range $(A)$ or span $(A)$ , to be the subspace of $ℝ^{m}$ such that $y \in range (A)$ if and only if $y = A x$ for some $x \in ℝ^{n}$ . Define the null space of $A$ , denoted by null $(A)$ , to be the subspace of $ℝ^{n}$ such that $x \in null (A)$ if and only if $A x = 0$ . When $A$ is viewed as an abstract linear map, null $(A)$ is also referred to as the kernel of the map, denoted by $\ker (A)$ .

Notice that the range of a matrix $A$ is exactly the span of all its column vectors; the null space of a matrix $A$ is exactly the set of vectors which are orthogonal to all its row vectors (for a definition of orthogonal vectors see Definition A.9). The notion of range or null space is useful whenever the solution to a linear equation of the form $A x = b$ is considered. In terms of range and null space, this equation will have a solution if $b \in range (A)$ and will have a unique solution only if $null (A) = \emptyset$ (the empty set).

In Matlab, the null space of a matrix $A$ can be computed using the command $Z$ = null(A).

Definition A. 22 (Rank of a matrix). The rank of a matrix is the dimension of its range:

rank (A) ≐ \dim (range (A)) . \tag A .32

Fact A.23 (Properties of matrix rank). For an arbitrary $m \times n$ matrix $A$ , its rank has the following properties:

$rank (A) = n - \dim (null (A))$ .
$0 \leq rank (A) \leq min {m, n}$ .
$rank (A)$ is equal to the maximum number of linearly independent column (or row) vectors of $A$ .
$rank (A)$ is the highest order of a nonzero minor $^{8}$ of $A$ .
Sylvester’s inequality: Let $B$ be an $n \times k$ matrix. Then $A B$ is an $m \times k$ matrix and

rank (A) + rank (B) - n \leq rank (A B) \leq min {rank (A), rank (B)} . \tag A .33

$^{8} A$ minor of order $k$ is the determinant of a $k \times k$ submatrix of $A$ .

For any nonsingular matrices $C \in ℝ^{m \times m}$ and $D \in ℝ^{n \times n}$ , we have

rank (A) = rank (C A D) . \tag A .34

In Matlab, the rank of a matrix $A$ is just rank (A) .

Definition A. 24 (Orthogonal complement to a subspace). Given a subspace $S$ of $ℝ^{n}$ , we define its orthogonal complement to be the subspace $S^{⊥} \subseteq ℝ^{n}$ such that $x \in S^{⊥}$ if and only if $x^{T} y = 0$ for all $y \in S$ . We write $ℝ^{n} = S \oplus S^{⊥}$ .

The notion of orthogonal complement is used in this book to define the "coim-age" of an image of a point or a line. Also, with respect to any linear map $A$ from $ℝ^{n}$ to $ℝ^{m}$ , the space $ℝ^{n}$ can be decomposed as a direct sum of two subspaces,

ℝ^{n} = null (A) \oplus null {(A)}^{⊥},

and $ℝ^{m}$ can be decomposed similarly as

ℝ^{m} = range (A) \oplus range {(A)}^{⊥} .

We also have the following not so obvious relationships:

Theorem A.25. Let $A$ be a linear map from $ℝ^{n}$ to $ℝ^{m}$ . Then:

(a) $null {(A)}^{⊥} = range (A^{T})$ ,

(b) $range {(A)}^{⊥} = null (A^{T})$ ,

(d) $range (A) = range (A A^{T})$ .

Proof. To prove part $c$ : null $(A A^{T}) = null (A^{T})$ , we have

$A A^{T} x = 0 \Rightarrow ⟨ x, A A^{T} x ⟩ = {‖ \begin{matrix} A^{T} x \end{matrix} ‖}^{2} = 0 \Rightarrow A^{T} x = 0$ , hence $null (A A^{T}) \subseteq null (A^{T})$ .
$A^{T} x = 0 \Rightarrow A A^{T} x = 0$ ; hence $null (A A^{T}) \supseteq null (A^{T})$ .

To prove part $d$ , $range (A A^{T}) = range (A)$ , we first need to prove that $ℝ^{n}$ is a direct sum of $range (A^{T})$ and $null (A)$ , i.e. part $a$ of the theorem. Part $b$ can then be proved similarly. We prove this by showing that a vector $x$ is in $null (A)$ if and only if it is orthogonal to $range (A^{T}) : x \in null (A) \Leftrightarrow ⟨ A x, y ⟩ = 0, \forall y \Leftrightarrow ⟨ x, A^{T} y ⟩ = 0, \forall y$ . Hence null $(A)$ is exactly the subspace that is the orthogonal complement to range $(A^{T})$ (denoted by range ${(A^{T})}^{⊥}$ ). Therefore, $ℝ^{n}$ is a direct sum of range $(A^{T})$ and null $(A)$ . Now to complete our proof of part $d$ , let ${Img}_{A} (S)$ denote the image of a subspace $S$ under the map $A$ . Then we have range $(A) = {Img}_{A} (ℝ^{n}) = {Img}_{A} (range (A^{T})) = range (A A^{T})$ (in the second equality we used the fact that $ℝ^{n}$ is a direct sum of $range (A^{T})$ and $null (A)$ ). These relations are depicted by Figure A.1.

In fact, the same result holds even if the domain of the linear map $A$ is replaced by an infinite-dimensional linear space with an inner product (i.e. $ℝ^{n}$ is replaced by a Hilbert space). In that case, this theorem is also known as the finite-rank operator fundamental lemma [Callier and Desoer, 1991]. We will later use this result to prove the singular value decomposition. But already it implies a result that is extremely useful in the study of multiple-view geometry:

Figure A.1. The orthogonal decomposition of the domain and codomain of a linear map $A$ .

Lemma A.26 (Rank reduction lemma). Let $A \in ℝ^{n \times n}$ be a matrix and let $W$ be a matrix of the form

W = [\begin{matrix} M & 0 \\ A B & A A^{T} \end{matrix}] \in ℝ^{(m + n) \times (k + n)} \tag A .35

for some matrices $M \in ℝ^{m \times k}$ and $B \in ℝ^{n \times k}$ . Then, regardless of what $B$ is, we always have

rank (M) = rank (W) - rank (A) . \tag A .36

The proof is easy using the fact range $(A B) \subseteq range (A) = range (A A^{T})$ with the second identity from the previous theorem, and we leave the rest of the proof to the reader as an exercise.

A linear map from $ℝ^{n}$ to itself is represented by a square $n \times n$ matrix $A$ . For such a map, we sometimes are interested in subspaces of $ℝ^{n}$ that are "invariant" under the map. $^{9}$ This notion turns out to be closely related to the eigenvectors of the matrix $A$ .

Definition A. 27 (Eigenvalues and eigenvectors of a matrix). Let $A$ be an $n \times n$ complex matrix $^{10}$ in $ℂ^{n \times n}$ . A nonzero vector $v \in ℂ^{n}$ is said to be its (right) eigenvector if

A v = λ v \tag A .37

for some scalar $λ \in ℂ; λ$ is called an eigenvalue of $A$ . Similarly, a nonzero row vector $η^{T} \in ℂ^{n}$ is called a left eigenvector of $A$ if $η^{T} A = λ η^{T}$ for some $λ \in ℂ$ .

$^{9}$ More rigorously speaking, a subspace $S \subset ℝ^{n}$ is $A$ -invariant if $A (S) \subseteq S$ .

$^{10}$ Although $A$ will mostly be a real matrix in this book, to talk about its eigenvectors, it is more convenient to think of it as a complex matrix (with all entries that happen to be real).

Unless otherwise stated, an eigenvector in this book by default means a right eigenvector. The set of all eigenvalues of a matrix $A$ is called its spectrum, denoted by $σ (A)$ . The Matlab command $[V, D] = eig (A)$ produces a diagonal matrix $D$ of eigenvalues and a full-rank matrix $V$ whose columns are the corresponding eigenvectors, so that $A V = V D$ .

We give the following facts about eigenvalues and eigenvectors of a matrix without a proof.

Fact A.28 (Properties of eigenvalues and eigenvectors). Given a matrix $A \in ℝ^{n \times n}$ , we have:

If $A v = λ v$ , then for the same eigenvalue $λ$ , there also exists a left eigenvector $η^{T}$ such that $η^{T} A = λ η^{T}$ and vice versa. Hence $σ (A) = σ (A^{T})$ .
The eigenvectors of $A$ associated with different eigenvalues are linearly independent.
All its eigenvalues $σ (A)$ are the roots of the (characteristic) polynomial equation $det (λ I - A) = 0$ . Hence $det (A)$ is equal to the product of all eigenvalues of $A$ .
If $B = P A P^{- 1}$ for some nonsingular matrix $P$ , then $σ (B) = σ (A)$ .
If $A$ is a real matrix, then $λ \in ℂ$ is an eigenvalue implies that its conjugate $\overset{―}{λ}$ is also an eigenvalue. Simply put, $σ (A) = \overset{―}{σ} (A)$ for real matrices.

A.5 Symmetric matrices and skew-symmetric matrices

Definition A.29 (Symmetric matrix). A matrix $S \in ℝ^{n \times n}$ is called symmetric if $S^{T} = S$ . A symmetric matrix $S$ is called positive (semi-)definite, if $x^{T} S x > 0$ (or $x^{T} S x \geq 0$ ) for all $x \in ℝ^{n}$ , denoted by $S > 0$ (or $S \geq 0$ ).

Fact A. 30 (Properties of symmetric matrices). If $S$ is a real symmetric matrix, then:

All eigenvalues of $S$ must be real, i.e. $σ (S) \subset ℝ$ .
Let $(λ, v)$ be an eigenvalue-eigenvector pair. If $λ_{i} \neq λ_{j}$ , then $v_{i} ⊥ v_{j}$ ; i.e. eigenvectors corresponding to distinct eigenvalues are orthogonal.
There always exist $n$ orthonormal eigenvectors of $S$ , which form a basis for $ℝ^{n}$ .
$S > 0 (S \geq 0)$ if $λ_{i} > 0 (λ_{i} \geq 0) \forall i = 1, 2, \dots, n$ ; i.e. $S$ is positive (semi-)definite if all eigenvalues are positive (nonnegative).
If $S \geq 0$ and $λ_{1} \geq λ_{2} \geq \dots \geq λ_{n}$ , then $max_{∥ x ∥_{2} = 1} ⟨ x, S x ⟩ = λ_{1}$ and $min_{∥ x ∥_{2} = 1} ⟨ x, S x ⟩ = λ_{n}$

From point 3, we see that if $V = [v_{1}, v_{2}, \dots, v_{n}] \in ℝ^{n \times n}$ is the matrix of all the eigenvectors, and $Λ = diag {λ_{1}, λ_{2}, \dots, λ_{n}}$ is the diagonal matrix of the corresponding eigenvalues, then we can write

S = V Λ V^{T},

where $V$ is an orthogonal matrix. In fact, $V$ can be further chosen to be in $S O (n)$ (i.e. of determinant +1) if $n$ is odd, since $V Λ V^{T} = (- V) Λ {(- V)}^{T}$ and $det (- V) = {(- 1)}^{n} det (V) .$

Definition A. 31 (Induced 2-norm of a matrix). Let $A \in ℝ^{m \times n}$ . We define the induced 2-norm of $A$ (as a linear map from $ℝ^{n}$ to $ℝ^{m}$ ) as

∥ A ∥_{2} ≐ max_{∥ x ∥_{2} = 1} ∥ A x ∥_{2} = max_{∥ x ∥_{2} = 1} \sqrt{⟨ x, A^{T} A x ⟩} .

Similarly, other induced operator norms on $A$ can be defined starting from different norms on the domain and codomain spaces on which $A$ operates.

Let $A$ be as above. Then $A^{T} A \in ℝ^{n \times n}$ is clearly symmetric and positive semidefinite, so it can be diagonalized by a orthogonal matrix $V$ . The eigenvalues, being nonnegative, can be written as $σ_{i}^{2}$ . By ordering the columns of $V$ so that the eigenvalue matrix $Λ$ has decreasing eigenvalues on the diagonal, we see, from point 5 of the preceding fact, that $A^{T} A = V diag {σ_{1}^{2}, σ_{2}^{2}, \dots, σ_{n}^{2}} V^{T}$ and

∥ A ∥_{2} = σ_{1} .

The induced 2-norm of a matrix $A \in ℝ^{m \times n}$ is different from the "2-norm" of $A$ viewed as a vector in $ℝ^{m n}$ . To distinguish them, the latter one is conventionally called the Frobenius norm of $A$ , precisely defined as $∥ A ∥_{f} = \sqrt{\sum_{i, j} a_{i j}^{2}}$ . Notice that $\sum_{i, j} a_{i j}^{2}$ is nothing but the trace of $A^{T} A$ (or $A A^{T}$ ). Thus, we have

∥ A ∥_{f} ≐ \sqrt{trace (A^{T} A)} = \sqrt{σ_{1}^{2} + σ_{2}^{2} + \dots + σ_{n}^{2}} .

The inverse problem of retrieving $A$ from the symmetric matrix $S = A^{T} A$ is usually solved by Cholesky factorization. For the given $S$ , its eigenvalues must be nonnegative. Thus, we have $S = V Λ V^{T} = A^{T} A$ for $A = Λ^{(\frac{1}{2})} V^{T}$ , where $Λ^{(\frac{1}{2})} = diag {σ_{1}, σ_{2}, \dots, σ_{n}}$ is the "square root" of the diagonal matrix $Λ$ . Since $R^{T} R = I$ for any orthogonal matrix, the solution for $A$ is not unique: $R A$ is also a solution. Cholesky factorization then restricts the solution to be an upper-triangular matrix (exactly what we need for camera calibration in Chapter 6). In Matlab, the Cholesky factorization is given by the command A = chol (S).

Definition A.32 (Skew-symmetric (or antisymmetric) matrix). A matrix $A \in ℝ^{n \times n}$ is called skew-symmetric (or antisymmetric) if $A^{T} = - A$ .

Fact A.33 (Properties of a skew-symmetric matrix). If $A$ is a real skew-symmetric matrix, then:

All eigenvalues of $A$ are either zero or purely imaginary, i.e. of the form $i ω$ for $i = \sqrt{- 1}$ and some $ω \in ℝ$ .
There exists an orthogonal matrix $V$ such that

A = V Λ V^{T}, \tag A .38

where $Λ$ is a block-diagonal matrix $Λ = diag {A_{1}, \dots, A_{m}, 0, \dots, 0}$ , where each $A_{i}$ is a $2 \times 2$ real skew-symmetric matrix of the form

A_{i} = [\begin{matrix} 0 & a_{i} \\ - a_{i} & 0 \end{matrix}] \in ℝ^{2 \times 2}, i = 1, 2, \dots, m . \tag A .39

From point 2, we conclude that the rank of any skew-symmetric matrix must be even. A commonly used skew-symmetric matrix in computer vision is associated with a vector $u \in ℝ^{3}$ , denoted by

\hat{u} = [\begin{matrix} 0 & - u_{3} & u_{2} \\ u_{3} & 0 & - u_{1} \\ - u_{2} & u_{1} & 0 \end{matrix}] \in ℝ^{3 \times 3} . \tag A .40

The reason for such a definition is that $\hat{u} v$ is equal to the conventional cross product $u \times v$ of two vectors in $ℝ^{3}$ . Then we have $rank (\hat{u}) = 2$ if $u \neq 0$ and the (left and right) null space of $\hat{u}$ is exactly spanned by the vector $u$ itself. That is, $\hat{u} u = 0$ and $u^{T} \hat{u} = 0$ . In other words, columns and rows of the matrix $\hat{u}$ are always orthogonal to $u$ .

Obviously, $A^{T} \hat{u} A$ is also a skew-symmetric matrix. Then $A^{T} \hat{u} A = \hat{v}$ for some $v \in ℝ^{3}$ . We want to know what the relationship between $v$ and $A, u$ is.

Fact A. 34 (Hat operator). If $A$ is a $3 \times 3$ matrix of determinant 1, then we have

A^{T} \hat{u} A = \overset{⏜}{A^{- 1} u} . \tag A .41

This is an extremely useful fact, which will be extensively used in our book. For example, this property allows us to "push" a matrix through a skew-symmetric matrix in the following way: $\hat{u} A = A^{- T} A^{T} \hat{u} A = A^{- T} \hat{A^{- 1} u}$ . We leave to the reader as an exercise to think about how this result needs to be modified when the determinant of $A$ is not 1, or when $A$ is not even invertible.

A.6 Lyapunov map and Lyapunov equation

An important type of linear equation that we will encounter in our book is of Lyapunov type: $^{11}$ Find a matrix $X \in ℂ^{n \times n}$ that satisfies the equation

A X + X B = 0 \tag A .42

for a given pair of matrices $A, B \in ℂ^{n \times n}$ . Although solutions to this type of equation can be difficult in general, simple solutions exist when both $A$ and $B$ have $n$ independent eigenvectors. Suppose ${u_{i} \in ℂ^{n}}_{i = 1}^{n}$ are the $n$ right eigenvectors of $A$ , and ${v_{j} \in ℂ^{n}}_{j = 1}^{n}$ are the $n$ left eigenvectors of $B$ ; i.e.

A u_{i} = λ_{i} u_{i}; v_{j}^{*} B = η_{j} v_{j}^{*} \tag A .43

$^{11}$ It is also called Sylvester equation in some literature.

for eigenvalues $λ_{i}, η_{j}$ for each $i, j$ . Here $v^{*}$ means the complex-conjugate and transpose of $v$ , since $v$ can be complex.

Fact A. 35 (Lyapunov map). For the above matrix $A$ and $B$ , the $n^{2}$ eigenvectors of the Lyapunov map

L : X \mapsto A X + X B \tag A .44

are exactly $X_{i j} = u_{i} v_{j}^{*} \in ℂ^{n \times n}$ , and the corresponding eigenvalues are $λ_{i} + η_{j} \in ℂ, i, j = 1, 2, \dots, n .$

Proof. The $n^{2}$ matrices ${X_{i j}}_{i, j = 1}^{n}$ are linearly independent, and they must be all the eigenvectors of $L$ .

Due to this fact, any matrix $X$ that satisfies the Lyapunov equation $A X + X B =$ 0 must be in the subspace spanned by eigenvectors $X_{i j}$ that have zero eigenvalues: $λ_{i} + η_{j} = 0$ . In Matlab, the command $X = lyap (A, B, C)$ solves the more general Lyapunov equation $A X + X B = - C$ .

In this book, we often look for solutions $X$ with extra requirements on its structure. For instance, $X$ needs to be real and symmetric (Chapter 6), or $X$ has to be a rotation matrix (Chapter 10). If so, we have only to take the intersection of the space of solutions to the Lyapunov equation with the space of symmetric matrices or rotation matrices.

A.7 The singular value decomposition (SVD)

The singular value decomposition (SVD) is a useful tool to capture essential features of a matrix (that represents a linear map), such as its rank, range space, null space, and induced norm, as well as to "generalize" the concept of "eigenvalue- eigenvector" pair to non-square matrices. The computation of the SVD is numerically well conditioned, making it extremely useful for solving many linear-algebraic problems such as matrix inversion, calculation of the rank, linear least-squares estimate, projections, and fixed-rank approximations. Since this book will use the SVD quite extensively, here we give a detailed proof of its properties.

A.7.1 Algebraic derivation

Given a matrix $A \in ℝ^{m \times n}$ , we have the following theorem.

Theorem A.36 (Singular value decomposition of a matrix). Let $A \in ℝ^{m \times n}$ have rank $p$ . Furthermore, suppose, without loss of generality, that $m \geq n$ . Then

$\exists U \in ℝ^{m \times p}$ whose columns are orthonormal,
$\exists V \in ℝ^{n \times p}$ whose columns are orthonormal, and
$\exists \sum \in ℝ^{p \times p}, \sum = diag {σ_{1}, σ_{2}, \dots, σ_{p}}$ diagonal with $σ_{1} \geq σ_{2} \geq \dots \geq σ_{p}$

such that $A = U \sum V^{T}$ .

Proof. We prove the claim by construction.

Compute $A^{T} A$ : it is symmetric and positive semi-definite of dimension $n \times n$ . Then order its eigenvalues in decreasing order and call them $σ_{1}^{2} \geq \dots \geq σ_{p}^{2} \geq \dots σ_{n}^{2} \geq 0$ . Call the $σ_{i}$ ’s singular values.
From an orthonormal set of eigenvectors of $A^{T} A$ create an orthonormal basis for $ℝ^{n}$ such that

span {v_{1}, v_{2}, \dots, v_{p}} = range (A^{T}), span {v_{p + 1}, \dots, v_{n}} = null (A) .

Note that the latter eigenvectors correspond to the zero singular values, since null $(A^{T} A) = null (A)$ (according to Theorem A.25).

Define $u_{i}$ such that $A v_{i} = σ_{i} u_{i}, \forall i = 1, 2, \dots, p$ , and see that the set ${u_{i}}_{i = 1}^{p}$ is orthonormal (proof left as exercise).
Complete the basis ${u_{i}}_{i = 1}^{p}$ , which spans range $(A)$ (by construction), to all $ℝ^{m}$ .
Then,

A [v_{1}, v_{2}, \dots, v_{n}] = [u_{1}, u_{2}, \dots, u_{m}] [\begin{matrix} σ_{1} & 0 & \dots & \dots & \dots & 0 \\ 0 & σ_{2} & \dots & \dots & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ & ⋮ & ⋮ \\ ⋮ & ⋮ & ⋮ & σ_{p} & ⋮ & ⋮ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & 0 & ⋮ & ⋮ & 0_{n} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & \dots & \dots & \dots & 0 \end{matrix}],

which we name $A \tilde{V} = \tilde{U} \sum^{~}$ .

Hence, $A = \tilde{U} \sum^{~} {\tilde{V}}^{T}$ .

Then the claim follows by deleting the columns of $\tilde{U}$ and the rows of ${\tilde{V}}^{T}$ that multiply the zero singular values.

In Matlab, to compute the SVD of a given $m \times n$ matrix $A$ , simply use the command $[U, S, V] = svd (A)$ , which returns matrices $U, S, V$ satisfying $A = U S V^{T}$ (where $S$ replaces $\sum$ ). Notice that in the standard SVD routine, the orthogonal matrices $U$ and $V$ do not necessarily have determinant +1 . So the reader should exercise extra caution when using the SVD to characterize the essential matrix in epipolar geometry in this book.

A.7.2 Geometric interpretation

Notice that in the SVD of a square matrix $A = U \sum V^{T} \in ℝ^{n \times n}$ , columns of $U = [u_{1}, u_{2}, \dots, u_{n}]$ and columns of $V = [v_{1}, v_{2}, \dots, v_{n}]$ form orthonormal bases for $ℝ^{n}$ . The SVD essentially states that if $A$ (as a linear map) maps a point $x$ to $y$ , then coordinates of $y$ with respect to the basis $U$ are related to coordinates of $x$ with respect to the basis $V$ by the diagonal matrix $\sum$ that scales each coordinate by the corresponding singular value.

Theorem A.37. Let $A \in ℝ^{n \times n} = U \sum V^{T}$ be a square matrix. Then $A$ maps the unit sphere $𝕊^{n - 1} ≐ {x \in ℝ^{n} : ∥ x ∥_{2} = 1}$ to an ellipsoid with semi-axes $σ_{i} u_{i}$ , where $u_{i}$ is the ith column of $U$ .

Proof. let $x, y$ be such that $A x = y$ . The set ${v_{i}}_{i = 1}^{n}$ is an orthonormal basis for $ℝ^{n}$ . With respect to such a basis $x$ has coordinates

{[α_{1}, α_{2}, \dots, α_{n}]}^{T} = {[⟨ v_{1}, x ⟩, ⟨ v_{2}, x ⟩, \dots, ⟨ v_{n}, x ⟩]}^{T} .

That is, $x = \sum_{i = 1}^{n} α_{i} v_{i}$ . With respect to the basis ${u_{i}}_{i = 1}^{n}, y$ has coordinates

{[β_{1}, β_{2}, \dots, β_{n}]}^{T} = {[⟨ u_{1}, y ⟩, ⟨ u_{2}, y ⟩, \dots, ⟨ u_{n}, y ⟩]}^{T} .

We also have $y = \sum_{i = 1}^{n} β_{i} u_{i} = A x = \sum_{i = 1}^{n} σ_{i} u_{i} v_{i}^{T} x = \sum_{i = 1}^{n} σ_{i} ⟨ v_{i}, x ⟩ u_{i}$ . Hence $σ_{i} α_{i} = β_{i}$ . Now $∥ x ∥_{2}^{2} = \sum_{i = 1} α_{i}^{2} = 1, \forall x \in 𝕊^{n - 1}$ , and so we have $\sum_{i = 1}^{n} β_{i}^{2} / σ_{i}^{2} = 1$ , which implies that the point $y$ satisfies the equation of an ellipsoid with semi-axes of length $σ_{i}$ . This is illustrated in Figure A. 2 for the case $n = 2$ .

A.7.3 Some properties of the SVD

Problems involving orthogonal projections onto invariant subspaces of $A$ , such as the linear least-squares (LLS) problem, can be easily solved using the SVD.

Definition A.38 (Generalized (Moore Penrose) inverse). Given a matrix $A \in ℝ^{m \times n}$ of rank $r$ with its SVD $A = U \sum V^{T}$ , we then define the generalized inverse of $A$ to be

A^{†} = V \sum^{†} U^{T}, where \sum^{†} = {[\begin{matrix} \sum_{1}^{- 1} & 0 \\ 0 & 0 \end{matrix}]}_{n \times m} .

The generalized inverse is sometimes also called the pseudo-inverse.

Figure A.2. The image of a unit sphere on the left under a nonsingular map $A \in ℝ^{2 \times 2}$ is an ellipsoid on the right.

In Matlab, the pseudo-inverse of a matrix is computed by the command X = pinv (A).

Fact A.39 (Properties of generalized inverse).

- A A^{†} A = A, A^{†} A A^{†} = A^{†} .

The generalized inverse can then be used to solve linear equations in general.

Proposition A.40 (Least-squares solution of a linear systems). Consider the problem $A x = b$ with $A \in ℝ^{m \times n}$ of rank $r \leq min (m, n)$ . The solution $x^{*}$ that minimizes $∥ A x - b ∥_{2}$ is given by $x^{*} = A^{†} b$ .

The following two results have something to do with the sensitivity of solving linear equations of the form $A x = b$ .

Proposition A.41 (Perturbations). Consider a nonsingular matrix $A \in ℝ^{n \times n}$ . Let $δ A$ be a full-rank perturbation. Then

- | σ_{k} (A + δ A) - σ_{k} (A) | \leq σ_{1} (δ A), \forall k = 1, 2, \dots, n,

- σ_{n} (A δ A) \geq σ_{n} (A) σ_{n} (δ A),

- σ_{1} (A^{- 1}) = \frac{1}{σ_{n} (A)},

where $σ_{i}$ denotes the ith singular value.

Proposition A.42 (Condition number). Consider the problem $A x = b$ , and consider a "perturbed" full-rank problem $(A + δ A) (x + δ x) = b$ . Since $A x = b$ , then to first-order approximation, $δ x = - A^{†} δ A x$ . Hence $∥ δ x ∥_{2} \leq {‖ \begin{matrix} A^{†} \end{matrix} ‖}_{2} ∥ δ A ∥_{2} ∥ x ∥_{2}$ , from which

\frac{∥ δ x ∥_{2}}{∥ x ∥_{2}} \leq {‖ \begin{matrix} A^{†} \end{matrix} ‖}_{2} ∥ A ∥_{2} \frac{∥ δ A ∥_{2}}{∥ A ∥_{2}} ≐ k (A) \frac{∥ δ A ∥_{2}}{∥ A ∥_{2}},

where $k (A) = {‖ \begin{matrix} A^{†} \end{matrix} ‖}_{2} ∥ A ∥_{2}$ is called the condition number of $A$ . It easy to see that $k (A) = σ_{1} / σ_{n}$ if $A$ is invertible.

Last but not the least, one of the most important properties of the SVD is related to a fixed-rank approximation of a given matrix. Given a matrix $A$ of rank $r$ , we want to find a matrix $B$ such that it has fixed rank $p < r$ and the Frobenius norm of the difference $∥ A - B ∥_{f}$ is minimal. The solution to this problem is given simply by setting all but the first $p$ singular values to zero

B ≐ U \sum_{(p)} V^{T},

where $\sum_{(p)}$ denotes the matrix obtained from $\sum$ by setting to zero its elements on the diagonal after the $p$ th entry. The matrix $B$ has exactly the same induced 2-norm of $A$ , i.e. $σ_{1} (A) = σ_{1} (B)$ , and satisfies the requirement on the rank.

Proposition A.43 (Fixed rank approximation). Let $A, B$ be defined as above. Then $∥ A - B ∥_{f}^{2} = σ_{p + 1}^{2} + \dots + σ_{r}^{2}$ . Furthermore, such a norm is the minimum achievable.

The proof is an easy exercise that follows directly from the properties of orthogonal projection and the properties of the SVD given above.