godok.id

4. kv PW vk kv wk 8w 2 W : This is a very strong result: it tells us theorthogonal projection is the best approximation to v through vectors in W:This is a key result which justi es the use of the projection in applicationssuch as least squares, polynomial interpolation and approximation, fourierseries, etc. In fact, this result can be extended to projection on convexsets in Hilbert spaces.5. kPW vkkvk 8v 2 W : This tells us the projection is a contraction. Inparticular, we know that kP k 1; since there are vectors (namely, thosein W ) for which equality holds.6. hPW u; vi hu; PW vi 8u; v 2 V (PW is "self-adjoint"). This can beproved explicitly using the unique decomposition of u and v as the sum ofcomponents in W and W ? . In particular, this also tells us that the matrixwhich represents PW is symmetric / self-adjoint as well if we choose a basisof orthonormal vectors.7. It can be shown that properties (1) and (4), (1) and (5) or (1) and (6)completely characterize the orthogonal projection. That is, from theseproperties alone we can deduce the rest, and that the operator P has tobe a projection onto its range.4.2The Gram-Schmidt Process and QR FactorizationWe can ask ourselves if, for any basis in V there exists a procedure to turn itinto an orthonormal basis. The Gram-Schmidt Process does exactly this, andas a by-product it also gives us a very useful matrix factorization, QR:Theorem 21 (Gram-Schmidt) If fwi gmi 1 is a linearly independent set, theremexists an orthonormal set fui gmsuchthatspan(fui gmi 1i 1 ) span(fwi gi 1 ): Itcan be constructed through the following process:89k X1 hwk ; vj ivj Pspan(fvi gk 1 )? (wk )v1 w1 , vk wki 1:;hvj ; vj ij 1u1 v1kv1 k,uk vkkvk kFurthermore, by completing fwi gmi 1 to a full basis of V (if malways obtain an orthonormal basis of V following this process.n), we canTheorem 22 (QR Factorization) Let A be a matrix of full column rank,with columns fwi gmi 1 : Then , by applying Gram-Schmidt to the columns of A(augmenting them to obtain a full basis if m n); we obtain the following:wk kvk k uk kX1j 18hwk ; uj i uj 8k

If we write this in matrix form, where Q is a matrix with columns fui gni 1 (byde nition, this is an orthogonal / unitary matrix) and Rkk kvk k ; Rjk hwk ; uj i if k j (upper triangular matrix), this last expression provides thefollowing matrix factorization for A:0kv1 k hw1 ; u2 i0101B 0kv2 kjjjjjjjjjj BB@A@Awm QR u1um um 1un B 0A w1 w20Bjjjjjjjjjj @ 0000This is, A (Q1 j Q2 )A.R10 Q1 R1 , where Q1 has the same column space asThis factorization is very useful both to solve linear systems of equations(there are e cient ways to compute QR; namely the Householder algorithm andother sparse or incomplete QR routines) because, once computed, the systemAx b is equivalent to solving:Rx Q bWhich can be rapidly solved through backward or forward substitution (since Ris upper triangular). Also, QR factorization is extensively used to obtain easierformulas for certain matrix products that appear in applications such as OLSand smooth splines.A relevant result regarding this matrix factorization is that, although it isnot unique in general, if we have that A Q1 R1 Q2 R2 , then it can be shownthat D R2 R1 1 is a diagonal, unitary matrix.4.3Riesz Representation Theorem and The Adjoint OperatorFor any linear operator T 2 L(V; W ); we can obtain a related operator T 2L(W; V ) called the adjoint operator, which has very interesting properties. Thisoperator becomes even more relevant for applications to vector spaces of in nitedimension. This operator is de ned as follows:De nition 23 Let T 2 L(V; W ). Then, the adjoint operator T 2 L(W; V ) isde ned by the following functional relation:hT v; wiW hv; T wiV 8v 2 V , w 2 WIf we choose orthonormal basis B and B 0 for V and W , then the matrix thatrepresents the adjoint is the conjugate transpose of the matrix that representsA: We get:hAx; yiRm hx; A yiRn 8x 2 Rn ; y 2 Rm00BBWhere A [T ]BB and A [T ]B 0 ([T ]B ) .9.00.1hwm ; u1 ihwm ; u2 iCCC.C.Ckvm k A0

The existence and uniqueness of this operator is given by the Riesz Representation Theorem for Hilbert Spaces:Theorem 24 (Riesz Representation) Let V vs F a Hilbert space, and T 2L(V; F ) a continuous, linear functional (element of the topological dual). Then,9!v 2 V such that:T u hu; vi 8u 2 VTherefore, the Adjoint operator is always well de ned by the functionalrelation we have outlined, parting from the linear functional Lw v hT v; wiW xing each w 2 W:Remark 25 Here is a quick application of the adjoint operator and the orthogonal projection operator: Let A 2 Mm n (F ); and Ax b a system of linearequations. Then the least squares solution to this system is given by the solutionto:rrrrrrrrrrrrAx0 PRan(A) (b)Since we are projecting b onto the column space of A; and we know this is thebest approximation we can have using linear combinations of the columns of A:Using properties of the projection operator, we now know that:Ax; bhAx; bPRan(A) (b) 0 8xAx0 i 0Now, using the adjoint of A; we nd:hx; A bA Ax0 i 0 8xSo, this means A b A Ax0 ; and therefore, if A A is invertible, this meansx0 (A A) 1 A byb Ax0 A(A A)1A bIncidentally, this also tells us that the projection matrix of a vector onto thecolumn space of a matrix A is given by PRan(A) A(A A) 1 A .Properties of the Adjoint: (T 2 L(V; W ))1. (T S) T S2. ( T ) T3. (T ) T4. IV IV (the identity is self-adjoint)5. (ST ) T S10

0B6. B and B 0 orthonormal basis of V and W () then [T ]BB 0 ([T ]B )(be careful, this is an () statement)The most important property of the adjoint, however, provides us with anexplicit relation between the kernel and the image of T and T . These relationscan be deduced directly from the de nition, and provide us with comprehensivetools to study spaces V and W:Theorem 26 ("Fundamental Theorem of Linear Algebra II") Let V; W nite dimentional Hilbert spaces, T 2 L(V; W ): Then:Ker(T ) Ran(T )?Ran(T ) Ker(T )?Thus, we can always write V Ker(T ) Ran(T ) and W Ker(T ) Ran(T ).Proof. (Ker(T ) Ran(T )? ): Let v 2 Ker(T ); and any T u 2 Ran(T ); thenv 2 Ran(T )? () hT u; vi 0 8u () hu; T vi 0 8u () v 2 Ker(T ).The proof of the second statement can be found replacing T and T above.A couple of results that follow from this one are:1. T is injective () T is onto2. Ker(T T ) Ker(T ), and thus, r(T T ) r(T ) r(T ) (rank).5Normal and Self-Adjoint Operators: SpectralTheorems and Related ResultsDepending on the eld F we are working with, we can obtain " eld sensitive"theorems that characterize diagonalizable operators. In particular, we are interested in the cases where the eld is either R or C: This discussion will alsoyield important results on isometric, unitary and positive operators.De nition 27 T 2 L(V ) is said to be a self-adjoint operator if TT . IfF R, this is equivalent to saying [T ]B is symmetric, and if F C, that [T ]Bis Hermitian (equal to its conjugate transpose).De nition 28 T 2 L(V ) is said to be normal if it commutes with its adjoint,that is, if T T T T:Remark 29 If F R, then an operator T is normal and it is not self-adjoint() 8B orthogonal basis of V , [T ]B is a block diagonal matrix, with blocks ofsize 1 and blocks of size 2 which are multiples of rotation matrices.First, we introduce a couple of interesting results on self-adjoint and normaloperators:11

Proposition 30 T 2 L(V ); F C then there exist unique self-adjoint operators T1 and T2 such that T T1 iT2 : T is then self-adjoint () T2 0, andis normal () T1 T2 T2 T1 : These operators are given by:T1 T T2, T2 TT2iProposition 31 If T 2 L(V ) is normal, then Ker(T ) Ker(T ) and Ran(T ) Ran(T ):The most important properties of these families of operators, however, haveto do with the spectral information we can retrieve:Proposition 32 T 2 L(V ) and self-adjoint and F C: Ifof T , then 2 Ris an eigenvalueProof. For u eigenvector, we have:hu; ui hu; T ui hT u; ui hu; uiProposition 33 T 2 L(V ) and F C: T is self-adjoint () hT v; vi 2 R8v 2 VProof. Using both self-adjoint and properties of the interior product:hT v; vi hv; T vi hT v; vi 8v 2 VThis, in particular tells us the Rayleigh quotient for such an operator isalways real, and we can also rederive last proposition.Proposition 34 If T 2 L(V ) is a normal operator,i) kT vk kT vk 8v 2 Vii) TI is normal 8 2 Ciii) v is an eigenvector of T () v is an eigenvector of TProof. (i): hT v; T vi hv; T T vi hv; T T vi hT v; T vi(ii): (TI) (TI) T TI(T T ) 2 I T TI(T T ) 2 I (TI)(TI)(iii): (TI)v 0 ) k(TI) vk 0 (by i and ii) () (TI) v 012

Theorem 35 (Spectral Theorem, F C Version) V vs C nite dimentional Hilbert space. T 2 L(V ). V has an orthonormal basis of eigenvectors ofT () T is normal.Proof. (( ) By Schur’s factorization, there exists a basis of V such that [T ]B isupper triangular. By Gram-Schmidt, I can turn this basis into an orthonormalone Q, and by studying the QR factorization, we realize the resulting matrixis still upper triangular. However, since the basis is now orthonormal, andT is normal, it follows that [T ]Q is a normal, upper triangular matrix. Thisnecessarily implies [T ]S is diagonal (We can see this by computing the productsof the o -diagonal elements, and concluding they have to be zero in order forthis to hold).( )) If this is the case, then we have Q an orthonormal basis and diagonalsuch that [T ]Q : Since a diagonal matrix is always normal, it follows that Tis a normal operator.Theorem 36 (Spectral Theorem, F R Version) V vs R nite dimentional Hilbert space. T 2 L(V ). V has an orthonormal basis of eigenvectors ofT () T is self-adjoint.Proof. We follow the proof for the complex case, noting that, since F R; bothSchur’s factorization and Gram-Schmidt will yield matrices with real entries.Finally a diagonal matrix with real entries is always self-adjoint (since this onlymeans that it is symmetric). We can also apply the theorem for the complexcase and use the properties for self-adjoint operators.In any case, we then have the following powerful properties:1. V kMi 1Eiand (E i )? ME8ijj6 i2. If we denote Pj PE j , then Pi Pj ij3. (Spectral Resolution of Identity)IV kXPii 14. (Spectral Resolution of T )T kXi Pii 1These properties characterize all diagonalizable operators on nite dimensional Hilbert spaces. Some important results that follow from this are:13

Theorem 37 (Cayley-Hamilton) T 2 L(V ); V nite dimensional Hilbert space.If p is the characteristic polynomial of T; then p(T ) 0.Theorem 38 V vs C and T 2 L(V ) normal, then 9p 2 C[x] polynomial suchthat p(T ) T . This polynomial can be found by the Lagrange Interpolationproblem fp( i ) i gki 1We also have the following properties for T normal, which we can now deduceusing the spectral decomposition of T . These properties basically tell us that, ifT is normal, we can operate it almost as if it were a number through its spectralrepresentation.Pk1. If q is a polynomial, then q(T ) i 1 q( i )Pi2. If T p0 for some p, then T03. An operator commutes with T () it commutes with each Pi4. T has a normal "square root" (S such that S 2 T )5. T is a projection () all its eigenvalues are 00 s or 10 s:6. T 5.1T (anti-adjoint) () all eigenvalues are pure imaginary numbersUnitary OperatorsDe nition 39 An operator T 2 L(V ) is said to be orthogonal (R) / unitary(C) if kT vk kvk 8v 2 V (this means T is a linear isometry, it is a "rigidtransformation"). A unitary operator can also be characterized by T normaland T T T T IV :Theorem 40 (Mazur-Ulam) If f is an isometry such that f (0) 0 and f isonto, then f is a linear isometry (unitary operator)Theorem 41 The following statements are equivalent for T 2 L(V ) :i) T is an isometryii) T T T T IViii) hT u; T vi hu; vi 8u; v 2 Viv) If B is an orthonormal basis, T (B) is an orthonormal basisv) There exists an orthonormal basis of V such that T (B) is an orthonormalbasis.Theorem 42 If is an eigenvalue of an isometry, then j j 1. T is then anisometry () T is an isometry as well.14

5.2Positive Operators and Square RootsDe nition 43 V a nite dimensional Hilbert Space, T 2 L(V ). We say T isa positive operator if T is self-adjoint and hT v; vi 0 8v 2 VRemark 44 A matrix A is said to be a positive operator (positive semide nitematrix) if hAx; xi x Ax 0 8x 2 F nRemark 45 If F C, we can remove the assumption that T is self-adjoint.Remark 46 The operators T T and T T are always positive. In fact, it canbe shown any positive operator T is of the form SS : This is a general versionof the famous Cholesky factorization for symmetric positive de nite matrices.Proposition 47 T is a positive operator () T is self-adjoint and all itseigenvalues are real and non-negative.Some properties of positive operators:1. T; U 2 L(V ) positive operators, then T U is positive2. T 2 L(V ) is positive ) cT is positive 8c3. T 2 L(V ) is positive and invertible ) T01is positive4. T 2 L(V ) positive ) T 2 is positive (the converse is false in general)5. T; U 2 L(V ) positive operators, then T U U T implies T U is positive.Here we use heavily that T U U T implies there is a basis of vectorswhich are simultaneously eigenvectors of T and U:De nition 48 T 2 L(V ): Then we say S is a square root of T if S 2 T .We note that, in general, the square root is not unique, For example, theidentity has an in nite number of square roots: permutations, re‡ections androtations by 180 : However, we can show that, if an operator is positive, thenit has a unique positive square root.Proposition 49 T 2 L(V ) is positive () T has a unique positive squareroot.15

66.1Singular Value Decomposition and the MoorePenrose Generalized InverseSingular Value DecompositionThe Singular Value Decomposition for T 2 L(V; W ) (and the correspondingfactorization for matrices) is, without a doubt, one of the most useful resultsin linear algebra. It is used in applications such as Least Squares Regression,Smooth Spline and Ridge Regression, Principal Component Analysis, MatrixNorms, Noise Filtering, Low Rank approximation of matrices and operators,etc. This decomposition also enables us to de ne a generalized inverse (alsoknown as the pseudoinverse), and to compute other decompositions, such as thePolar decomposition for positive operators and computing positive square rootsexplicitly.Theorem 50 (Singular Value Decomposition, or SVD) Let V; W vs F Hilbertspaces, T 2 L(V; W ) with rank r. Then, there exist orthonormal basis of V andW fv1 ; ::; vn g and fu1 ; ::; um g, as well as positive scalars 1:::2r 0such that:T viT vi i ui0; i r; i rThese scalars are called the "singular values" of T . Conversely, if basis andscalars like these exist, then fv1 ; ::; vn g is an orthonormal basis of eigenvectorsof T T such that the rst r are associated to the eigenvalues 21 ; :::; 2r , and therest are associated to 0.Using what we know about positive operators, we can see how the statement of this theorem must always be true. Regardless of what T is, T T isa positive operator, and therefore diagonalizable, with nonnegative eigenvalues f 21 ; :::; 2r g and possibly also 0: Then, we obtain the set of fu1 ; ::; um g bycomputing T vi i ui for the rst r vectors, and then completing it to anorthonormal basis of W .Also, this theorem immediately has a geometric interpretation: by choosingthe "right" basis, we know exactly what is the action of T on the unit sphere.Basically, T sends the unit sphere to the boundary of a r dimensional ellipsoid(since it squashes fvr 1 ; ::; vn g to zero), with axis on the rst r u0i s: Also, thebiggest axis of this ellipsoid is the one in the direction of u1 ; and the smallestis the one in the direction of ur .Finally, we note that this theorem applied to a matrix A 2 Mm n (F ) yieldsthe following matrix factorization: If V; U are unitary matrices with fv1 ; ::; vn gand fu1 ; ::; um g as columns, and if is the matrix in Mm n (F ) with all zeros16

except forii ifor i0jA U V @u 1jr, then:10j BB0un A BB.j @ .0jj01.0CC0 CBC@0 A0.r0100nrv1.vm1CAThis factorization is known as the Singular Value Decomposition, or SVD factorization of A:We know that, for the system of equations Ax b, the best approximationis given by the solution of A Ax A b. By using the SVD, we can alwayscompute the solution with minimum norm:Given an SVD for A; A U V , we have the following:kAxbk kU V x bk k V x Q bkSince U is a unitary matrix. Therefore, all we need is to minimize k yand then solve for x V y, c U b: However, it is clear that:k y2ck rXi 1j i yi2ci j nXi r 1ck ;2jci jWhich is minimized precisely when yi cii for ir and its minimum valuePn2is i r 1 jci j . If we want the y with minimum norm, all we have to do is tomake the rest of its coordinates zero.Now, solving for x; if we de ne:011001BCB 0 . 00 CyBC B .C.1@ .0 Ar00 0n rThen the solution for this problem is given by:x Vy Vyc (VyU )bFrom the properties of Least Squares, and this last formula, we already knowthat the matrix (V y U ) does the following:1. If b 2 Ran(A), (the system is consistent) then it gives us the solutionto Ax b with minimum norm. For any x 2 Rn ; we know we can writex PKer(A) x PKer(T )? x: Since A(PKer(A) x) 0; then (V y U )b is theunique solution in Ker(A)? .17

2. If b 2 Ran(A); (the system is inconsistent) then it projects b in CS(A);and then gives us the unique solution to Ax PRan(A) b in Ker(A)? :3. We can also deduce this from the fact that, from the construction ofthe SVD, the Fundamental Theorem of Linear Algebra II, and A V U ; that fv1 ; :::; vr g is a basis for Ker(A)? ; fvr 1 ; :::; vn g for Ker(A),fu1 ; :::; ur g for Ran(A) and fur 1 ; :::; um g for Ran(T )? .6.2The Moore-Penrose Generalized InverseTheorem 51 (Moore-Penrose Generalized Inverse) Given V; W vs F Hilbertspaces, T 2 L(V; W ) with rank r: There exists a unique linear operator, whichwe call the Moore-Penrose Generalized Inverse (or pseudoinverse, for short)T y : W ! V , such that, if S is the restriction of T to Ker(T )? , then:T y jRan(T ) S1As an extension of this inverse, it has the following properties:T yTTTPKer(T )?yPRan(T )Finally, if we have an SV D decomposition of T; the pseudoinverse T y can becomputed as:vj; j rT y uj jyT ujIn matrix form, if A [T ]UV, yA 0;[T ]VU ,then:yA Vyj rUThe following properties can be obtained for the SVD and the Pseudoinverse:1. Let A 2 Mm n (C). Then, A; A and A have the same singular values.Also, (Ay ) (A )y and (Ay ) (A )y2. (Moore-Penrose Conditions) Let T 2 L(V; W ). If an operator Uis such that: (a) T U TT , (b) U T UU and (c) U T and T U areself-adjoint then UT y . These conditions are a characterization of thepseudoinverse of T as a linear operator.3. We can check that the general formula for the projection to Ran(A) whichwe calculated with the adjoint matrix is:PRan(A) A(A A)y A AAy Uy0yUWhereis a diagonal matrix with 1 s in the rst r diagonal entriesand 00 s i

corollary of the Fundamental Theorem of Algebra, applied to the characteristic equation). Theorem 10 (Schur s factorization) V ev C; T 2 L(V): There always exists a basis B such that [T] B is upper triangular. 3.1 The Rayleigh Quotient and the Min-Max Theorem 3.2 Gershgorin s Discs Theorem