matrix-analysis-w8

實變函數論─應用數學系 吳培元老師 1 Matrix Analysis 第八週課程講義   1 1 1 1 -1 1 -1 Pf:" ": Let ,... be o.n. eigenvectors of . . . ,..., . Let ,... unitary. Let be 1, ,..., Let * Then 1, * ,... * n n n j j y y A w r t U y y x x x W W y U x y y U W U W             || * 1 1 1 1* 1 1 1 , , = * ,y ... = , n n n n n n Ax x AUy Uy U AUy y y y y y y y                                     1 2 1 , where . = n n n i i i y y y y y                       1 -1 2 2 1 -1 1 1 2 2 1 -1 1 1 min , : 1, ,... || \\ = min : 1, * ,..., * . min : 1, * ,..., * j n n i i i j i i n n i i i j i i Ax x x x W W y y y U W U W y y y U W U W                         1 j 2 2 1 -1 1 1 1 & ... 0 . = min : 1, * ,..., * & ... 0 \ max min " j n j i i i j j n i i j j y y y y y U W U W y y                               ": by Thm. 2. 實變函數論─應用數學系 吳培元老師 2     1 1 Ex. ran = ker *, ker =ran * Applications: (I) eigenvalue comparison: Thm1. , Hermitian, , , ,( .) ( ): ... ( ) : ... Then n n n j j A n n A A A A A B n n Ax x Bx x x A B A B u u u j                           1 -1 1 -1,..., Pf: = max min , : , 1, ,..., / , min , max min , = (II) rank-1 perturbation: Thm2. , j n j jW W j u Bx x x x x W W Ax x Ax x Ax x A B n          1 1 1 1 2 2 1 Hermitian, & rank( - )=1, ( ): ... , ( ) : ... ... (interlacing property) Pf: Check: Let - = max min ( ) , max min ( n n n n j j j n A B B A A B u u u u u u F B A u A F x x                                  1 -1 1 -1 ) , : 1, ,..., , , where ran V . ,..., || , ran j j A F x x x x W W y F y W W Ax x x F        1 -1 1 1 = ker *= ker max min , : 1, ,..., ,..., = j j j F F Ax x x x W W W W       1 1 Thm3. Hermitian, 0 & ran ... : ( ) ... : ( + ) Then (III) Principal submatrix: * Thm4. , where A (n+1) (n+1) Hermitian, * * n n j j j r A n n F n n F r A u u A F u j B A B n n                         1 +1 1 1 1 2 +1 . ... : ( ) ... : ( ) Then ... (interlacing property) n n n n n A u u B u u                   實變函數論─應用數學系 吳培元老師 3  1 1 -1 1 -1 1 1 Pf: (i) = max min , : , 1, ,..., ,..., ˆ let , - with la 0 j j n j j j n k k n u Ax x x x x W W W W x x y x y W W x                                 1 1 -1 1 -1 st component deleted. 0 max min y, y : , y 1, y ,... , 0 1 || ˆ ˆˆ ˆ ˆ ˆ ˆ = max min , : : 1, ,..., n j n j A y W W By y y y y W W u                      1 -1 ˆ ˆ ,..., j jW W   +1 1 +1 2 1 2 1 1 j+2 n+1 (ii) : = min max , : 1, , ,... ,..., 0 min max y, y : y 1, y , y ,... , 0 1 j j n j j n j n n u Ax x x x x W W W W A W W                                2 1 j+1 j+2 n 1 ,..., ˆ ˆ ˆˆ ˆ ˆ ˆ ˆ = min max , : 1, , , ... ˆ ˆ ,..., j n n j n j W W By y y y y W W W W W u         1 1 - 1 More generally : * Thm5. , Hermitian, * * ... : ( ) ... : ( ) Then . Converses of (I) & (II): Thm6. Hermitian, ... : eigenval n k j j j n k n B A n n B k k A u u B u j A n n                          1 1 2 2 1 ues of . Assume ... 0, rank =1 ( + ): ... . n n n A u u u F F A F u u                 實變函數論─應用數學系 吳培元老師 4 1 1 1 2 2 +1 1 +1 Thm7. Hermitian, ... : ( ) Assume ... . * Then Hermitian with eigenvlaues: ... . * * Ref: R. Bhatia, Matrix analysis, p.61, Thm. III.1.9 Othe n n n n B n n u u B u u u B                      r developments: (1) , Hermitian eigenvlaues of & + ? (2) , singular values of & + ? (3) Hermitian eigenvlaues of & diagonal entries of ? A B A A B A B A A B A A A Normal matrix: Def. normal if * * Hermitian (self-adjoint) if * 0 (positive semidefinite) if , 0 >0 (positive definite) if , >0 n T n n T TT T T T T T T Tx x x T Tx x x           0 in . unitary if * * I . n nT T T TT   Note1. Hermitian , Note2. Hermitian , or unitary T normal 0, or>0 nT Tx x x T T          實變函數論─應用數學系 吳培元老師 5 1 Spectral thm. for normal matrices: normal , i.e. diagonalizable under unitary equiv. n T n n T T              Jordan form of normal T T Pf: " " Schur-triangulaton; norm of rows & columns same: * ; let jTx T x x x e     need polar identity Under this situation, 1 cyclic 's distinct 2 Hermitian j j T T       3 0 0 4 > 0 > 0 5 unitary =1 . j j j j T j T j T j             2 1 2 1 Thm. 0 unique 0 ||| (square root of ). Pf: Existence Let n T n n X X T T T T U            1 2 *, where unitary & 0 . Let * Then 0 & . j n U U j X U U X X T                      實變函數論─應用數學系 吳培元老師 6 2 1 1 1 1 1 2 2 1 1 1 1 1 Uniqueness: Assume 0 & . * * * n n n x x T X T Y Y Y Y                                                       2 2 1 1 1 1 YY Y Y 1 1Prove only for differ. eigenvalues May assume =...= Check: =n Y              1 1 1 1 2 1 2 1 2 2 1 2 1 Let * * *= . = . n n n n j W YW Y W W Y W W j Y                                                                               1 1 * . n X U U X                   實變函數論─應用數學系 吳培元老師 7   1 2 1 2 1 1 1 2 Note: ( ) for some poly p. Alg = Pf. Let be a poly ( ) . = = ( ). interpolating poly: only requirement: i i nn i j T p T T T T p p i p T p T                                        .i j Polar decomposition: where 1 & 0. Note: unique 0. z z u u z             Thm. , where unitary & 0 Uniqueness: Note1. In general, unique invertible, (by proof below). 0 1 0 1 0 0 0 1 0 0 Ex. = 0 0 1 0 0 1 0 0 1 Note2 i i T n n T UP U P U T T e P                                    2 1 2 s unique Pf: If , then * ( *)( ) ( * ) is unique || T UP T T PU UP P P T T T      1 2 * * * 1/2 Pf. of Thm: Existence: Let ( * ) 0. Define : ker ran ker ran || ran ( ) n n P T T U T T T T T T         1 2 : ( * ) V ,U x T T y x Ty  * * 21 1 1 2 * * * *2 2 2 * 1/2 * * 1/2 where : ker ker is isometric onto.( look at Jordan form of and ) , , ( ) , ( ) ( ) ker ker( ) ran ran( ) V T T T T Ty Ty Ty T Ty y T T y T T y T T y T T T T T T           well-defined, isometric U unitaryU  實變函數論─應用數學系 吳培元老師 8 1 2 1 || 1 Singular value decomposition (SVD): Def: Let ... 0 be eigenvalues of ( * ) singular values of Thm. , where , are unitary. n n T n n s s T T T s T n n T V W V W s                  1 1 1 ... 0 (singular values of ) are unique. Pf: Existence :Let be polar decomposition of . Let * , where unitary & . * Uniqueness n n n s s A T UP T s P W DW W D s s T UW W s                       1 1 * 1 * : Assume , where , unitary & 0 Then ( )( ) Unitary / 0 Polar decomposition of . j n n s T V W V W s j s s T VW W W s T s W                        1 2( * ) ' are singular values of . n j W T T s s s T         實變函數論─應用數學系 吳培元老師 9             1 1 1 1 1 1 Other expressions for SVD (I) ... ... = ( ) = , where othogonal & o.n. n n n n n n j j j j j j j j j j j s w T v v s w s v w s v w s v w u w u s v w                                    1 1 1 1 1 1 1 1 Notation: , , , is an rank-one matrix with range V (II) T: . Then o.n. bases ... & ... of w.r.t. wh n n n n T n n n n n n n n x x y x y y y x x y x y x y xy n n x x y x y e e f f                              1 ich has 0 matrix representation 0 n T s s     實變函數論─應用數學系 吳培元老師 10 rank T Summary: 1 1 (1) invertible & 0 0 Cor. , r T n n X Y XTY A B n n                     -1 . Then invertible , =B rank rank . Pf: row operations column operations (2) invertible =Jordan form Cor. , . X Y XAY A B X Y T n n X X TX A B n n            1 j Then , have same Jordan form (3) unitary & = , where s 0 . Cor. , . Then unitary & , have same singular v n A B A B s T n n V W VTW j s A B n n V W VAW B A B                    -1 alues. (4) (?) Note: , . Then for some unitary tr w( *, ) tr ( * ) word w( , ) Note: Each of the above can be interpreted in terms of bases & linear tr A B n n A U BU A A w B B       ansf.