Page 311 - Matrix Analysis & Applied Linear Algebra

5.5 Gram–Schmidt Procedure 307
5.5 GRAM–SCHMIDT PROCEDURE

As discussed in §5.4, orthonormal bases possess significant advantages over bases
n n
that are not orthonormal. The spaces and C clearly possess orthonormal
bases (e.g., the standard basis), but what about other spaces? Does every finite-
dimensional space possess an orthonormal basis, and, if so, how can one be
44
produced? The Gram–Schmidt orthogonalization procedure developed below
answers these questions.
Let B = {x 1 , x 2 ,..., x n } be an arbitrary basis (not necessarily orthonormal)
1/2
for an n-dimensional inner-product space S, and remember that = .

Objective: Use B to construct an orthonormal basis O = {u 1 , u 2 ,..., u n }
for S.

Strategy: Construct O sequentially so that O k = {u 1 , u 2 ,..., u k } is an or-
thonormal basis for S k = span {x 1 , x 2 ,..., x k } for k =1,...,n.
For k =1, simply take u 1 = x 1 / x 1 . It’s clear that O 1 = {u 1 } is an
orthonormal set whose span agrees with that of S 1 = {x 1 } . Now reason in-
ductively. Suppose that O k = {u 1 , u 2 ,..., u k } is an orthonormal basis for
S k = span {x 1 , x 2 ,..., x k } , and consider the problem of finding one additional
vector u k+1 such that O k+1 = {u 1 , u 2 ,..., u k , u k+1 } is an orthonormal basis
for S k+1 = span {x 1 , x 2 ,..., x k , x k+1 } . For this to hold, the Fourier expansion
(p. 299) of x k+1 with respect to O k+1 must be
k+1

x k+1 = u i x k+1 u i ,
i=1
which in turn implies that
k
x k+1 − i=1 u i x k+1 u i
u k+1 = . (5.5.1)
u k+1 x k+1
Since u k+1 =1, it follows from (5.5.1) that
k

| u k+1 x k+1 | =
x k+1 − u i x k+1 u i
,
i=1
44
Jorgen P. Gram (1850–1916) was a Danish actuary who implicitly presented the essence of or-
thogonalization procedure in 1883. Gram was apparently unaware that Pierre-Simon Laplace
(1749–1827) had earlier used the method. Today, Gram is remembered primarily for his de-
velopment of this process, but in earlier times his name was also associated with the matrix
product A A that historically was referred to as the Gram matrix of A.
∗
Erhard Schmidt (1876–1959) was a student of Hermann Schwarz (of CBS inequality fame) and
the great German mathematician David Hilbert. Schmidt explicitly employed the orthogonal-
ization process in 1907 in his study of integral equations, which in turn led to the development
of what are now called Hilbert spaces.Schmidt made significant use of the orthogonalization
process to develop the geometry of Hilbert Spaces, and thus it came to bear Schmidt’s name.