Singular Value Decompositions

Section 7.4 Singular Value Decompositions

The Spectral Theorem has motivated the past few sections. In particular, we applied the fact that symmetric matrices can be orthogonally diagonalized to simplify quadratic forms, which enabled us to use principal component analysis to reduce the dimension of a dataset.

🔗

But what can we do with matrices that are not symmetric or even square? For instance, the following matrices are not diagonalizable, much less orthogonally so:

🔗

[\begin{matrix} 2 & 1 \\ 0 & 2 \end{matrix}], [\begin{matrix} 1 & 1 & 0 \\ - 1 & 0 & 1 \end{matrix}] .

In this section, we will develop a description of matrices called the singular value decomposition that is, in many ways, analogous to an orthogonal diagonalization. For example, we have seen that any symmetric matrix can be written in the form

Q D Q^{T}

where

Q

is an orthogonal matrix and

D

is diagonal. A singular value decomposition will have the form

U Σ V^{T}

where

U

and

V

are orthogonal and

Σ

is diagonal. Most notably, we will see that every matrix has a singular value decomposition whether it’s symmetric or not.

🔗

Preview Activity 7.4.1.

Let’s review orthogonal diagonalizations and quadratic forms as our understanding of singular value decompositions will rely on them.

🔗

Suppose that $A$ is any matrix. Explain why the matrix $G = A^{T} A$ is symmetric.
Suppose that $A = [\begin{matrix} 1 & 2 \\ - 2 & - 1 \end{matrix}] .$ Find the matrix $G = A^{T} A$ and write out the quadratic form $q_{G} ([\begin{array}{r} x_{1} \\ x_{2} \end{array}])$ as a function of $x_{1}$ and $x_{2} .$
What is the maximum value of $q_{G} (x)$ over all unit vectors and in which direction does it occur?
xxxxxxxxxx
Language:
Messages
What is the minimum value of $q_{G} (x)$ over all unit vectors and in which direction does it occur?
What is the geometric relationship between the directions in which the maximum and minimum values occur?

🔗

Subsection 7.4.1 Finding singular value decompositions

We will begin by explaining what a singular value decomposition is and how we can find one for a given matrix

A .

🔗

Recall how the orthogonal diagonalization of a symmetric matrix is formed: if

A

is symmetric, we write

A = Q D Q^{T}

where the diagonal entries of

D

are the eigenvalues of

A

and the columns of

Q

are the associated eigenvectors. Moreover, the eigenvalues are related to the maximum and minimum values of the associated quadratic form

q_{A} (u)

among all unit vectors.

🔗

A general matrix, particularly a matrix that is not square, may not have eigenvalues and eigenvectors, but we can discover analogous features, called singular values and singular vectors, by studying a function somewhat similar to a quadratic form. More specifically, any matrix

A

defines a function

🔗

l_{A} (x) = | A x |,

which measures the length of

A x .

For example, the diagonal matrix

D = [\begin{matrix} 3 & 0 \\ 0 & - 2 \end{matrix}]

gives the function

l_{D} (x) = \sqrt{9 x_{1}^{2} + 4 x_{2}^{2}} .

The presence of the square root means that this function is not a quadratic form. We can, however, define the singular values and vectors by looking for the maximum and minimum of this function

l_{A} (u)

among all unit vectors

u .

🔗

While

l_{A} (x)

is not itself a quadratic form, it becomes one if we square it:

🔗

{(l_{A} (x))}^{2} = | A x |^{2} = (A x) \cdot (A x) = x \cdot (A^{T} A x) = q_{A^{T} A} (x) .

We call

G = A^{T} A,

the Gram matrix associated to

A

and note that

🔗

l_{A} (x) = \sqrt{q_{G} (x)} .

This is important in the next activity, which introduces singular values and singular vectors.

🔗

Activity 7.4.2.

The following interactive figure will help us explore singular values and vectors geometrically before we begin a more algebraic approach.

🔗

Instructions.

You may choose a

2 \times 2

matrix

A = [\begin{matrix} a & b \\ c & d \end{matrix}]

using the four sliders at the top of the diagram. On the left, you may vary the red unit vector

x

by clicking in the head of the vector.

Figure 7.4.1. Singular values, right singular vectors and left singular vectors

Select the matrix

A = [\begin{matrix} 1 & 2 \\ - 2 & - 1 \end{matrix}] .

As we vary the vector

x,

we see the vector

A x

on the right in gray while the height of the blue bar to the right tells us

l_{A} (x) = | A x | .

🔗

The first singular value $σ_{1}$ is the maximum value of $l_{A} (x)$ over all unit vectors and an associated right singular vector $v_{1}$ is a unit vector describing a direction in which this maximum occurs.

Use the diagram to find the first singular value $σ_{1}$ and an associated right singular vector $v_{1} .$
The second singular value $σ_{2}$ is the minimum value of $l_{A} (x)$ over all unit vectors and an associated right singular vector $v_{2}$ is a unit vector describing a direction in which this minimum occurs.

Use the diagram to find the second singular value $σ_{2}$ and an associated right singular vector $v_{2} .$
Here’s how we can find the right singular values and vectors without using the diagram. Remember that $l_{A} (x) = \sqrt{q_{G} (x)}$ where $G = A^{T} A$ is the Gram matrix associated to $A .$ Since $G$ is symmetric, it is orthogonally diagonalizable. Find $G$ and an orthogonal diagonalization of it.
xxxxxxxxxx
Language:
Messages
What is the maximum value of the quadratic form $q_{G} (x)$ among all unit vectors and in which direction does it occur? What is the minimum value of $q_{G} (x)$ and in which direction does it occur?
Because $l_{A} (x) = \sqrt{q_{G} (x)},$ the first singular value $σ_{1}$ will be the square root of the maximum value of $q_{G} (x)$ and $σ_{2}$ the square root of the minimum. Verify that the singular values that you found from the diagram are the square roots of the maximum and minimum values of $q_{G} (x) .$
Verify that the right singular vectors $v_{1}$ and $v_{2}$ that you found from the diagram are the directions in which the maximum and minimum values occur.
Finally, we introduce the left singular vectors $u_{1}$ and $u_{2}$ by requiring that $A v_{1} = σ_{1} u_{1}$ and $A v_{2} = σ_{2} u_{2} .$ Find the two left singular vectors.
xxxxxxxxxx
Language:
Messages
Form the matrices

$U = [\begin{matrix} u_{1} & u_{2} \end{matrix}], Σ = [\begin{matrix} σ_{1} & 0 \\ 0 & σ_{2} \end{matrix}], V = [\begin{matrix} v_{1} & v_{2} \end{matrix}]$

and explain why $A V = U Σ .$
Finally, explain why $A = U Σ V^{T}$ and verify that this relationship holds for this specific example.

🔗

As this activity shows, the singular values of

A

are the maximum and minimum values of

l_{A} (x) = | A x |

among all unit vectors and the right singular vectors

v_{1}

and

v_{2}

are the directions in which they occur. The key to finding the singular values and vectors is to utilize the Gram matrix

G

and its associated quadratic form

q_{G} (x) .

We will illustrate with some more examples.

🔗

Example 7.4.2.

We will find a singular value decomposition of the matrix

A = [\begin{matrix} 1 & 2 \\ - 1 & 2 \end{matrix}] .

Notice that this matrix is not symmetric so it cannot be orthogonally diagonalized.

🔗

We begin by constructing the Gram matrix

G = A^{T} A = [\begin{matrix} 2 & 0 \\ 0 & 8 \end{matrix}] .

Since

G

is symmetric, it can be orthogonally diagonalized with

🔗

D = [\begin{matrix} 8 & 0 \\ 0 & 2 \end{matrix}], Q = [\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}] .

🔗

We now know that the maximum value of the quadratic form

q_{G} (x)

is 8, which occurs in the direction

[\begin{array}{r} 0 \\ 1 \end{array}] .

Since

l_{A} (x) = \sqrt{q_{G} (x)},

this tells us that the maximum value of

l_{A} (x),

the first singular value, is

σ_{1} = \sqrt{8}

and that this occurs in the direction of the first right singular vector

v_{1} = [\begin{array}{r} 0 \\ 1 \end{array}] .

🔗

In the same way, we also know that the second singular value

σ_{2} = \sqrt{2}

with associated right singular vector

v_{2} = [\begin{array}{r} 1 \\ 0 \end{array}] .

🔗

The first left singular vector

u_{1}

is defined by

A v_{1} = [\begin{array}{r} 2 \\ 2 \end{array}] = σ_{1} u_{1} .

Because

σ_{1} = \sqrt{8},

we have

u_{1} = [\begin{array}{r} 1 / \sqrt{2} \\ 1 / \sqrt{2} \end{array}] .

Notice that

u_{1}

is a unit vector because

σ_{1} = | A v_{1} | .

🔗

In the same way, the second left singular vector is defined by

A v_{2} = [\begin{array}{r} 1 \\ - 1 \end{array}] = σ_{2} u_{2},

which gives us

u_{2} = [\begin{array}{r} 1 / \sqrt{2} \\ - 1 / \sqrt{2} \end{array}] .

🔗

We then construct

🔗

\begin{aligned} U & = [\begin{array}{c} u_{1} & u_{2} \end{array}] = [\begin{array}{c} 1 / \sqrt{2} & 1 / \sqrt{2} \\ 1 / \sqrt{2} & - 1 / \sqrt{2} \end{array}] \\ Σ & = [\begin{array}{c} σ_{1} & 0 \\ 0 & σ_{2} \end{array}] = [\begin{array}{c} \sqrt{8} & 0 \\ 0 & \sqrt{2} \end{array}] \\ V & = [\begin{array}{c} v_{1} & v_{2} \end{array}] = [\begin{array}{c} 0 & 1 \\ 1 & 0 \end{array}] \end{aligned}

🔗

We now have

A V = U Σ

because

🔗

A V = [\begin{matrix} A v_{1} & A v_{2} \end{matrix}] = [\begin{matrix} σ_{1} u_{1} & σ_{2} u_{2} \end{matrix}] = Σ U .

Because the right singular vectors, the columns of

V,

are eigenvectors of the symmetric matrix

G,

they form an orthonormal basis, which means that

V

is orthogonal. Therefore, we have

(A V) V^{T} = A = U Σ V^{T} .

This gives the singular value decomposition

🔗

A = [\begin{matrix} 1 & 2 \\ - 1 & 2 \end{matrix}] = [\begin{matrix} 1 / \sqrt{2} & 1 / \sqrt{2} \\ 1 / \sqrt{2} & - 1 / \sqrt{2} \end{matrix}] [\begin{matrix} \sqrt{8} & 0 \\ 0 & \sqrt{2} \end{matrix}] {[\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}]}^{T} = U Σ V^{T} .

🔗

To summarize, we find a singular value decomposition of a matrix

A

in the following way:

🔗

Construct the Gram matrix $G = A^{T} A$ and find an orthogonal diagonalization to obtain eigenvalues $λ_{i}$ and an orthonormal basis of eigenvectors.
The singular values of $A$ are the squares roots of eigenvalues $λ_{i}$ of $G;$ that is, $σ_{i} = \sqrt{λ_{i}} .$ By convention, the singular values are listed in decreasing order: $σ_{1} \geq σ_{2} \geq \dots .$ The right singular vectors $v_{i}$ are the associated eigenvectors of $G .$
The left singular vectors $u_{i}$ are found by $A v_{i} = σ_{i} u_{i} .$ Because $σ_{i} = | A v_{i} |,$ we know that $u_{i}$ will be a unit vector.

In fact, the left singular vectors will also form an orthonormal basis. To see this, suppose that the associated singular values are nonzero. We then have:

$\begin{aligned} σ_{i} σ_{j} (u_{i} \cdot u_{j}) & = (σ_{i} u_{i}) \cdot (σ_{j} u_{j}) = (A v_{i}) \cdot (A v_{j}) \\ = v_{i} \cdot (A^{T} A v_{j}) \\ = v_{i} \cdot (G v_{j}) = λ_{j} v_{i} \cdot v_{j} = 0 \end{aligned}$

since the right singular vectors are orthogonal.

🔗

Example 7.4.3.

Let’s find a singular value decomposition for the symmetric matrix

A = [\begin{matrix} 1 & 2 \\ 2 & 1 \end{matrix}] .

The associated Gram matrix is

🔗

G = A^{T} A = [\begin{matrix} 5 & 4 \\ 4 & 5 \end{matrix}],

which has an orthogonal diagonalization with

🔗

D = [\begin{matrix} 9 & 0 \\ 0 & 1 \end{matrix}], Q = [\begin{matrix} 1 / \sqrt{2} & 1 / \sqrt{2} \\ 1 / \sqrt{2} & - 1 / \sqrt{2} \end{matrix}] .

This gives singular values and vectors

🔗

\begin{aligned} σ_{1} = 3, & v_{1} = [\begin{array}{r} 1 / \sqrt{2} \\ 1 / \sqrt{2} \end{array}], & u_{1} = [\begin{matrix} 1 / \sqrt{2} \\ 1 / \sqrt{2} \end{matrix}] \\ σ_{2} = 1, & v_{2} = [\begin{array}{r} 1 / \sqrt{2} \\ - 1 / \sqrt{2} \end{array}], & u_{2} = [\begin{matrix} - 1 / \sqrt{2} \\ 1 / \sqrt{2} \end{matrix}] \end{aligned}

and the singular value decomposition

A = U Σ V^{T}

where

🔗

U = [\begin{matrix} 1 / \sqrt{2} & - 1 / \sqrt{2} \\ 1 / \sqrt{2} & 1 / \sqrt{2} \end{matrix}], Σ = [\begin{matrix} 3 & 0 \\ 0 & 1 \end{matrix}], V = [\begin{matrix} 1 / \sqrt{2} & 1 / \sqrt{2} \\ 1 / \sqrt{2} & - 1 / \sqrt{2} \end{matrix}] .

🔗

This example is special because

A

is symmetric. With a little thought, it’s possible to relate this singular value decomposition to an orthogonal diagonalization of

A

using the fact that

G = A^{T} A = A^{2} .

🔗

Activity 7.4.3.

In this activity, we will construct the singular value decomposition of

A = [\begin{matrix} 1 & 0 & - 1 \\ 1 & 1 & 1 \end{matrix}] .

Notice that this matrix is not square so there are no eigenvalues and eigenvectors associated to it.

🔗

Construct the Gram matrix $G = A^{T} A$ and find an orthogonal diagonalization of it.
xxxxxxxxxx
Language:
Messages
Identify the singular values of $A$ and the right singular vectors $v_{1},$ $v_{2},$ and $v_{3} .$ What is the dimension of these vectors? How many nonzero singular values are there?
Find the left singular vectors $u_{1}$ and $u_{2}$ using the fact that $A v_{i} = σ_{i} u_{i} .$ What is the dimension of these vectors? What happens if you try to find a third left singular vector $u_{3}$ in this way?
As before, form the orthogonal matrices $U$ and $V$ from the left and right singular vectors. What are the shapes of $U$ and $V ?$ How do these shapes relate to the number of rows and columns of $A ?$
Now form $Σ$ so that it has the same shape as $A :$

$Σ = [\begin{matrix} σ_{1} & 0 & 0 \\ 0 & σ_{2} & 0 \end{matrix}]$
and verify that $A = U Σ V^{T} .$
xxxxxxxxxx

Language:
Messages
How can you use this singular value decomposition of $A = U Σ V^{T}$ to easily find a singular value decomposition of $A^{T} = [\begin{matrix} 1 & 1 \\ 0 & 1 \\ - 1 & 1 \end{matrix}] ?$

🔗

Example 7.4.4.

We will find a singular value decomposition of the matrix

A = [\begin{matrix} 2 & - 2 & 1 \\ - 4 & - 8 & - 8 \end{matrix}] .

🔗

Finding an orthogonal diagonalization of

G = A^{T} A

gives

🔗

D = [\begin{matrix} 144 & 0 & 0 \\ 0 & 9 & 0 \\ 0 & 0 & 0 \end{matrix}], Q = [\begin{matrix} 1 / 3 & 2 / 3 & 2 / 3 \\ 2 / 3 & - 2 / 3 & 1 / 3 \\ 2 / 3 & 1 / 3 & - 2 / 3 \end{matrix}],

which gives singular values

σ_{1} = \sqrt{144} = 12,

σ_{2} = \sqrt{9} = 3,

and

σ_{3} = 0 .

The right singular vectors

v_{i}

appear as the columns of

Q

so that

V = Q .

🔗

We now find

🔗

\begin{aligned} A v_{1} = [\begin{matrix} 0 \\ - 12 \end{matrix}] = 12 u_{1}, & u_{1} = [\begin{array}{r} 0 \\ - 1 \end{array}] \\ A v_{2} = [\begin{matrix} 3 \\ 0 \end{matrix}] = 3 u_{1}, & u_{1} = [\begin{array}{r} 1 \\ 0 \end{array}] \\ A v_{3} = [\begin{matrix} 0 \\ 0 \end{matrix}] \end{aligned}

Notice that it’s not possible to find a third left singular vector since

A v_{3} = 0 .

We therefore form the matrices

🔗

U = [\begin{matrix} 0 & 1 \\ - 1 & 0 \end{matrix}], Σ = [\begin{matrix} 12 & 0 & 0 \\ 0 & 3 & 0 \end{matrix}], V = [\begin{matrix} 1 / 3 & 2 / 3 & 2 / 3 \\ 2 / 3 & - 2 / 3 & 1 / 3 \\ 2 / 3 & 1 / 3 & - 2 / 3 \end{matrix}],

which gives the singular value decomposition

A = U Σ V^{T} .

🔗

Notice that

U

is a

2 \times 2

orthogonal matrix because

A

has two rows, and

V

is a

3 \times 3

orthogonal matrix because

A

has three columns.

🔗

As we’ll see in the next section, some additional work may be needed to construct the left singular vectors

u_{j}

if more of the singular values are zero, but we won’t worry about that now. For the time being, let’s record our work in the following theorem.

🔗

Theorem 7.4.5. The singular value decomposition.

m \times n

matrix

A

may be written as

A = U Σ V^{T}

where

U

is an orthogonal

m \times m

matrix,

V

is an orthogonal

n \times n

matrix, and

Σ

is an

m \times n

matrix whose entries are zero except for the singular values of

A

which appear in decreasing order on the diagonal.

🔗

Notice that a singular value decomposition of

A

gives us a singular value decomposition of

A^{T} .

More specifically, if

A = U Σ V^{T},

then

🔗

A^{T} = (U Σ V^{T})^{T} = V Σ^{T} U^{T} .

🔗

Proposition 7.4.6.

A = U Σ V^{T},

then

A^{T} = V Σ^{T} U^{T} .

In other words,

A

and

A^{T}

share the same singular values, and the left singular vectors of

A

are the right singular vectors of

A^{T}

and vice-versa.

🔗

As we said earlier, a singular value decomposition should be thought of a generalization of an orthogonal diagonalization. For instance, the Spectral Theorem tells us that a symmetric matrix can be written as

Q D Q^{T} .

Many matrices, however, are not symmetric and so they are not orthogonally diagonalizable. However, every matrix has a singular value decomposition

U Σ V^{T} .

The price of this generalization is that we usually have two sets of singular vectors that form the orthogonal matrices

U

and

V

whereas a symmetric matrix has a single set of eignevectors that form the orthogonal matrix

Q .

🔗

Subsection 7.4.2 The structure of singular value decompositions

Now that we have an understanding of what a singular value decomposition is and how to construct it, let’s explore the ways in which a singular value decomposition reveals the underlying structure of the matrix. As we’ll see, the matrices

U

and

V

in a singular value decomposition provide convenient bases for some important subspaces, such as the column and null spaces of the matrix. This observation will provide the key to some of our uses of these decompositions in the next section.

🔗

Activity 7.4.4.

Let’s suppose that a matrix

A

has a singular value decomposition

A = U Σ V^{T}

where

🔗

U = [\begin{matrix} u_{1} & u_{2} & u_{3} & u_{4} \end{matrix}], Σ = [\begin{matrix} 20 & 0 & 0 \\ 0 & 5 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}], V = [\begin{matrix} v_{1} & v_{2} & v_{3} \end{matrix}] .

What is the shape of $A;$ that is, how many rows and columns does $A$ have?
Suppose we write a three-dimensional vector $x$ as a linear combination of right singular vectors:

$x = c_{1} v_{1} + c_{2} v_{2} + c_{3} v_{3} .$

We would like to find an expression for $A x .$

To begin, $V^{T} x = [\begin{array}{r} v_{1} \cdot x \\ v_{2} \cdot x \\ v_{3} \cdot x \end{array}] = [\begin{array}{r} c_{1} \\ c_{2} \\ c_{3} \end{array}] .$

Now $Σ V^{T} x = [\begin{matrix} 20 & 0 & 0 \\ 0 & 5 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}] [\begin{array}{r} c_{1} \\ c_{2} \\ c_{3} \end{array}] = [\begin{matrix} 20 c_{1} \\ 5 c_{2} \\ 0 \\ 0 \end{matrix}] .$

And finally, $A x = U Σ V^{T} x = [\begin{matrix} u_{1} & u_{2} & u_{3} & u_{4} \end{matrix}] [\begin{matrix} 20 c_{1} \\ 5 c_{2} \\ 0 \\ 0 \end{matrix}] = 20 c_{1} u_{1} + 5 c_{2} u_{2} .$

To summarize, we have $A x = 20 c_{1} u_{1} + 5 c_{2} u_{2} .$

What condition on $c_{1},$ $c_{2},$ and $c_{3}$ must be satisfied if $x$ is a solution to the equation $A x = 40 u_{1} + 20 u_{2} ?$ Is there a unique solution or infinitely many?
Remembering that $u_{1}$ and $u_{2}$ are linearly independent, what condition on $c_{1},$ $c_{2},$ and $c_{3}$ must be satisfied if $A x = 0 ?$
How do the right singular vectors $v_{i}$ provide a basis for $Nul (A),$ the subspace of solutions to the equation $A x = 0 ?$
Remember that $b$ is in $Col (A)$ if the equation $A x = b$ is consistent, which means that

$A x = 20 c_{1} u_{1} + 5 c_{2} u_{2} = b$

for some coefficients $c_{1}$ and $c_{2} .$ How do the left singular vectors $u_{i}$ provide an orthonormal basis for $Col (A) ?$
Remember that $rank (A)$ is the dimension of the column space. What is $rank (A)$ and how do the number of nonzero singular values determine $rank (A) ?$

🔗

This activity shows how a singular value decomposition of a matrix encodes important information about its null and column spaces. More specifically, the left and right singular vectors provide orthonormal bases for

Nul (A)

and

Col (A) .

This is one of the reasons that singular value decompositions are so useful.

🔗

Example 7.4.7.

Suppose we have a singular value decomposition

A = U Σ V^{T}

where

Σ = [\begin{matrix} σ_{1} & 0 & 0 & 0 & 0 \\ 0 & σ_{2} & 0 & 0 & 0 \\ 0 & 0 & σ_{3} & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix}] .

This means that

A

has four rows and five columns just as

Σ

does.

🔗

As in the activity, if

x = c_{1} v_{1} + c_{2} v_{2} + \dots + c_{5} v_{5},

we have

🔗

A x = σ_{1} c_{1} u_{1} + σ_{2} c_{2} u_{2} + σ_{3} c_{3} u_{3} .

🔗

b

is in

Col (A),

then

b

must have the form

🔗

b = σ_{1} c_{1} u_{1} + σ_{2} c_{2} u_{2} + σ_{3} c_{3} u_{3},

which says that

b

is a linear combination of

u_{1},

u_{2},

and

u_{3} .

These three vectors therefore form a basis for

Col (A) .

In fact, since they are columns in the orthogonal matrix

U,

they form an orthonormal basis for

Col (A) .

🔗

Remembering that

rank (A) = \dim Col (A),

we see that

rank (A) = 3,

which results from the three nonzero singular values. In general, the rank

r

of a matrix

A

equals the number of nonzero singular values, and

u_{1}, u_{2}, \dots, u_{r}

form an orthonormal basis for

Col (A) .

🔗

Moreover, if

x = c_{1} v_{1} + c_{2} v_{2} + \dots + c_{5} v_{5}

satisfies

A x = 0,

then

🔗

A x = σ_{1} c_{1} u_{1} + σ_{2} c_{2} u_{2} + σ_{3} c_{3} u_{3} = 0,

which implies that

c_{1} = 0,

c_{2} = 0,

and

c_{3} = 0 .

Therefore,

x = c_{4} v_{4} + c_{5} v_{5}

v_{4}

and

v_{5}

form an orthonormal basis for

Nul (A) .

🔗

More generally, if

A

is an

m \times n

matrix and if

rank (A) = r,

the last

n - r

right singular vectors form an orthonormal basis for

Nul (A) .

🔗

Generally speaking, if the rank of an

m \times n

matrix

A

r,

then there are

r

nonzero singular values and

Σ

has the form

🔗

[\begin{matrix} σ_{1} & \dots & 0 & \dots & 0 \\ 0 & \dots & 0 & \dots & 0 \\ 0 & \dots & σ_{r} & \dots & 0 \\ 0 & \dots & 0 & \dots & 0 \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & \dots & 0 & \dots & 0 \end{matrix}],

The first

r

columns of

U

form an orthonormal basis for

Col (A) :

🔗

U = [\underset{Col (A)}{\underset{⏟}{u_{1} \dots u_{r}}} u_{r + 1} \dots u_{m}]

and the last

n - r

columns of

V

form an orthonormal basis for

Nul (A) :

🔗

V = [v_{1} \dots v_{r} \underset{Nul (A)}{\underset{⏟}{v_{r + 1} \dots v_{n}}}]

🔗

Remember that Proposition 7.4.6 says that

A

and its transpose

A^{T}

share the same singular values. Since the rank of a matrix equals its number of nonzero singular values, this means that

rank (A) = rank (A^{T}),

a fact that we cited back in Section 6.2.

🔗

Proposition 7.4.8.

For any matrix

A,

🔗

rank (A) = rank (A^{T}) .

🔗

If we have a singular value decomposition of an

m \times n

matrix

A = U Σ V^{T},

Proposition 7.4.6 also tells us that the left singular vectors of

A

are the right singular vectors of

A^{T} .

Therefore,

U

is the

m \times m

matrix whose columns are the right singular vectors of

A^{T} .

This means that the last

m - r

vectors form an orthonormal basis for

Nul (A^{T}) .

Therefore, the columns of

U

provide orthonormal bases for

Col (A)

and

Nul (A^{T}) :

🔗

U = [\underset{Col (A)}{\underset{⏟}{u_{1} \dots u_{r}}} \underset{Nul (A^{T})}{\underset{⏟}{u_{r + 1} \dots u_{m}}}] .

This reflects the familiar fact that

Nul (A^{T})

is the orthogonal complement of

Col (A) .

🔗

In the same way,

V

is the

n \times n

matrix whose columns are the left singular vectors of

A^{T},

which means that the first

r

vectors form an orthonormal basis for

Col (A^{T}) .

Because the columns of

A^{T}

are the rows of

A,

this subspace is sometimes called the row space of

A

and denoted

Row (A) .

While we have yet to have an occasion to use

Row (A),

there are times when it is important to have an orthonormal basis for it, and a singular value decomposition provides just that. To summarize, the columns of

V

provide orthonormal bases for

Col (A^{T})

and

Nul (A) :

🔗

V = [\underset{Col (A^{T})}{\underset{⏟}{v_{1} \dots v_{r}}} \underset{Nul (A)}{\underset{⏟}{v_{r + 1} \dots v_{n}}}]

🔗

Considered altogether, the subspaces

Col (A),

Nul (A),

Col (A^{T}),

and

Nul (A^{T})

are called the four fundamental subspaces associated to

A .

In addition to telling us the rank of a matrix, a singular value decomposition gives us orthonormal bases for all four fundamental subspaces.

🔗

Theorem 7.4.9.

Suppose

A

is an

m \times n

matrix having a singular value decomposition

A = U Σ V^{T} .

Then

🔗

$r = rank (A)$ is the number of nonzero singular values.
The columns $u_{1}, u_{2}, \dots, u_{r}$ form an orthonormal basis for $Col (A) .$
The columns $u_{r + 1}, \dots, u_{m}$ form an orthonormal basis for $Nul (A^{T}) .$
The columns $v_{1}, v_{2}, \dots, v_{r}$ form an orthonormal basis for $Col (A^{T}) .$
The columns $v_{r + 1}, \dots, v_{n}$ form an orthonormal basis for $Nul (A) .$

🔗

When we previously outlined a procedure for finding a singular decomposition of an

m \times n

matrix

A,

we found the left singular vectors

u_{j}

using the expression

A v_{j} = σ_{j} u_{j} .

This produces left singular vectors

u_{1}, u_{2}, \dots, u_{r},

where

r = rank (A) .

r < m,

however, we still need to find the left singular vectors

u_{r + 1}, \dots, u_{m} .

Theorem 7.4.9 tells us how to do that: because those vectors form an orthonormal basis for

Nul (A^{T}),

we can find them by solving

A^{T} x = 0

to obtain a basis for

Nul (A^{T})

and applying the Gram-Schmidt algorithm.

🔗

We won’t worry about this issue too much, however, as we will frequently use software to find singular value decompositions for us.

🔗

Subsection 7.4.3 Reduced singular value decompositions

As we’ll see in the next section, there are times when it is helpful to express a singular value decomposition in a slightly different form.

🔗

Activity 7.4.5.

Suppose we have a singular value decomposition

A = U Σ V^{T}

where

🔗

U = [\begin{matrix} u_{1} & u_{2} & u_{3} & u_{4} \end{matrix}], Σ = [\begin{matrix} 18 & 0 & 0 \\ 0 & 4 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}], V = [\begin{matrix} v_{1} & v_{2} & v_{3} \end{matrix}] .

What is the shape of $A ?$ What is $rank (A) ?$
Identify bases for $Col (A)$ and $Col (A^{T}) .$
Explain why

$U Σ = [\begin{matrix} u_{1} & u_{2} \end{matrix}] [\begin{matrix} 18 & 0 & 0 \\ 0 & 4 & 0 \end{matrix}] .$
Explain why

$[\begin{matrix} 18 & 0 & 0 \\ 0 & 4 & 0 \end{matrix}] V^{T} = [\begin{matrix} 18 & 0 \\ 0 & 4 \end{matrix}] {[\begin{matrix} v_{1} & v_{2} \end{matrix}]}^{T} .$
If $A = U Σ V^{T},$ explain why $A = U_{r} Σ_{r} V_{r}^{T}$ where the columns of $U_{r}$ are an orthonormal basis for $Col (A),$ $Σ_{r}$ is a square, diagonal, invertible matrix, and the columns of $V_{r}$ form an orthonormal basis for $Col (A^{T}) .$

🔗

We call this a reduced singular value decomposition.

🔗

Proposition 7.4.10. Reduced singular value decomposition.

A

is an

m \times n

matrix having rank

r,

then

A = U_{r} Σ_{r} V_{r}^{T}

where

🔗

$U_{r}$ is an $m \times r$ matrix whose columns form an orthonormal basis for $Col (A),$
$Σ_{r} = [\begin{matrix} σ_{1} & 0 & \dots & 0 \\ 0 & σ_{2} & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & 0 & σ_{r} \end{matrix}]$ is an $r \times r$ diagonal, invertible matrix, and
$V_{r}$ is an $n \times r$ matrix whose columns form an orthonormal basis for $Col (A^{T}) .$

🔗

Example 7.4.11.

In Example 7.4.4, we found the singular value decomposition

🔗

A = [\begin{matrix} 2 & - 2 & 1 \\ - 4 & - 8 & - 8 \end{matrix}] = [\begin{matrix} 0 & 1 \\ - 1 & 0 \end{matrix}] [\begin{matrix} 12 & 0 & 0 \\ 0 & 3 & 0 \end{matrix}] {[\begin{matrix} 1 / 3 & 2 / 3 & 2 / 3 \\ 2 / 3 & - 2 / 3 & 1 / 3 \\ 2 / 3 & 1 / 3 & - 2 / 3 \end{matrix}]}^{T} .

Since there are two nonzero singular values,

rank (A) = 2

so that the reduced singular value decomposition is

🔗

A = [\begin{matrix} 2 & - 2 & 1 \\ - 4 & - 8 & - 8 \end{matrix}] = [\begin{matrix} 0 & 1 \\ - 1 & 0 \end{matrix}] [\begin{matrix} 12 & 0 \\ 0 & 3 \end{matrix}] {[\begin{matrix} 1 / 3 & 2 / 3 \\ 2 / 3 & - 2 / 3 \\ 2 / 3 & 1 / 3 \end{matrix}]}^{T} .

🔗

Subsection 7.4.4 Summary

This section has explored singular value decompositions, how to find them, and how they organize important information about a matrix.

🔗

A singular value decomposition of a matrix $A$ is a factorization where $A = U Σ V^{T} .$ The matrix $Σ$ has the same shape as $A,$ and its only nonzero entries are the singular values of $A,$ which appear in decreasing order on the diagonal. The matrices $U$ and $V$ are orthogonal and contain the left and right singular vectors, respectively, as their columns.
To find a singular value decomposition of a matrix, we construct the Gram matrix $G = A^{T} A,$ which is symmetric. The singular values of $A$ are the square roots of the eigenvalues of $G,$ and the right singular vectors $v_{j}$ are the associated eigenvectors of $G .$ The left singular vectors $u_{j}$ are determined from the relationship $A v_{j} = σ_{j} u_{j} .$
A singular value decomposition reveals fundamental information about a matrix. For instance, the number of nonzero singular values is the rank $r$ of the matrix. The first $r$ left singular vectors form an orthonormal basis for $Col (A)$ with the remaining left singular vectors forming an orthonormal basis of $Nul (A^{T}) .$ The first $r$ right singular vectors form an orthonormal basis for $Col (A^{T})$ while the remaining right singular vectors form an orthonormal basis of $Nul (A) .$
If $A$ is a rank $r$ matrix, we can write a reduced singular value decomposition as $A = U_{r} Σ_{r} V_{r}^{T}$ where the columns of $U_{r}$ form an orthonormal basis for $Col (A),$ the columns of $V_{r}$ form an orthonormal basis for $Col (A^{T}),$ and $Σ_{r}$ is an $r \times r$ diagonal, invertible matrix.

🔗

Exercises 7.4.5 Exercises

1.

Consider the matrix

A = [\begin{matrix} 1 & 2 & 1 \\ 0 & - 1 & 2 \end{matrix}] .

xxxxxxxxxx
 
​

🔗

Find the Gram matrix $G = A^{T} A$ and use it to find the singular values and right singular vectors of $A .$
Find the left singular vectors.
Form the matrices $U,$ $Σ,$ and $V$ and verify that $A = U Σ V^{T} .$
What is $rank (A)$ and what does this say about $Col (A) ?$
Determine an orthonormal basis for $Nul (A) .$

🔗

2.

Find singular value decompositions for the following matrices:

🔗

$[\begin{matrix} 0 & 0 \\ 0 & - 8 \end{matrix}] .$
$[\begin{matrix} 2 & 3 \\ 0 & 2 \end{matrix}] .$
$[\begin{matrix} 4 & 0 & 0 \\ 0 & 0 & 2 \end{matrix}]$
$[\begin{matrix} 4 & 0 \\ 0 & 0 \\ 0 & 2 \end{matrix}]$

🔗

3.

Consider the matrix

A = [\begin{matrix} 2 & 1 \\ 1 & 2 \end{matrix}] .

🔗

Find a singular value decomposition of $A$ and verify that it is also an orthogonal diagonalization of $A .$
If $A$ is a symmetric, positive semidefinite matrix, explain why a singular value decomposition of $A$ is an orthogonal diagonalization of $A .$

🔗

4.

Suppose that the matrix

A

has the singular value decomposition

🔗

[\begin{matrix} - 0.46 & 0.52 & 0.46 & 0.55 \\ - 0.82 & 0.00 & - 0.14 & - 0.55 \\ - 0.04 & 0.44 & - 0.85 & 0.28 \\ - 0.34 & - 0.73 & - 0.18 & 0.55 \end{matrix}] [\begin{matrix} 6.2 & 0.0 & 0.0 \\ 0.0 & 4.1 & 0.0 \\ 0.0 & 0.0 & 0.0 \\ 0.0 & 0.0 & 0.0 \end{matrix}] [\begin{matrix} - 0.74 & 0.62 & - 0.24 \\ 0.28 & 0.62 & 0.73 \\ - 0.61 & - 0.48 & 0.64 \end{matrix}] .

What are the dimensions of $A ?$
What is $rank (A) ?$
Find orthonormal bases for $Col (A),$ $Nul (A),$ $Col (A^{T}),$ and $Nul (A^{T}) .$
Find the orthogonal projection of $b = [\begin{array}{r} 1 \\ 0 \\ 2 \\ - 1 \end{array}]$ onto $Col (A) .$

🔗

5.

Consider the matrix

A = [\begin{matrix} 1 & 0 & - 1 \\ 2 & 2 & 0 \\ - 1 & 1 & 2 \end{matrix}] .

xxxxxxxxxx
 
​

🔗

Construct the Gram matrix $G$ and use it to find the singular values and right singular vectors $v_{1},$ $v_{2},$ and $v_{3}$ of $A .$ What are the matrices $Σ$ and $V$ in a singular value decomposition?
What is $rank (A) ?$
Find as many left singular vectors $u_{j}$ as you can using the relationship $A v_{j} = σ_{j} u_{j} .$
Find an orthonormal basis for $Nul (A^{T})$ and use it to construct the matrix $U$ so that $A = U Σ V^{T} .$
State an orthonormal basis for $Nul (A)$ and an orthonormal basis for $Col (A) .$

🔗

6.

Consider the matrix

B = [\begin{matrix} 1 & 0 \\ 2 & - 1 \\ 1 & 2 \end{matrix}]

and notice that

B = A^{T}

where

A

is the matrix in Exercise 7.4.5.1.

xxxxxxxxxx
 
​

🔗

Use your result from Exercise 7.4.5.1 to find a singular value decomposition of $B = U Σ V^{T} .$
What is $rank (B) ?$ Determine a basis for $Col (B)$ and $Col (B)^{⊥} .$
Suppose that $b = [\begin{array}{r} - 3 \\ 4 \\ 7 \end{array}] .$ Use the bases you found in the previous part of this exercise to write $b = \hat{b} + b^{⊥},$ where $\hat{b}$ is in $Col (B)$ and $b^{⊥}$ is in $Col (B)^{⊥} .$
Find the least-squares approximate solution to the equation $B x = b .$

🔗

7.

Suppose that

A

is a square

m \times m

matrix with singular value decomposition

A = U Σ V^{T} .

🔗

If $A$ is invertible, find a singular value decomposition of $A^{- 1} .$
What condition on the singular values must hold for $A$ to be invertible?
How are the singular values of $A$ and the singular values of $A^{- 1}$ related to one another?
How are the right and left singular vectors of $A$ related to the right and left singular vectors of $A^{- 1} ?$

🔗

8.

If $Q$ is an orthogonal matrix, remember that $Q^{T} Q = I .$ Explain why $det Q = \pm 1 .$
If $A = U Σ V^{T}$ is a singular value decomposition of a square matrix $A,$ explain why $| det A |$ is the product of the singular values of $A .$
What does this say about the singular values of $A$ if $A$ is invertible?

🔗

9.

A

is a matrix and

G = A^{T} A

its Gram matrix, remember that

🔗

x \cdot (G x) = x \cdot (A^{T} A x) = (A x) \cdot (A x) = {| A x |}^{2} .

For a general matrix $A,$ explain why the eigenvalues of $G$ are nonnegative.
Given a symmetric matrix $A$ having an eigenvalue $λ,$ explain why $λ^{2}$ is an eigenvalue of $G .$
If $A$ is symmetric, explain why the singular values of $A$ equal the absolute value of its eigenvalues: $σ_{j} = | λ_{j} | .$

🔗

10.

Determine whether the following statements are true or false and explain your reasoning.

🔗

If $A = U Σ V^{T}$ is a singular value decomposition of $A,$ then $G = V (Σ^{T} Σ) V^{T}$ is an orthogonal diagonalization of its Gram matrix.
If $A = U Σ V^{T}$ is a singular value decomposition of a rank 2 matrix $A,$ then $v_{1}$ and $v_{2}$ form an orthonormal basis for the column space $Col (A) .$
If $A$ is a symmetric matrix, then its set of singular values is the same as its set of eigenvalues.
If $A$ is a $10 \times 7$ matrix and $σ_{7} = 4,$ then the columns of $A$ are linearly independent.
The Gram matrix is always orthogonally diagonalizable.

🔗

11.

Suppose that

A = U Σ V^{T}

is a singular value decomposition of the

m \times n

matrix

A .

σ_{1}, \dots, σ_{r}

are the nonzero singular values, the general form of the matrix

Σ

🔗

Σ = [\begin{matrix} σ_{1} & \dots & 0 & \dots & 0 \\ 0 & \dots & 0 & \dots & 0 \\ 0 & \dots & σ_{r} & \dots & 0 \\ 0 & \dots & 0 & \dots & 0 \\ 0 & ⋮ & 0 & ⋮ & 0 \\ 0 & \dots & 0 & \dots & 0 \end{matrix}] .

If you know that the columns of $A$ are linearly independent, what more can you say about the form of $Σ ?$
If you know that the columns of $A$ span $R^{m},$ what more can you say about the form of $Σ ?$
If you know that the columns of $A$ are linearly independent and span $R^{m},$ what more can you say about the form of $Σ ?$

🔗

You have attempted 1 of 1 activities on this page.

🔗

Prev Top Next