13.3. LEAST SQUARE APPROXIMATION 309

where T is an upper triangular matrix. Then from Lemma 13.2.10

T ∗ = (U∗AU)∗ =U∗A∗U =U∗AU = T.

Thus T = T ∗ and T is upper triangular. This can only happen if T is really a diagonalmatrix having real entries on the main diagonal. (If i ̸= j, one of Ti j or Tji equals zero. ButTi j = Tji and so they are both zero. Also Tii = Tii.)

Finally, letU =

(u1 u2 · · · un

)where the ui denote the columns of U and

D =

λ 1 0

. . .

0 λ n

The equation, U∗AU = D implies

AU =(

Au1 Au2 · · · Aun

)= UD =

(λ 1u1 λ 2u2 · · · λ nun

)where the entries denote the columns of AU and UD respectively. Therefore, Aui = λ iuiand since the matrix is unitary, the i jth entry of U∗U equals δ i j and so

δ i j = uTi u j = uT

i u j = ui ·u j.

This proves the corollary because it shows the vectors {ui} form an orthonormal basis.In case A is real and symmetric, simply ignore all complex conjugations in the aboveargument. ■

13.3 Least Square ApproximationA very important technique is that of the least square approximation.

Lemma 13.3.1 Let A be an m× n matrix and let A(Fn) denote the set of vectors in Fm

which are of the form Ax for some x ∈ Fn. Then A(Fn) is a subspace of Fm.

Proof: Let Ax and Ay be two points of A(Fn) . It suffices to verify that if a,b are scalars,then aAx+bAy is also in A(Fn) . But aAx+bAy = A(ax+by)∈ A(Fn) because A is linear.■

Lemma 13.3.2 Suppose b≥ 0 and c∈R such that a+bt2+ct ≥ a for all t ∈R, then c= 0.

Proof: You need bt2 + ct ≥ 0 for all t. The slope of t 7→bt2 + ct is c when t = 0. Thusthe inequality is violated unless c = 0. ■

The following theorem gives the equivalence of an orthogonality condition with a mini-mization condition. The following picture illustrates the geometric meaning of this theorem