LINEAR ALGEBRA Appendix A in Stoica Moses Ch 2 3 in Hayes Here we follow Ch 2 3 in Hayes 2 3 1 Vectors Let signal be represented by scalar values x1 x2 xN Then the vector notation is x1 x2 x xN Vector transpose xT x1 x2 xN Hermitian transpose xH xT x 1 x 2 x N Sometimes it is convenient to consider sets of vectors for EE 524 Fall 2004 6 1 example x n x n 1 x n x n N 1 Note Stoica and Moses use to denote the Hermitian transpose Magnitude of a vector Vector Euclidean norm kxk N X 1 2 2 xi xH x i 1 Scalar inner product of two complex vectors a a1 aN T and b b1 bN T aH b N X a i bi i 1 Cauchy Schwartz inequality aH b kak kbk where equality holds only iff a and b are colinear i e a b EE 524 Fall 2004 6 2 Orthogonal vectors aH b bH a 0 Example Consider the output of a linear time invariant LTI system filter y n N 1 X h k x n k hT x n k 0 where h 0 h 1 h h N 1 x n x n 1 x n x n N 1 2 3 2 Linear Independence Vector Spaces and Basis Vectors A set of vectors x1 x2 xn is said to be linearly independent if 1x1 2x2 nxn 0 1 implies that i 0 for all i If a set of nonzero i can be found so that 1 holds the vectors are linearly dependent For EE 524 Fall 2004 6 3 example for nonzero 1 x1 2x2 nxn Example 2 3 2 1 x1 2 1 1 x2 0 1 linearly independent 0 1 1 x1 2 x2 0 x3 1 linearly dependent 0 1 1 because x1 x2 2x3 Given N vectors v 1 v 2 v N consider the set of all vectors V that may be formed as a linear combination of the vectors v i N X v iv i i 1 This set forms a vector space and the vectors v i are said to span the space V If v i s are linearly independent they are said to form a basis for the space V and the number of basis vectors N is referred to as the space dimension The basis for a vector space is not unique EE 524 Fall 2004 6 4 2 3 3 Matrices n m matrix A aij a11 a12 a13 a21 a22 a23 a31 a32 a33 an1 an2 an3 a1m a2m a3m anm If n m then A is a square matrix Symmetric matrix AT A Hermitian matrix AH A Some properties apply to transpose A B H AH B H T as well AH H A AB H B H AH Column and row representations of an n m matrix rH 1 rH 2 A c1 c2 cm rH n EE 524 Fall 2004 6 2 5 2 3 4 Matrix Inverse Rank Discussion The rank of A of linearly independent columns in 2 of linearly independent row vectors in 2 i e of linearly independent vectors in r 1 r 2 r n Important property rank A rank AAH rank AH A For any n m matrix A rank A min n m If rank A min n m A is said to be of full rank If A is a square matrix of full rank then there exists a unique matrix A 1 called the inverse of A A 1A AA 1 I where 1 0 0 1 I 0 0 0 0 is called the identity matrix 0 0 1 0 0 0 0 1 If a square matrix A of size n n is not of full rank i e rank A n then it is said to be singular Properties AB 1 B 1A 1 AH 1 A 1 H EE 524 Fall 2004 6 6 Useful Matrix Inversion Identities Matrix Inversion Lemma A BCD 1 A 1 A 1B C 1 DA 1B 1DA 1 for arbitrary square nonsingular A and C In the special case where C is a scalar B b is a column vector and D dH is a row vector For C 1 we obtain the Woodbury identity H 1 A bd EE 524 Fall 2004 6 H 1 1 A b d A 1 A H 1 1 d A b 7 2 3 5 The Determinant and the Trace The determinant of an n n matrix for any i det A n X 1 i j aij det Aij j 1 where Aij is the n 1 n 1 matrix formed by deleting the ith row and the jth column of A Example a11 a12 a13 A a21 a22 a23 a31 a32 a33 a a a21 a23 det A a11 det 22 23 a12 det a32 a33 a31 a33 a21 a22 a13 det a31 a32 Property an n n matrix A is invertible nonsingular iff its determinant is nonzero det A 6 0 EE 524 Fall 2004 6 8 Properties of the determinant for n n matrix A det A n det A det AB det A det B 1 1 det A det A det AT det A Another important function of a matrix is trace tr A n X aii i 1 EE 524 Fall 2004 6 9 2 3 6 Linear Equations Many practical DSP problems e g signal modeling Wiener filtering etc require solving a set of linear equations a11x1 a12x2 a1mxm b1 a21x1 a22x2 a2mxm b2 an1x1 an2x2 anmxm bn In matrix notation Ax b 3 where A is an n m matrix with entries aij x is an m dimensional vector of xi s and b is an n dimensional vector of bi s For A a1 a2 am we can view 3 as an expansion of b m X b xiai i 1 EE 524 Fall 2004 6 10 Square matrix A m n The nature of the solution depends upon whether or not A is singular Nonsingular case x A 1b Singular case no solution or many solutions Example x1 x2 1 x1 x2 2 no solution x1 x2 1 x1 x2 1 EE 524 Fall 2004 6 many solutions 11 Rectangular matrix A m n More equations than unknowns and in general no solution exists The system is called overdetermined When A is a full rank matrix and therefore AH A is nonsingular a common approach is to find the least squares solution i e the vector x that minimizes the Euclidean norm of the error vector kek2 kb Axk2 EE 524 Fall 2004 6 12 b Ax H b Ax bH b xH AH b bH Ax xH AH Ax H 1 H H H H 1 H x A A A b A A x A A A b bH b bH A AH A 1AH b The second term is independent of x solution is Therefore the LS xLS AH A 1AH b EE 524 Fall 2004 6 13 The best …