i
i
i
i
i
i
i
i
106 5. Linear Algebra
Here U and V are two, potentially different, orthogonal matrices, whose columns
are known as the left and right singular vectors of A,andS is a diagonal matrix
whose entries are known as the singular values of A.WhenA is symmetric and
has all non-negative eigenvalues, the SVD and the eigenvalue decomposition are
the same.
There is another relationship between singular values and eigenvalues that
can be used to compute the SVD (though this is not the way an industrial-strength
SVD implementation works). First we define M = AA
T
. We assume that we
can perform a SVD on M:
M = AA
T
=(USV
T
)(USV
T
)
T
= US(V
T
V)SU
T
= US
2
U
T
.
The substitution is based on the fact that (BC)
T
= C
T
B
T
, that the transpose
of an orthogonal matrix is its inverse, and the transpose of a diagonal matrix
is the matrix itself. The beauty of this new form is that M is symmetric and
US
2
U
T
is its eigenvaluedecomposition, where S
2
contains the (all non-negative)
eigenvalues. Thus, we find that the singular values of a matrix are the square roots
of the eigenvalues of the product of the matrix with its transpose, and the left
singular vectors are the eigenvectors of that product. A similar argument allows
V, the matrix of right singular vectors, to be computed from A
T
A.
Example. We now make this concrete with an example:
A =
11
01
; M = AA
T
=
21
11
.
We saw the eigenvalue decomposition for this matrix in the previous section. We
observe immediately
11
01
=
0.8507 −0.5257
0.5257 0.8507
√
2.618 0
0
√
0.382
V
T
.
We can solve for V algebraically:
V =(S
−1
U
T
M)
T
.
The inverse of S is a diagonal matrix with the reciprocals of the diagonal elements
of S. This yields
11
01
= U
σ
1
0
0 σ
2
V
T
=
0.8507 −0.5257
0.5257 0.8507
1.618 0
00.618
0.5257 0.8507
−0.8507 0.5257
.
i
i
i
i
i
i
i
i
5.4. Eigenvalues and Matrix Diagonalization 107
This form used the standard symbol σ
i
for the ith singular value. Again, for a
symmetric matrix, the eigenvalues and the singular values are the same (σ
i
= λ
i
).
We will examine the geometry of SVD further in Section 6.1.6.
Frequently Asked Questions
• Why is matrix multiplication defined the way it is rather than just element
by element?
Element by element multiplication is a perfectly good way to define matrix mul-
tiplication, and indeed it has nice properties. However, in practice it is not very
useful. Ultimately most matrices are used to transform column vectors, e.g., in
3D you might have
b = Ma,
where a and b are vectors and M is a 3×3 matrix. To allow geometric operations
such as rotation, combinations of all three elements of a must go into each element
of b. That requires us to either go row-by-row or column-by-column through M.
That choice is made based on composition of matrices having the desired property,
M
2
(M
1
a)=(M
2
M
1
)a
which allows us to use one composite matrix C = M
2
M
1
to transformour vector.
This is valuable when many vectors will be transformed by the same composite
matrix. So, in summary, the somewhat weird rule for matrix multiplication is en-
gineered to have these desired properties.
• Sometimes I hear that eigenvalues and singular values are the same
thing and sometimes that one is the square of the other. Which is right?
If a real matrix A is symmetric, and its eigenvalues are non-negative, then its
eigenvalues and singular values are the same. If A is not symmetric, the ma-
trix M = AA
T
is symmetric and has non-negative real eignenvalues. The sin-
gular values of A and A
T
are the same and are the square roots of the singu-
lar/eigenvalues of M. Thus, when the square root statement is made, it is because
two different matrices (with a very particular relationship) are being talked about:
M = AA
T
.
Notes
The discussion of determinants as volumes is based on A Vector Space Approach
to Geometry (Hausner, 1998). Hausner has an excellent discussion of vector
i
i
i
i
i
i
i
i
108 5. Linear Algebra
analysis and the fundamentals of geometry as well. The geometric derivation
of Cramer’s rule in 2D is taken from Practical Linear Algebra: A Geometry Tool-
box (Farin & Hansford, 2004). That book also has geometric interpretations of
other linear algebra operations such as Gaussian elimination. The discussion of
eigenvalues and singular values is based primarily on Linear Algebra and Its Ap-
plications (Strang, 1988). The example of SVD of the shear matrix is based on a
discussion in Computer Graphics and Geometric Modeling (Salomon, 1999).
Exercises
1. Write an implicit equation for the 2D line through points (x
0
,y
0
) and
(x
1
,y
1
) using a 2D determinant.
2. Show that if the columns of a matrix are orthonormal, then so are the rows.
3. Prove the properties of matrix determinants stated in Equations (5.5)–(5.7).
4. Show that the eigenvalues of a diagonal matrix are its diagonal elements.
5. Show that for a square matrix A, AA
T
is a symmetric matrix.
6. Show that for three 3D vectors a, b, c, the following identity holds: |abc| =
(a × b) · c.
7. Explain why the volume of the tetrahedron with side vectors a, b, c (see
Figure 5.2) is given by |abc|/6.
8. Demonstrate the four interpretations of matrix-matrix multiplication by tak-
ing the following matrix-matrix multiplication code, rearranging the nested
loops, and interpreting the resulting code in terms of matrix and vector op-
erations.
function mat-mult(in a[m][p], in b[p][n], out c[m][n]) {
// the array c is initialized to zero
for i = 1 to m
for j = 1 to n
fork=1top
c[i][j] += a[i][k]
*
b[k][j]
}
9. Prove that if A, Q,andD satisfy Equation (5.14), v is the ith row of Q,
and λ is the ith entry on the diagonal of D,thenv is an eigenvector of A
with eigenvalue λ.
i
i
i
i
i
i
i
i
5.4. Eigenvalues and Matrix Diagonalization 109
10. Prove that if A, Q,andD satisfy Equation (5.14), the eigenvalues of A are
all distinct, and v is an eigenvector of A with eigenvalue λ, then for some
i, v is the ith row of Q and λ is the ith entry on the diagonal of D.
11. Given the (x, y) coordinates of the three vertices of a 2D triangle, explain
why the area is given by
1
2
x
0
x
1
x
2
y
0
y
1
y
2
111
.
i
i
i
i
i
i
i
i
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.