MATRIX FACTORIZATIONS

 A factorization of a matrix A is an equation that

expresses A as a product of two or more matrices.
 Whereas matrix multiplication involves a synthesis of
data (combining the effects of two or more linear
transformations into a single matrix), matrix
factorization is an analysis of data.
THE LU FACTORIZATION
 The LU factorization is motivated by the fairly common
industrial and business problem of solving a sequence of
equations, all with the same coefficient matrix:
𝐴𝐱 = 𝐛1, 𝐴𝐱 = 𝐛2, … , 𝐴𝐱 = 𝐛𝑝 (1)
 When A is invertible, one could compute A-1 and then
compute A-1b1, A-1b2, and so on.
 However, it is more efficient to solve the first equation in
the sequence (1) by row reduction and obtain the LU
factorization of A at the same time. Thereafter, the
remaining equations in sequence (1) are solved with the
LU factorization.
THE LU FACTORIZATION
 Assume that A is an 𝑚 × 𝑛 matrix that can be row
reduced to echelon form, without row interchanges.
 Then A can be written in the form A = LU, were L is an
𝑚 × 𝑚 lower triangular matrix with 1’s on the diagonal
and U is an 𝑚 × 𝑛 echelon form of A.
 For instance, see Fig. below. Such a factorization is
called an LU factorization of A. The matrix L is
invertible and is called a unit lower triangular matrix.
THE LU FACTORIZATION
 Why is LU factorization useful?
 When A = LU, the equation Ax = b can be written as
L(Ux) = b.
 Writing y for Ux, we can find x by solving the pair of
equations
Ly = b
Ux = y

 First solve Ly = b for y, and then solve Ux = y for x. See

Fig. on the next slide. Each equation is easy to solve
because L and U are triangular.
THE LU FACTORIZATION

 Example 1 It can be verified that

−9
5
 Use this factorization of A to solve Ax=b, where 𝐛=
7
11
THE LU FACTORIZATION
 Solution The solution of Ly = b needs only 6
multiplications and 6 additions, because the arithmetic
takes place only in column 5.

 Then, for Ux = y, the “backward” phase of row

reduction requires 4 divisions, 6 multiplications, and 6
additions.

© 2016 Pearson Education, Ltd. Slide 2.5- 6

THE LU FACTORIZATION
 For instance, creating the zeros in column 4 of [U y]
requires 1 division in row 4 and 3 multiplication-
addition pairs to add multiples of row 4 to the rows
above.

 To find x requires 28 arithmetic operations, or “flops”

(floating point operations), excluding the cost of finding
L and U. In contrast, row reduction of [A b] to [I x]
takes 62 operations.
 AN LU FACTORIZATION ALGORITHM
 Suppose A can be reduced to an echelon form U using only row
replacements that add a multiple of one row to another below it.
 In this case, there exist unit lower triangular elementary
matrices E1 ,…, Ep such that
𝐸 𝑝 … 𝐸 1𝐴 = 𝑈
 Then
𝐴 = 𝐸𝑝 … 𝐸1 −1𝑈 = 𝐿𝑈 (3)
 where
𝐿 = 𝐸𝑝 … 𝐸1 -1 (4)
 It can be shown that products and inverses of unit lower
triangular matrices are also unit lower triangular. Thus L is unit
lower triangular.
 AN LU FACTORIZATION ALGORITHM
 Note that row operations in equation (3), which reduce A
to U, also reduce the L in equation (4) to I, because
𝐸𝑝 … 𝐸1𝐿 = 𝐸𝑝 … 𝐸1 𝐸𝑝 … 𝐸1 −1 = 𝐼 .
 This observation is the key to constructing L.

Algorithm for an LU Factorization

1. Reduce A to an echelon form U by a sequence of row
replacement operations, if possible.
2. Place entries in L such that the same sequence of row
operations reduces L to I.
 AN LU FACTORIZATION ALGORITHM
 Step 1 is not always possible, but when it is, the argument
above shows that an LU factorization exists.
 Example 2 on the following slides will show how to
implement step 2. By construction, L will satisfy
(𝐸𝑝 ⋯ 𝐸1)L = I
 using the same 𝐸𝑝 , … , 𝐸1 as in equation (3). Thus L will be
invertible, by the Invertible Matrix Theorem, with
(𝐸𝑝 … 𝐸1)= L-1. From (3), L-1A = U, and A = LU. So step 2
will produce an acceptable L.
 AN LU FACTORIZATION ALGORITHM
 Example 2 Find an LU factorization of

 Solution Since A has four rows, L should be 4 × 4. The

first column of L is the first column of A divided by the top
pivot entry:
 AN LU FACTORIZATION ALGORITHM
 Compare the first columns of A and L. The row operations that
create zeros in the first column of A will also create zeros in the
first column of L.
 To make this same correspondence of row operations on A hold
for the rest of L, watch a row reduction of A to an echelon form
U. That is, highlight the entries in each matrix that are used to
determine the sequence of row operations that transform A into
U.

(5)
 AN LU FACTORIZATION ALGORITHM
 The highlighted entries above determine the row reduction of
A to U. At each pivot column, divide the highlighted entries
by the pivot and place the result into L:

 An easy calculation verifies that this L and U satisfy LU = A.

 QR FACTORIZATION OF MATRICES
 Theorem 12: The QR Factorization
 If A is an m ×n matrix with linearly independent columns,
then A can be factored as A = QR, where Q is an m ×n
matrix whose columns form an orthonormal basis for
ColA and R is an n ×n upper triangular invertible matrix
with positive entries on its diagonal.

 Proof The columns of A form a basis {x1, . . . , xn} for

Col A. Construct an orthonormal basis {u1, . . . , un} for W
= Col A with property (1) in Theorem 11. This basis may
be constructed by the Gram-Schmidt process or some
other means.
 QR FACTORIZATION OF MATRICES
 Let
𝑄 = [𝐮1 𝐮2 . . . 𝐮𝑛 ]

 For k = 1 ,…,k, xk is in Span{x1, . . . , xk} = Span{u1, . . . ,

uk}. So there are constants, r1k , . . . , rkk, such that

𝑥𝑘 = 𝑟1𝑘𝐮1 + ⋯ + 𝑟𝑘𝑘 𝐮𝑘 + 0 ∙ 𝐮𝑘 + 1 + ⋯ + 0 ∙ 𝐮𝑛

 We may assume that rkk ≥ 0. This shows that xk is a linear

combination of the columns of Q using as weights the
entries in the vector
 QR FACTORIZATION OF MATRICES
𝑟1𝑘
.
.
.
𝑟
r𝑘 = 𝑘𝑘
0
.
.
.
0
 That is, xk = Qrk for k = 1, . . . , n. Let R = [r1 . . . rn]. Then
A = [x1 . . . xn] = [Qr1 . . . Qrn] = QR
 The fact that R is invertible follows easily from the fact that the
columns of A are linearly independent. Since R is clearly upper
triangular, its nonnegative diagonal entries must be positive.
 QR FACTORIZATION OF MATRICES
1 0 0
 Example 4 Find a QR factorization of A = 1 1 0 .
1 1 1
1 1 1
 Solution The columns of A are the vectors x1, x2, and x3 in
Example 2. An orthogonal basis for Col A = Span{x1, x2,
x3} was found in that example:

1 −3 0
1 1 −2/3
𝑣1 = , 𝑣2 = , 𝑣3 =
1 1 1/3
1 1 1/3
 QR FACTORIZATION OF MATRICES
 To simplify the arithmetic that follows, scale v3 by letting
v3 = 3v3. Then normalize the three vectors to obtain u1, u2,
and u3, and use these vectors as the columns of Q:

1/2 −3/ 12 0
1/2 1/ 12 −2/ 6
Q= .
1/2 1/ 12 1/ 6
1/2 1/ 12 1/ 6

 By construction, the first k columns of Q are an

orthonormal basis of Span{x1 , . . . , xk}.
QR FACTORIZATION OF MATRICES

 From the proof of Theorem 12, A = QR for some R. To find

R, observe that QTQ = I, because the columns of Q are
orthonormal. Hence
𝑄𝑇𝐴 = 𝑄𝑇 𝑄𝑅 = 𝐼𝑅 = 𝑅
 and
1/2 1/2 1/2 1/2 1 0 0
R = −3/ 12 1/ 12 1/ 12 1/ 12 1 1 0
1 1 1
0 −2/ 6 1/ 12 1/ 6 1 1 1
2 3/2 1
= 0 3/ 12 2/ 12
0 0 3/ 12
 EIGENVECTORS AND EIGENVALUES
 Definition: An eigenvector of an 𝑛 × 𝑛 matrix A is a nonzero vector
x such that 𝐴𝐱 = λx for some scalar λ. A scalar λ is called an
eigenvalue of A if there is a nontrivial solution x of 𝐴𝐱 = λx; such
an x is called an eigenvector corresponding to λ.
 λ is an eigenvalue of an 𝑛 × 𝑛 matrix A if and only if the equation
(𝐴 − λ𝐼)𝐱 = 𝟎 (3)
has a nontrivial solution.
 The set of all solutions of (3) is just the null space of the matrix
𝐴 − λ𝐼.
 So this set is a subspace of ℝ𝑛 and is called the eigenspace of A
corresponding to λ.
 The eigenspace consists of the zero vector and all the eigenvectors
corresponding to λ.
EIGENVECTORS AND EIGENVALUES
 Example 3: Show that 7 is an eigenvalue of matrix
1 6
𝐴= and find the corresponding eigenvectors.
5 2
 Solution: The scalar 7 is an eigenvalue of A if and only
if the equation
𝐴𝐱 = 7𝐱 (1)
has a nontrivial solution.
 But (1) is equivalent to 𝐴𝐱 − 7𝐱 = 𝟎, or
(𝐴 − 7𝐼)𝐱 = 𝟎 (2)
 To solve this homogeneous equation, form the matrix
1 6 7 0 −6 6
𝐴 − 7𝐼 = − =
5 2 0 7 5 −5
 EIGENVECTORS AND EIGENVALUES
 The columns of 𝐴 − 7𝐼 are obviously linearly
dependent, so (2) has nontrivial solutions.
 To find the corresponding eigenvectors, use row
operations:
−6 6 0 1 −1 0
∼
5 −5 0 0 0 0
1
 The general solution has the form 𝑥2 .
1
 Each vector of this form with 𝑥2 ≠ 0 is an eigenvector
corresponding to 𝜆 = 7.
 EIGENVECTORS AND EIGENVALUES
4 −1 6
 Example 4: Let 𝐴 = 2 1 6 . An eigenvalue of A is
2 −1 8
2. Find a basis for the corresponding eigenspace.
 Solution: Form
4 −1 6 2 0 0 2 −1 6
𝐴 − 2𝐼 = 2 1 6 − 0 2 0 = 2 −1 6
2 −1 8 0 0 2 2 −1 6
and row reduce the augmented matrix for (𝐴 − 2𝐼)𝐱 = 𝟎.
2 −1 6 0 2 −1 6 0
2 −1 6 0 ∼ 0 0 0 0
2 −1 6 0 0 0 0 0
 EIGENVECTORS AND EIGENVALUES
 At this point, it is clear that 2 is indeed an eigenvalue of
A because the equation (𝐴 − 2𝐼)𝐱 = 𝟎 has free variables.
 The general solution is
𝑥1 1/2 −3
𝑥2 = 𝑥2 1 + 𝑥3 0 , x2 and x3 free.
𝑥3 0 1
 The eigenspace, shown in the following figure, is a two-
1 −3
dimensional subspace of ℝ3 . A basis is 2 , 0 .
0 1
EIGENVECTORS AND EIGENVALUES
 Theorem 1: The eigenvalues of a triangular matrix
are the entries on its main diagonal.
 Proof: For simplicity, consider the 3 × 3 case.
 If A is upper triangular, the 𝐴 − 𝜆𝐼 has the form
𝑎11 𝑎12 𝑎13 λ 0 0
𝐴 − λ𝐼 = 0 𝑎22 𝑎23 − 0 λ 0
0 0 𝑎33 0 0 λ
𝑎11 − λ 𝑎12 𝑎13
= 0 𝑎22 − λ 𝑎23
0 0 𝑎33 − λ
EIGENVECTORS AND EIGENVALUES
 The scalar λ is an eigenvalue of A if and only if the
equation (𝐴 − λ𝐼)𝐱 = 𝟎 has a nontrivial solution, that
is, if and only if the equation has a free variable.

 Because of the zero entries in 𝐴 − λ𝐼, it is easy to see

that (𝐴 − λ𝐼)𝐱 = 𝟎 has a free variable if and only if
at least one of the entries on the diagonal of 𝐴 − λ𝐼 is
zero.

 This happens if and only if λ equals one of the entries

a11, a22, a33 in A.
 EIGENVECTORS AND EIGENVALUES
 Theorem 2: If v1, …, vr are eigenvectors that correspond
to distinct eigenvalues λ1, …, λr of an 𝑛 × 𝑛 matrix A,
then the set {v1, …, vr} is linearly independent.
 Proof: Suppose {v1, …, vr} is linearly dependent.
 Since v1 is nonzero, Theorem 7 in Section 1.7 says that
one of the vectors in the set is a linear combination of the
preceding vectors.
 Let p be the least index such that 𝐯𝑝+1 is a linear
combination of the preceding (linearly independent)
vectors.
EIGENVECTORS AND EIGENVALUES
 Then there exist scalars c1, …, cp such that
𝑐1 𝐯1 + ⋯ + 𝑐𝑝 𝐯𝑝 = 𝐯𝑝+1 (5)
 Multiplying both sides of (5) by A and using the fact
that 𝐴𝐯𝑘 = 𝜆𝑘 𝐯𝑘 for each k, we obtain
𝑐1 𝐴𝐯1 + ⋯ + 𝑐𝑝 𝐴𝐯𝑝 = 𝐴𝐯𝑝+1
𝑐1 λ1𝐯1 + ⋯ + 𝑐𝑝 λ𝑝 𝐯𝑝 = λ𝑝+1 𝐯𝑝+1 (6)
 Multiplying both sides of (5) by λ𝑝+1 and subtracting
the result from (6), we have
𝑐1 (λ1 − λ𝑝+1 )𝐯1 + ⋯ + 𝑐𝑝 (λ𝑝 − λ𝑝+1 )𝐯𝑝 = 0 (7)
EIGENVECTORS AND EIGENVALUES
 Since {v1, …, vp} is linearly independent, the weights
in (7) are all zero.
 But none of the factors λ𝑖 − λ𝑝+1 are zero, because
the eigenvalues are distinct.
 Hence 𝑐𝑖 = 0 for 𝑖 = 1, … , 𝑝.

 But then (5) says that v𝑝+1 = 0, which is impossible.

 Hence {v1, …, vr} cannot be linearly dependent and

therefore must be linearly independent.
EIGENVECTORS AND DIFFERENCE EQUATIONS
 If A is an 𝑛 × 𝑛 matrix, then (8) is a recursive description of a
sequence {xk} in ℝ𝑛 .
𝐱 𝑘+1 = 𝐴𝐱 𝑘 , (𝑘 = 0,1,2 … ) (8)

 A solution of (8) is an explicit description of {xk} whose

formula for each xk does not depend directly on A or on the
preceding terms in the sequence other than the initial term x0.

 The simplest way to build a solution of (8) is to take an

eigenvector x0 and its corresponding eigenvalue λ and let
𝐱𝑘 = λ𝑘 𝐱0 , (𝑘 = 1,2, … ) (9)
 This sequence is a solution because
𝐴𝐱𝑘 = 𝐴(λ𝑘 𝐱0 ) = λ𝑘 (𝐴𝐱 0 ) = λ𝑘 (λx0 ) = λ𝑘+1 𝐱 0 = 𝐱 𝑘+1
 EIGENVECTORS AND DIFFERENCE EQUATIONS
 The simplest way to build a solution of (8) is to take an
eigenvector x0 and its corresponding eigenvalue λ and let
𝐱𝑘 = λ𝑘 x0 , (𝑘 = 1,2, … ) (9)
 This sequence is a solution because
𝐴x𝑘 = 𝐴 λ𝑘 x0
= λ𝑘 𝐴x0 = λ𝑘 λx0
= λ𝑘+1 x0 = x𝑘+1
 DIAGONALIZATION
7 2
 Example 2: Let 𝐴 = . Find a formula for
−4 1
Ak, given that 𝐴 = 𝑃𝐷𝑃−1 , where
1 1 5 0
𝑃= and 𝐷 =
−1 −2 0 3
 Solution: The standard formula for the inverse of a
−1 2 1
2 × 2 matrix yields 𝑃 =
−1 −1
 Then, by associativity of matrix multiplication,
𝐴2 = (𝑃𝐷𝑃−1 )(𝑃𝐷𝑃−1 ) = 𝑃𝐷(𝑃−1 𝑃)𝐷𝑃−1 = 𝑃𝐷𝐷𝑃−1
𝐼
1 1 52 0 2 1
= 𝑃𝐷2 𝑃−1 =
−1 −2 0 32 −1 −1
© 2016 Pearson Education, Ltd. Slide 5.3- 32
 DIAGONALIZATION
 Again,
𝐴3 = (𝑃𝐷𝑃−1 )𝐴2 = (𝑃𝐷 𝑃−1 )𝑃 𝐷2 𝑃−1
𝐼
= 𝑃𝐷𝐷2 𝑃−1 = 𝑃𝐷3 𝑃−1
 In general, for 𝑘 ≥ 1,
1 1 5𝑘 0 2 1
 𝐴𝑘 = 𝑃𝐷𝑘 𝑃−1
=
−1 −2 0 3𝑘 −1 −1
2 ⋅ 5𝑘 − 3𝑘 5 𝑘 − 3𝑘
=
2 ⋅ 3𝑘 − 2 ⋅ 5𝑘 2 ⋅ 3𝑘 − 5𝑘
 A square matrix A is said to be diagonalizable if A is
similar to a diagonal matrix, that is, if 𝐴 = 𝑃𝐷𝑃−1 for
some invertible matrix P and some diagonal, matrix D.
© 2016 Pearson Education, Ltd. Slide 5.3- 33
 THE DIAGONALIZATION THEOREM
 Theorem 5: An 𝑛 × 𝑛 matrix A is diagonalizable if and
only if A has n linearly independent eigenvectors.
In fact, 𝐴 = 𝑃𝐷𝑃−1 , with D a diagonal matrix, if and
only if the columns of P and n linearly independent
eigenvectors of A. In this case, the diagonal entries of D
are eigenvalues of A that correspond, respectively, to the
eigenvectors in P.
In other words, A is diagonalizable if and only if
there are enough eigenvectors to form a basis of ℝ𝑛 . We
call such a basis an eigenvector basis of ℝ𝑛 .

© 2016 Pearson Education, Ltd. Slide 5.3- 34

 THE DIAGONALIZATION THEOREM
 Proof: First, observe that if P is any 𝑛 × 𝑛 matrix with
columns v1, …, vn, and if D is any diagonal matrix with
diagonal entries λ1, …, λn, then
𝐴𝑃 = 𝐴 𝐯1 𝐯2 ⋯ 𝐯𝑛 = 𝐴𝐯1 𝐴𝐯2 ⋯ 𝐴𝐯𝑛 (1)
while
λ1 0 ⋯ 0
0 λ2 ⋯ 0
𝑃𝐷 = 𝑃 = λ1 𝐯1 λ2 𝐯2 ⋯ λ𝑛 𝐯𝑛 (2)
⋮ ⋮ ⋮
0 0 ⋯ λ𝑛
 Now suppose A is diagonalizable and 𝐴 = 𝑃𝐷𝑃−1 . Then
right-multiplying this relation by P, we have 𝐴𝑃 = 𝑃𝐷.
© 2016 Pearson Education, Ltd. Slide 5.3- 35
 THE DIAGONALIZATION THEOREM
 In this case, equations (1) and (2) imply that
𝐴𝐯1 𝐴𝐯2 ⋯ 𝐴𝐯𝑛 = λ1 𝐯1 λ2 𝐯2 ⋯ λ𝑛 𝐯𝑛 (3)
 Equating columns, we find that
𝐴𝐯1 = λ1 𝐯1 , 𝐴𝐯2 = λ2 𝐯2 , … , 𝐴𝐯𝑛 = λ𝑛 𝐯𝑛 (4)
 Since P is invertible, its columns v1, …, vn must be
linearly independent.

 Also, since these columns are nonzero, the equations in

(4) show that λ1, …, λn are eigenvalues and v1, …, vn are
corresponding eigenvectors.

© 2016 Pearson Education, Ltd. Slide 5.3- 36

THE DIAGONALIZATION THEOREM
 This argument proves the “only if ” parts of the first
and second statements, along with the third statement,
of the theorem.
 Finally, given any n eigenvectors v1, …, vn, use them to
construct the columns of P and use corresponding
eigenvalues λ1, …, λn to construct D.
 By equations (1)–(3), 𝐴𝑃 = 𝑃𝐷.
 This is true without any condition on the eigenvectors.

 If, in fact, the eigenvectors are linearly independent,

then P is invertible (by the Invertible Matrix Theorem),
and 𝐴𝑃 = 𝑃𝐷 implies that 𝐴 = 𝑃𝐷𝑃−1 .
© 2016 Pearson Education, Ltd. Slide 5.3- 37
DIAGONALIZING MATRICES
 Example: Diagonalize the following matrix, if
possible.
1 3 3
𝐴 = −3 −5 −3
3 3 1
That is, find an invertible matrix P and a diagonal
matrix D such that 𝐴 = 𝑃𝐷𝑃−1 .
 Solution: There are four steps to implement the
description in Theorem 5.
 Step 1. Find the eigenvalues of A.
 Here, the characteristic equation turns out to involve a
cubic polynomial that can be factored:
DIAGONALIZING MATRICES
0 = det( 𝐴 − λ𝐼) = −λ3 − 3λ2 + 4
= −(λ − 1)(λ + 2)2
 The eigenvalues are λ = 1 and λ = −2.
 Step 2. Find three linearly independent eigenvectors
of A.
 Three vectors are needed because A is a 3 × 3 matrix.
 This is a critical step.
 If it fails, then Theorem 5 says that A cannot be
diagonalized.
 DIAGONALIZING MATRICES
1
 Basis for λ = 1: v1 = −1
1
−1 −1
 Basis for λ = −2: v2 = 1 and v3 = 0
0 1
 You can check that {v1, v2, v3} is a linearly independent set.
 Step 3. Construct P from the vectors in step 2.
 The order of the vectors is unimportant.
 Using the order chosen in step 2, form
 DIAGONALIZING MATRICES
1 −1 −1
𝑃 = v1 v2 v3 = −1 1 0
1 0 1
 Step 4. Construct D from the corresponding
eigenvalues.
 In this step, it is essential that the order of the eigenvalues
matches the order chosen for the columns of P.
 Use the eigenvalue 𝜆 = −2 twice, once for each of the
eigenvectors corresponding to 𝜆 = −2:
1 0 0
𝐷 = 0 −2 0
0 0 −2
 DIAGONALIZING MATRICES
 To avoid computing 𝑃−1 , simply verify that 𝐴𝑃 = 𝑃𝐷.
 Compute
1 3 3 1 −1 −1 1 2 2
𝐴𝑃 = −3 −5 −3 −1 1 0 = −1 −2 0
3 3 1 1 0 1 1 0 −2

1 −1 −1 1 0 0 1 2 2
𝑃𝐷 = −1 1 0 0 −2 0 = −1 −2 0
1 0 1 0 0 −2 1 0 −2
 DIAGONALIZING MATRICES
 Theorem 6: An 𝑛 × 𝑛 matrix with n distinct eigenvalues
is diagonalizable.
 Proof: Let v1, …, vn be eigenvectors corresponding to the
n distinct eigenvalues of a matrix A.
 Then {v1, …, vn} is linearly independent, by Theorem 2
in Section 5.1.
 Hence A is diagonalizable, by Theorem 5.
 It is not necessary for an 𝑛 × 𝑛 matrix to have n distinct
eigenvalues in order to be diagonalizable.
 The 3 x 3 matrix in Example 3 is diagonalizable even
though it has only two distinct eigenvalues.
MATRICES WHOSE EIGENVALUES ARE NOT DISTINCT

 If an 𝑛 × 𝑛 matrix A has n distinct eigenvalues, with

corresponding eigenvectors v1, …, vn, and if 𝑃 =
v1 ⋯ v2 , then P is automatically invertible
because its columns are linearly independent, by
Theorem 2.

 When A is diagonalizable but has fewer than n distinct

eigenvalues, it is still possible to build P in a way that
makes P automatically invertible, as the next theorem
shows.
MATRICES WHOSE EIGENVALUES ARE NOT DISTINCT
 Theorem 7: Let A be an 𝑛 × 𝑛 matrix whose distinct eigenvalues
are λ1, …, λp.
a. For 1 ≤ 𝑘 ≤ 𝑝,the dimension of the eigenspace for λk is less
than or equal to the multiplicity of the eigenvalue λk.
b. The matrix A is diagonalizable if and only if the sum of the
dimensions of the eigenspaces equals n, and this happens if
and only if (i) the characteristic polynomial factors completely
into linear factors and (ii) the dimension of the eigenspace for
each λk equals the multiplicity of λk
c. If A is diagonalizable and Bk is a basis for the eigenspace
corresponding to Bk for each k, then the total collection of
vectors in the sets B1, …, Bp forms an eigenvector basis for
ℝ𝑛 .
 THE SINGULAR VALUES OF AN 𝑚 × 𝑛 MATRIX
 Theorem 9 Suppose {v1, . . . , vn} is an orthonormal
basis of ℝ𝑛 consisting of eigenvectors of ATA, arranged
so that the corresponding eigenvalues of ATA satisfy 𝜆1 ≥
⋯ ≥ 𝜆𝑛 , and suppose A has r nonzero singular values.
Then {Av1, . . . , Avr} is an orthogonal basis for Col A, and
rank A = r.

 Proof Because vi and 𝜆𝑗vj are orthogonal for 𝑖 ≠ 𝑗,

𝐴𝑣𝑖 𝑇 𝐴𝑣𝑗 = 𝑣𝑖𝑇 𝐴𝑇𝐴𝑣𝑗 = 𝑣𝑖𝑇 𝜆𝑗 𝑣𝑗 = 0

 Thus {Av1, . . . , Avn} is an orthogonal set.

 THE SINGULAR VALUES OF AN 𝑚 × 𝑛 MATRIX
 Since the lengths of the vectors Av1, . . . , Avn are the
singular values of A, and since there are r nonzero
singular values, 𝐴𝑣𝑖 ≠ 0 if and only if 1 ≤ 𝑖 ≤ 𝑟.

 So Av1, . . . , Avr are linearly independent vectors, and

they are in Col A.

 Finally, for any y in Col A—say, y = Ax—we can write

𝑥 = 𝑐1𝑣1 + ⋯ + 𝑐𝑛𝑣𝑛, and

𝑦 = 𝐴𝑥 = 𝑐1𝐴𝑣1 + ⋯ + 𝑐𝑟𝐴𝑣𝑟 + 𝑐𝑟 + 1𝐴𝑣𝑟 + 1 + ⋯ + 𝑐𝑛𝐴𝑣𝑛

 THE SINGULAR VALUES OF AN 𝑚 × 𝑛 MATRIX
= 𝑐1𝐴𝑣1 + ⋯ + 𝑐𝑟𝐴𝑣𝑟 + 0 + ⋯ + 0

 Thus y is in Span{Av1, . . . , Avr}, which shows that {Av1, .

. . , Avr} is an (orthogonal) basis for Col A.

 Hence rank A = dim Col A = r.

 THE SINGULAR VALUE DECOMPOSITION

 Theorem 10: The Singular Value Decomposition Let A

be an 𝑚 × 𝑛 matrix with rank r. Then there exists an 𝑚 ×
𝑛matrix Σ as in (3) for which the diagonal entries in D are
the first r singular values of A, 𝜎1 ≥ 𝜎2 ≥ ⋯ ≥ 𝜎𝑟 > 0,
and there exist an 𝑚 × 𝑚 orthogonal matrix U and an 𝑛 ×
𝑛 orthogonal matrix V such that

𝐴 = 𝑈Σ𝑉𝑇
 THE SINGULAR VALUE DECOMPOSITION

 Any factorization 𝐴 = 𝑈Σ𝑉𝑇, with U and V orthogonal,

Σ as in (3), and positive diagonal entries in D, is called a
singular value decomposition (or SVD) of A.

 The columns of U in such a decomposition are called left

singular vectors of A, and the columns of V are called
right singular vectors of A.

 Proof Let 𝜆𝑖 and vi be as in Theorem 9, so that {Av1, . . . ,

Avr} is an orthogonal basis for Col A.
 THE SINGULAR VALUE DECOMPOSITION
 Normalize each Avi to obtain an orthonormal basis {u1, . .
. , ur}, where
1 1
𝑢𝑖 = 𝐴𝑣𝑖 = 𝐴𝑣𝑖
𝐴𝑣𝑖 𝜎1
 And
𝐴𝑣𝑖 = 𝜎𝑖𝑢𝑖 (1 ≤ i ≤ r) (4)
 Now extend {u1, . . . , ur} to an orthonormal basis {u1, . .
. , um} of ℝ𝑚 , and let
𝑈 = [𝑢1 𝑢2 . . . 𝑢𝑚] and 𝑉 = [𝑣1 𝑣2 . . . 𝑣𝑚]

 By construction, U and V are orthogonal matrices.

THE SINGULAR VALUE DECOMPOSITION
 Also, from (4),
𝐴𝑉 = 𝐴𝑥1 … 𝐴𝑣𝑟 0 … 0 = [𝜎1𝑢1 . . . 𝜎𝑟𝑢𝑟 0 . . . 0]
 Let D be the diagonal matrix with diagonal entries
𝜎1,...,𝜎𝑟, and let Σ be as in (3) above. Then

 Since V is an orthogonal matrix, 𝑈Σ𝑉𝑇 = 𝐴𝑉𝑉𝑇 = 𝐴.

 THE SINGULAR VALUE DECOMPOSITION
 Example 3 Use the results of Examples 1 and 2 to construct
4 11 14
a singular value decomposition of 𝐴 = .
8 7 −2

 Solution A construction can be divided into three steps.

 Step 1. Find an orthogonal diagonalization of ATA. That is,
find the eigenvalues of ATA and a corresponding orthonormal
set of eigenvectors. If A had only two columns, the
calculations could be done by hand. Larger matrices usually
require a matrix program. However, for the matrix A here,
the eigendata for ATA are provided in Example 2.
 THE SINGULAR VALUE DECOMPOSITION
 Step 2. Set up V and 𝜮. Arrange the eigenvalues of ATAin
decreasing order. In Example 1, the eigenvalues are already
listed in decreasing order: 360, 90, and 0. The corresponding
unit eigenvectors, v1, v2, and v3, are the right singular vectors
of A. Using Example 1, construct
1/3 −2/3 2/3
𝑉 = 𝑣1 𝑣2 𝑣3 = 2/3 −1/3 −2/3
2/3 2/3 1/3

 The square roots of the eigenvalues are the singular values:

𝜎1 = 6 10, 𝜎2 = 3 10, 𝜎3 = 0
 THE SINGULAR VALUE DECOMPOSITION
 The nonzero singular values are the diagonal entries of D.
The matrix Σ is the same size as A, with D in its upper left
corner and with 0’s elsewhere.
6 10 0 6 10 0 0
𝐷= , Σ= 𝐷 0 =
0 3 10 0 3 10 0

 Step 3. Construct U. When A has rank r, the first r columns

of U are the normalized vectors obtained from Av1, . . . , Avr.
In this example, A has two nonzero singular values, so rank
A = 2. Recall from equation (2) and the paragraph before
Example 2 that 𝐴𝑣1 = 𝜎1 and 𝐴𝑣2 = 𝜎2 .
THE SINGULAR VALUE DECOMPOSITION
 Thus
1 1 18 3/ 10
𝑢1 = 𝐴𝑣1 = =
𝜎1 6 10 6 1/ 10
1 1 3 1/ 10
𝑢2 = 𝐴𝑣2 = =
𝜎2 3 10 −9 −3/ 10
 Note that {u1, u2} is already a basis for ℝ2 . Thus no
additional vectors are needed for U, and U = [u1 u2]. The
singular value decomposition of A is
1/3 2/3 2/3
3/ 10 1/ 10 6/ 10 0 0
𝐴= −2/3 −1/3 2/3
1/ 10 −3/ 10 0 3/ 10 0 2/3 −2/3 1/3
 THE SINGULAR VALUE DECOMPOSITION

 Theorem: The Invertible Matrix Theorem (concluded)

 Let A be an 𝑛 × 𝑛 matrix. Then the following statements
are each equivalent to the statement that A is an invertible
matrix.
u. (Col A)┴ = {0}.
v. (NulA) ┴ = ℝ2
w. Row A = ℝ𝑛
x. A has n nonzero singular values.
 THE SINGULAR VALUE DECOMPOSITION
 Example 7 (Reduced SVD and the Pseudoinverse of A)
When Σ contains rows or columns of zeros, a more compact
decomposition of A is possible. Using the notation
established above, let r = rank A, and partition U and V into
submatrices whose first blocks contain r columns:
𝑈 = [𝑈𝑟 𝑈𝑚 − 𝑟], where 𝑈𝑟= [u1 . . . ur]
𝑉 = [𝑉𝑟 𝑈𝑛 − 𝑟], where 𝑉𝑟= [v1. . . vr]
 Then 𝑈𝑟 is 𝑚 × 𝑟 and V𝑟 is 𝑛 × 𝑟. Then partitioned matrix
multiplication shows that
𝐷 0 𝑉𝑟𝑇 𝑇
𝐴 = 𝑈𝑟 𝑈𝑚 − 𝑟 𝑇 = 𝑈𝑟𝐷𝑉 𝑟 (9)
0 0 𝑉𝑛−𝑟
 THE SINGULAR VALUE DECOMPOSITION
 This factorization of A is called a reduced singular value
decomposition of A. Since the diagonal entries in D are
nonzero, D is invertible. The following matrix is called the
pseudoinverse (also, the Moore-Penrose inverse) of A:

−1 𝑇
𝐴+ = 𝑉𝑟𝐷 𝑈𝑟
(10)