Math 1b Prac — The Gram-Schmidt process; orthogonal projectionJanuary 24, 2011 — extended/revised January 28, 2011To warm up, we start withTheorem 1. Nonzero pairwise orthogonal vectors u1, u2,...,ukare linearly independent.Proof: Suppose u1, u2,...,ukare nonzero orthogonal vectors and thatc1u1+ c2u2+ ...+ ckuk= 0.Given i, take the inner product of both sides with uito getc1u1, ui + ...+ ciui, ui + ...+ ckuk, ui = 0, ui =0.Most of the inner products on the left are zero, and the only s u rviving term isciui, ui = ci||ui||2=0,and because ||ui||2= 0, it must be that ci= 0. This holds for all i =1, 2,...,k,andthismeans that u1, u2,...,ukare linearly independent. To save typing, we b orrow the description of of the Gram-Schmidt process from theWikipedia article.The definition of proju(v) should be modified to include the case when u = 0 ,wherewe understand proj0(v)=0.Exercise:Ifx − cu is orthogonal to u =0,thenc =x, u /u, u , i.e. cu =proju(x).Example. Letv1=(1, 1, 1, 1, 1),v2=(0, 1, 2, 3, 4),v3=(0, 1, 4, 9, 16).Thenu1=(1, 1, 1, 1, 1),u2=(−2, − 1, 0, 1, 2),u3=(2, −1, −2, −1, 2).Theorem 2. The vectors u1, u2, u3,... produced by the Gram-Schmidt process are pair-wise orthogonal.Proof: We need to check that ui, uj =0fori = j. We proceed by induction on k.Suppose we know ui, uj =0for1≤ i<j≤ k − 1. Then for i<k,ui, uk = ui, vk−proju1(vk)+proju2(vk)+...+projuk−1(vk) = ui, vk −ui, proju1(vk) + ...+ ui, projuk−1(vk) .Since projuj(x) is a scalar multiple of uj, all the terms ui, projuj(vk) are 0 exceptpossibly when i = j, and we haveui, uk = ui, vk −ui, projui(vk) = ui, vk −ui,ui, vk ui, ui ui = ui, vk −ui, vk ui, ui ui, ui =0.Note that if u1, u2, u3,... are nonzero orthogonal vectors, and we let ei= ui/||ui||,then e1, e2, e3,... are orthonormal vectors. Orthonormal means that the vectors are or -thogonal and that they each have length 1. The standard basis in Rnis only one exampleof an or thonormal bas is for Rn.Theorem 3. Let u1, u2,...,ukbe the vectors produced from v1, v2,...,vkby the Gram-Schmidt or thogonalization pro ces s ; let U and V be the matrices whose rows are, respec-tively, u1, u2,...,ukand v1, v2,...,vk. Then there are (square) lower triangular matricesE and F with 1’s on the diagonal so that U = EV and V = FU.Proof: Omitted. Example. To continue our p revious example,⎛⎝1111 10123 4014916⎞⎠=⎛⎝100210641⎞⎠⎛⎝11111−2 −10 122 −1 −2 −12⎞⎠and⎛⎝11111−2 −10 122 −1 −2 −12⎞⎠=⎛⎝1002102 −41⎞⎠⎛⎝1111 10123 4014916⎞⎠.A related fact is that a matrix A canbewrittenasA = LQ where L is a squarelower triangular matrix and the nonzer o rows of Q are orthonormal (orthogonal and ofunit length).Example:⎛⎝1111 10123 4014916⎞⎠=⎛⎝√50 02√5√10 06√54√10√14⎞⎠⎛⎝1/√51/√51/√51/√51/√5−2/√10 −1/√10 0 1/√10 2/√102/√14 −1/√14 −2/√14 −1/√14 2/√14⎞⎠Recall from geom etry that the area of a parallelogram is the p roduct of the “base”and the “altitude”. If the parallelogram is spanned by two vectors v1and v2and wetake v1as the base, then the altitude is the length of u2and the area is ||u1|| · ||u2||.More generally, the k-dimensional volume of a parallelopided is the product of the (k −1)-dimensional volume of a (k − 1)-dimensional base and the altitude. This leads to thefollowing theorem.Theorem 4 . Let u1, u2,...,ukbe the vectors obtained from v1, v2,...,vkby the Gram-Schmidt process. The k-dimens ional volume of the parallelopiped spanned by v1, v2,...,vkis the same as that of the parallelopiped spanned by u1, u2,...,uk, and this volume is||u1||·||u2||···||uk||.As in the proof of Theorem 2, if u1,...,ukare (pairwise) orthogonal and nonzerovectors in Rnand x is any vector in Rn,thenu =ki=1x, ui ui, ui ui(∗)is such that u, ui = x, ui for i =1, 2,...,k, and thus x−u ∈ U⊥.Thenu1,...,uk, x−uis a larger s et of orthogonal vectors . This observation leads to the following theorem .Theorem 5. Any subspace of Rnhas an orthogonal basis.Theorem 6. Let U be a subspace of Rn. Then any vector x can be written uniquely asasumx = u + w where u ∈ U and w ∈ U⊥. The vector u is the unique closest vector tox in U.Proof: Choos e a basis for U.Givenx,letu be as in (∗)andletw = x−u.Thenx = u+w,u ∈ U,andw ∈ U⊥.Ifu ∈ U,then||x − u ||2= ||w +(u −u )||2= ||w||2+ ||u −u ||2≥||w||2= ||x − u||2,since w and u − u are or thogonal, and equality will hold if and only if u = u.Theuniqueness of this expression is left as an exercise. The vector u as in the statement of Theorem 6 (or as in (∗)) is called the orthogonalprojection of x onto the subspace U and denoted by pr ojU(x). So w =projU⊥(x). Thevector u −w = x − 2w is called the reflection of x through U and is denoted by r eflU(x).Remark: The connnection between least-squares (approximate) solutions of Az = band orthogonal projection is this. The column space U is the set of all vectors Az as zranges o ver Rn,whenA has n column s . If the orthogonal pr ojection of b onto the columnspace of A is b = Az0,thenz0is a least-squares (approximate) solution. If the columns ofA are linearly d ependent, there will b e many solutions of Az = b , so that’s why there mayb e numerous least-squares solutions even though there is only one orthogonal projection.Both projU(·)andreflU(·) are examples of linear transformations or linear mappingsfrom Rnto Rn. This means (or is equivalent to the statement) that there are n×n matricesP and R so thatprojU(x)=P x and reflU(x)=Rx.A mapping γ from Rnto Rmis said to be linear when γ(a + b)=γ(a)+γ(b) for allvectors a and b in Rn,andγ(ca)=cγ(a) for any scalar c and vector a.IfM is an m ×nmatrix, then the mapping x → Mx is, it is easy to see, a linear mapping. It turns outthat every linear mapping arises from a matrix, but the reader need not know this, or thedefinition of linear mapping, at this point. It will not be on the midterm.Theorem 7 . If the columns of an n×k matrix A form a basis for a k-dimensional subspaceU of Rn(thought of as columns vectors), thenprojU(x)=P x where P = A(AA)−1A.Proof: It is important to know that the k ×k matrix AA is nonsingular when A has rankk.Thisisleftasanexercise.Write x = u + w where u ∈ U and w ∈ U⊥.WewanttoshowP x