Linear Algebra - MA1002 Lecture Notes PDF

MA1002: Linear Algebra Dr. Jagannath Bhanja IIITDM Kancheepuram, Chennai Text books 1 Linear Algebra, Kenneth Hoffman and Ray Kunze, Prentice-Hall, Second Edition (available online). 2 Topics in Algebra, I. N. Herstein, Wiley. 3 Linear Algebra and its Applications, Gilbe...

MA1002: Linear Algebra Dr. Jagannath Bhanja IIITDM Kancheepuram, Chennai Text books 1 Linear Algebra, Kenneth Hoffman and Ray Kunze, Prentice-Hall, Second Edition (available online). 2 Topics in Algebra, I. N. Herstein, Wiley. 3 Linear Algebra and its Applications, Gilbert Strang, 4th edition. 4 Introduction to Linear Algebra, Krishnamurthi (BITS Pilani). 1 Evaluation Scheme (Tentative) Quiz 1 25 Quiz 2 25 End Semester Examination 50 2 Applications of Linear Algebra To summarize and manipulate data (Machine Learning, Image Processing) To model satellites, jet engines (Eigen values) Many more! Prepare a detailed report of an application of linear algebra tools in CSE/ECE/ME and Design You have first assignment ! 3 Mathematical Structures 1 Field (Members are called scalars) 2 Vector Space (Members are called vectors) 4 Field Definition A non empty set F together with operations (i)+ : F × F → F (addition) and (ii) · : F × F → F (multiplication) is said to be a field if the following axioms and properties are satisfied. Closure axiom: For every a, b ∈ F =⇒ a+b ∈F and a · b ∈ F Associative axiom: For all a, b, c ∈ F =⇒ a + (b + c) = (a + b) + c and a · (b · c) = (a · b) · c 5 Field Contd. Identity axiom: There exist elements 0, 1 ∈ F such that a + 0 = 0 + a = a, ∀a ∈ F a · 1 = 1 · a = a, ∀a ∈ F Inverse axiom:(i) For every a ∈ F , there exists b ∈ F such that a+b =b+a=0 (b is called additive inverse of a) and (ii) for every a ∈ F − {0}, there exists c ∈ F − {0} such that a·c =c ·a=1 (c is called multiplicative inverse of a) 6 Field Contd. Commutative Property: a + b = b + a ∀a, b ∈ F and a · b = b · a ∀a, b ∈ F Distributive Property: For every a, b, c ∈ F a · (b + c) = a · b + a · c and (a + b) · c = a · c + b · c Notation: A field F with respect to operations +, · is usually denoted as (F , +, ·) 7 Field Examples N = {1, 2, 3,... , } - set of all natural numbers Is (N, +, ·) a field? Closure axiom: We know that for all a, b ∈ N, a + b and a · b are also elements of N Associative axiom: Associative property is true for N for both + and · Identity axiom: 0∈ / N and hence identity axiom is not satisfied Thus (N, +, ·) is not a field. 8 Field Examples Z = {... , −2, −1, 0, 1, 2,...} - set of all integers Is (Z, +, ·) a field? Closure axiom: For all a, b ∈ Z, a + b and a · b are also elements of Z Associative axiom: Associative property is true for Z for both + and · Identity axiom: There exists 0, 1 ∈ Z such that a + 0 = 0 + a = a and a · 1 = 1 · a = a, ∀a ∈ Z Inverse axiom: For every a ∈ Z, there exists −a ∈ Z such that a + (−a) = −a + a = 0. But for 2 ∈ Z there doesnot exist a multiplicative inverse in Z Thus (Z, +, ·) is not a field 9 Field Examples Z2 = {0, 1} - congruence class modulo 2. Is (Z2 , +, ·) a field? Closure axiom: 0 + 0 = 0, 1 + 0 = 1, 0 + 1 = 1, 1 + 1 = 0 0 · 0 = 0, 1 · 0 = 0, 0 · 1 = 0, 1 · 1 = 1 Thus, the closure axiom is true. Associative axiom: From closure axiom we can see that associative axiom also holds true. Identity axiom: 0 ∈ Z2 is the additive identity and 1 ∈ Z2 is the multiplicative identity. 10 Inverse axiom: Additive inverse of 0 is 0 and 1 is 1. Multiplicative inverse of 1 is 1. Commutative property: From closure axiom, we can see that addition and multiplication are commutative in Z2 Distributive property: For every a, b ∈ Z2 (a + b) · 0 = 0 = a · 0 + b · 0 (a + b) · 1 = a + b = a · 1 + b · 1 Thus distributive law holds. Therefore, (Z2 , +, ·) is a field. 11 Field Examples R - Set of real numbers. Is (R, +, ·) a field? Closure axiom: Addition of two real numbers is a real number. Similarly, Multiplication of two real numbers is a real number. Thus, the closure axiom is true. Associative axiom: Addition and Multiplication are always associative in R. Identity axiom: 0 ∈ R is the additive identity and 1 ∈ R is the multiplicative identity. 12 Inverse axiom: Additive inverse of an element a ∈ R is −a. Multiplicative inverse of an element a ∈ R − {0} is 1a. Commutative property: It is true that for every a, b ∈ R a + b = b + a and a · b = b · a Distributive property: Distributive property is true for real numbers with respect to + and · Therefore, (R, +, ·) is a field. 13 Questions Q- Set of all rational numbers C- Set of all complex numbers 1 Is (Q, +, ·) a field? 2 Is (C, +, ·) a field? 14 Linear Equations Equation of a line : y = mx + c ax + by = c 15 Example of a line 16 Equation of a plane : z = ax + by + c Ax + By + Cz = D 17 Example of a plane 18 Systems of linear equations A11 x1 + A12 x2 +... + A1n xn = b1 A21 x1 + A22 x2 +... + A2n xn = b2 : : : Am1 x1 + Am2 x2 +... + Amn xn = bm m equations n varaibles (x1 , x2 ,... , xn ) Aij , bi ∈ F (F is a field) 19 Matrix form      A11 A12... A1n x1 b1  A21 A22... A2n  x2   b2  =         ............ ...  ...  Am1 Am2... Amn xn bm AX = B A = [Aij ]m×n , 1 ≤ i ≤ m, 1 ≤ j ≤ n X = [xj ]n×1 , B = [bi ]m×1 The solution set of the linear system AX = B is S = {X ∈ R n : AX = B} 20 Problem 1 Solve the following system of linear equations 4x − y = 5 2x + y = 7 Matrix form " #" # " # 4 −1 x 5 = 2 1 y 7 Solve graphically (sketch it!) 21 Problem 1 (solution) 22 Problem 1 Solve the following system of linear equations 4x − y = 5 2x + y = 7 Matrix form " #" # " # 4 −1 x 5 = 2 1 y 7 Solve graphically (sketch it!) Solution S = {(2, 3)} 23 Our objective is to design an efficient machinery to solve AX = B 24 Solution of Problem 1 through elementary row operations 4x − y = 5 (Eq1) 2x + y = 7 (Eq2) Let us employ a high school technique Multiply (Eq2) by 2 4x − y = 5 (Eq1) 4x + 2y = 14 (Eq2) (Eq2)-(Eq1) =⇒ 4x − y = 5 (Eq1) 0x + 3y = 9 (Eq2) We have three equivalent systems say red, blue and green 25 contd. Let us express red system in augmented matrix form " # 4 −1 5 2 1 7 Multiply second row by 2 (R2 ←− 2 × R2 ) " # " # 4 −1 5 4 −1 5 ∼ 2 1 7 4 2 14 Substract first row from second row (R2 ←− R2 − R1 ) " # " # " # 4 −1 5 4 −1 5 4 −1 5 ∼ ∼ 2 1 7 4 2 14 0 3 9 26 Contd. " # " # " # 4 −1 5 4 −1 5 4 −1 5 ∼ ∼ 2 1 7 4 2 14 0 3 9 R2 ←− 13 R2 =⇒ " # 4 −1 5 ∼ 0 1 3 R1 ←− 14 R1 =⇒ " # 1 − 41 5 4 ∼ 0 1 3 27 Contd. R1 ←− 14 R1 =⇒ " # 1 − 41 5 4 ∼ 0 1 3 R1 ←− R1 + 14 R2 =⇒ " # 1 0 2 ∼ 0 1 3 Let us write it in the system of equations form x + 0y = 2 0x + y = 3 28 Salient points Multiplying an equation by a non-zero scalar preserves the solution space (Ri ←− cRi , c ̸= 0) Replacing i th equation by sum of i th equation and constant multiple of j th equation preserves the solution space. (Ri ←− Ri + cRj ) Interchanging two equations preserves the solution space. (Ri ←→ Rj ) 29 Problem 2 Solve the following system of linear equations. 3x − 2y = −6, x + 2y = −10 Solve graphically ! Augmented matrix is " # 3 −2 −6 1 2 −10 Interchange first and second rows (R1 ←→ R2 ) " # 1 2 −10 ∼ 3 −2 −6 30 Problem 2 contd. R2 ←− R2 − 3R1 =⇒ " # 1 2 −10 ∼ 0 −8 24 R2 ←− − 18 R2 " # 1 2 −10 ∼ 0 1 −3 31 Problem 2 contd. R1 ←− R1 − 2R2 =⇒ " # 1 0 −4 ∼ 0 1 −3 x = −4, y = −3 Solution S = {(−4, −3)} 32 Problem 3 Solve the system of linear equations x + y = 2, 2x + 2y = 5 Solve graphically! Augmented matrix is " # 1 1 2 (R2 ←− R2 − 2R1 ) 2 2 5 " # 1 1 2 ∼ 0 0 1 Second row is 0x + 0y = 1. No solution 33 Problem 4 Solve the system x + 2y = 5, 2x + 4y = 10 Solve graphically! Augmented matrix is " # 1 2 5 (R2 ←− R2 − 2R1 ) 2 4 10 " # 1 2 5 ∼ =⇒ x + 2y = 5 0 0 0 Let y = c =⇒ x = 5 − 2c. The solution S = {(5 − 2c, c) : c ∈ R} 34 two dimensional problem and possible solutions 35 3-dimensional problem with a unique solution 36 3-dimensional problem with no solutions 37 3-dimensional problem with infinite number of solutions 38 Linear combination of equations A11 x1 + A12 x2 + A13 x3 = b1 (1) A21 x1 + A22 x2 + A23 x3 = b2 (2) Consider c1 (1) + c2 (2)( a linear combination) =⇒ c1 (A11 x1 + A12 x2 + A13 x3 ) + c2 (A21 x1 + A22 x2 + A23 x3 ) = c1 b1 + c2 b2 (3) 39 Suppose that x1 = a, x2 = b, x3 = c is solution of (1) and (2) Show that above solution is also a solution of (3). Consider L.H.S. of (3), c1 (A11 a + A12 b + A13 c) + c2 (A21 a + A22 b + A23 c) = c1 b1 + c2 b2 So x1 = a, x2 = b, x3 = c is solution of (3) Converse need not be true (Try !) Note: If X ∗ is a solution of k linear equations, then X ∗ is also a solution of a linear combination of those k equations. 40 Equivalent systems We say two sytems are equivalent if each equation in each system is a linear combination of equations in the other system. Why do we focus on equivalent systems? 41 Theorem 1: Equivalent systems of linear equations have exactly same solutions. Proof: Let (A) and (B) be two equivalent systems with solution sets SA and SB respectively. Prove that SA = SB. Let X ∈ SA. =⇒ X satisfies every equation in (A), and every equation in (B) is a linear combination of equations in (A). =⇒ X satisfies every equation in (B). =⇒ X ∈ SB Hence SA ⊆ SB Similarly, SB ⊆ SA =⇒ SA = SB 42 Problem Show that the following systems of linear equations are equivalent. x −y =0 } − − − − − (I ) 2x + y = 0 3x + y = 0 } − − − − − (II ) x +y =0 43 Solution 3x + y = 13 (x − y ) + 34 (2x + y ) x + y = − 13 (x − y ) + 23 (2x + y ) x − y = (3x + y ) − 2(x + y ) 2x + y = 12 (3x + y ) + 21 (x + y ) Note : AX = 0 is called a homogeneous system. 44 Elementary row operations Consider a matrix A = [Aij ], where Aij ∈ F , a field. The i th row of A is Ri = [Ai1 , Ai2 ,... , Ain ] Type 1: Multiplication of one row of A by a non-zero scalar c ∈F (e : Ri ←− cRi ) Type 2: Replacement of i th row by row i plus c times of row j where c ∈ F (e : Ri ←− Ri + cRj ) Type 3: Interchange of two rows (e : Ri ←→ Rj ) 45 Inverse of the Type 1 elementary row operation " # A11 A12 A13 A= A21 A22 A23 Let e : R1 ←− cR1 , c ̸= 0 " # cA11 cA12 cA13 e(A) = A21 A22 A23 We define e1 : R1 ←− c1 R1 " # A11 A12 A13 e1 (e(A)) = =A A21 A22 A23 Prove that e(e1 (A)) = A =⇒ e1 (e(A)) = A = e(e1 (A)) 46 Inverse of the Type 1 elementary row operation " # A11 A12 A13 A= A21 A22 A23 Let e : R1 ←− cR1 , c ̸= 0 " # cA11 cA12 cA13 e(A) = A21 A22 A23 We define e1 : R1 ←− c1 R1 =⇒ e1 is the inverse elementary operation of e " # A11 A12 A13 e1 (e(A)) = =A A21 A22 A23 Prove that e(e1 (A)) = A =⇒ e1 (e(A)) = A = e(e1 (A)) 47 Inverse of the Type 2 elementary row operation " # A11 A12 A13 A= A21 A22 A23 Let e : R2 ←− R2 + cR1 , c ∈F " # A11 A12 A13 e(A) = A21 + cA11 A22 + cA12 A23 + cA13 We define e1 : R2 ←− R2 − cR1. =⇒ e1 (e(A)) = A Similarly, e(e1 (A)) = A = e1 (e(A)) Note: e1 is the inverse of e 48 Inverse of the Type 3 elementary row operation " # A11 A12 A13 A= A21 A22 A23 Let e : R1 ←→ R2. " # A21 A22 A23 e(A) = A11 A12 A13 We define e1 : R1 ←→ R2. " # A11 A12 A13 e1 (e(A)) = =A A21 A22 A23 Similarly, e(e1 (A)) = A = e1 (e(A)) Note: e1 is the inverse of e 49 Theorem 2 To each elementary row operation e there corresponds an elementary operation e1 , of the same type as e, such that e(e1 (A)) = A = e1 (e(A)). In other words, inverse operation of an elementary operation exists and is of an elementary operation of the same type. Proof : Type 1 Inverse of the Type 1 e : Ri ←− cRi , c ̸= 0 e1 : Ri ←− c1 Ri 50 Proof of Theorem 2 contd. Type 2 Inverse of the Type 2 e : Ri ←− Ri + cRj e1 : Ri ←− Ri − cRj Type 3 Inverse of the Type 3 e : Ri ←→ Rj e1 : Ri ←→ Rj Note that for an m × n matrix A, e(e1 (A)) = A = e1 (e(A)) 51 Note e1 : R2 ←− 2R2 and e2 : R2 ←− R2 − R1 " # " # " # 4 −1 5 −→ 4 −1 5 −→ 4 −1 5 A= =B 2 1 7 (e1 ) 4 2 14 (e2 ) 0 3 9 e2 (e1 (A)) = B e1−1 : R2 ←− 21 R2 and e2−1 : R2 ←− R2 + R1 " # " # " # 4 −1 5 ←− 4 −1 5 ←− 4 −1 5 A= =B 2 1 7 (e1−1 ) 4 2 14 (e2−1 ) 0 3 9 e1−1 (e2−1 (B)) = A A and B are called row-equivalent matrices. 52 Row-equivalent matrices Definition : If A and B are m × n matrices over the field F , we say B is row-equivalent to A if B can be obtained from A by a finite sequence of elementary row operations. 53 Theorem 3 If A and B are row-equivalent m × n matrices, the homogeneous systems of linear equations AX = 0 and BX = 0 have exactly same solutions. Proof: Suppose that we pass A to B by a finite sequence of elementary row operations : A = A0 −→ A1 −→ A2 −→... −→ Ak = B Note: If (1) A0 X = 0 and A1 X = 0 have same solutions, (2) A1 X = 0 and A2 X = 0 have same solutions, (j)... ,... , (k) Ak−1 X = 0 and Ak X = 0 have same solutions, then AX = 0 and BX = 0 have same solutions. 54 Proof of Theorem 3 contd. It is enough to prove that Aj X = 0 and Aj+1 X = 0 have exactly the same solutions(that is one elementary row operation doesn’t disturb the set of solutions). Suppose that B is obtained from A by a single elementary row operation, say e (i.e., e(A) = B). No matter which of the types the operation is : (1) , (2) or (3), each equation in the system BX = 0 is a linear combination of the equations in AX = 0. Since e −1 is an elementary row operation (i.e., e −1 (B) = A), each equation in the system AX = 0 will also be a linear combination of equations in BX = 0. Hence these two systems are equivalent, and by Theorem 1, they have the same solutions. 55 Problem 1 Show that the following systems are row-equivalent. AX = 0 BX = 0 2x1 − x2 + 3x3 + 2x4 = 0 x3 − 11 3 x4 = 0 17 x1 + 4x2 − x4 = 0 x1 + 3 x4 = 0 2x1 + 6x2 − x3 + 5x4 = 0 x2 − 35 x4 = 0 Solution at page number 8(Hoffman and Kunz) It’s an assignment. Note that solving the second system is easy ! 56 Note Let us consider the matrix B from the previous problem.   0 0 1 − 11 3 B =  1 0 0 17   3  5 0 1 0 −3 Note that the first non-zero entry of each non-zero row of B is 1. Note that each column of B which contains the leading non-zero entry of some row has all its other entries 0.   0 0 1 − 11 3 B =  1 0 0 17   3  0 1 0 − 53 57 Row-reduced matrix An m × n matrix R is called row-reduced if : (a) the first non-zero entry of each non-zero row of R is 1; (b) each column of R which contains the leading non-zero entry of some row has all its other entries 0. Examples : (i) Identity matrix and (ii)the matrix B (previous problem) Examples of non row-reduced matrices     1 0 0 0 0 2 1  0 1 −1 0  ,  1 0 −3      0 0 1 0 0 0 0 58 Problem 1 Find all solutions of the following system of equations by row-reducing the coefficient matrix. 1 3 x1 + 2x2 − 6x3 = 0 −4x1 + 5x3 = 0 −3x1 + 6x2 − 13x3 = 0 − 37 x1 + 2x2 − 38 x3 = 0 Solution: The coefficient matrix of the system is 1   3 2 −6  −4 0 5     −3 6 −13    − 37 2 − 83 59 Problem 1 contd. R1 ←− 3R1 , R4 ←− 3R4   1 6 −18  −4 0 5  ∼   −3 6 −13    −7 6 −8 R2 ←− R2 + 4R1 , R3 ←− R3 + 3R1 , R4 ←− R4 + 7R1   1 6 −18  0 24 −67  ∼   0 24 −67    0 48 −134 60 Problem 1 contd. 1 R2 ←− 24 R2   1 6 −18  0 1 − 67 24  ∼   0 24 −67    0 48 −134 R1 ←− R1 − 6R2 , R3 ←− R3 − 24R2 , R4 ←− R4 − 48R2 0 − 45   1  0 1 − 67 24  ∼  (a row − reduced matrix)    0 0 0  0 0 0 Thus x1 − 54 x3 = 0 67 x2 − 24 x3 = 0 61 Problem 1 contd. Let x3 = a. =⇒ x1 = 45 a, x2 = 24 67 a 5 67 Solution set, S = {( 4 a, 24 a, a) : a ∈ R} Note that (i) x3 is a called free variable and (ii) x1 , x2 are called pivot variables. 62 Theorem 4 Every m × n matrix over the field F is row-equivalent to a row-reduced matrix. Proof : (Assignment) 63 Problem 2 Find all solutions of the systems of linear equations AX = 2X and AX = 3X where   6 −4 0 A =  4 −2 0 .   −1 0 3 Solution : (i) The system AX = 2X is      6 −4 0 x x  4 −2 0   y  = 2  y       −1 0 3 z z  6x − 4y = 2x   =⇒ 4x − 2y = 2y  −x + 3z = 2z  64 Problem 2 contd.  4x − 4y = 0   =⇒ 4x − 4y = 0  −x + z = 0  The coefficient matrix is   4 −4 0  4 −4 0    −1 0 1 Let us find a row-reduced matrix which is row-equivalent to the above matrix. R3 ←− (−1)R3 , R3 ←→ R1   1 0 −1 ∼  4 −4 0    65 4 −4 0 Problem 2 contd. R2 ←− R2 − 4R1 and R3 ←− R3 − 4R1   1 0 −1 ∼  0 −4 4    0 −4 4 R2 ←− − 14 R2   1 0 −1 ∼  0 1 −1    0 −4 4 R3 ←− R3 + 4R2   1 0 −1 ∼  0 1 −1    0 0 0 66 Problem 2 contd. The equivalent system is ) x −z =0 y −z =0 Let z = a (Note that z is a free variable). Thus x = a = y (ii) Find all solutions of AX = 3X The solution set is S = X ∈ R3 : AX = 3X = {(0, 0, a) : a ∈ R}.  67 Note   0 1 −3 0 0 1  0 0 0 1 0 2  A=     0 0 0 0 1 3  0 0 0 0 0 0 1 A is a row-reduced matrix. 2 All non-zero rows are above zero rows. 3 The ki denotes the column which contains leading one (called pivot elements) (if exists) of Ri (row i). k1 = 2, k2 = 4, and k3 = 5. Note that k1 < k2 < k3. 68 Row-reduced echelon matrix   0 1 −3 0 0 1  0 0 0 1 0 2  A=     0 0 0 0 1 3  0 0 0 0 0 0 blue zeros forms a staircase (echelon) from right to left. 69 Row-reduced echelon matrix An m × n matrix R is called a row-reduced echelon matrix if: (a) R is row-reduced ; (b) every row of R which has all its entries 0 occurs below every row which has a non-zero entry; (c) if rows 1, 2,... , r are the non-zero rows of R, and if the leading non-zero entry of row i occurs in column ki , i = 1, 2,... , r , then k1 < k2 <... < kr. 70 B is a row-reduced matrix, but not a row-reduced echelon matrix 1 − 11   0 0 3  1 0 0 17 3  B=   0 − 53   0 1  0 0 0 0 Why? k1 = 3, k2 = 1, k3 = 2 which violates the condition (c) Could you find a a row-reduced echelon matrix C which is row-equivalent to B? (R1 ←→ R2 , R2 ←→ R3 ) 0 17   1 0 3  0 1 0 − 35  C =  (Is it unique?)    0 0 1 − 11 3  0 0 0 0 71 Theorem 5 Every m × n matrix A is row-equivalent to a row-reduced echelon matrix. Proof. Assignment. 72 Problem 3 Solve the system of linear equations AX = b where     1 −2 1 2 1 A =  1 1 −1 1  and b =  2 .     1 7 −5 −1 3 73 Note 1: Consider a row-reduced echelon matrix R and the system RX = 0 , where   0 1 −3 0 21 ) x2 − 3x3 + 21 x5 = 0 R= 0 0 0 1 2    x4 + 2x5 = 0 0 0 0 0 0 No. of non-zero rows of R, r = 2, No. of variables, n = 5 k1 = 2, k2 = 4 =⇒ Pivot variables = {xk1 , xk2 } = {x2 , x4 }. No. of free variables = n − r = 5 − 2 = 3, Free variables = {u1 , u2 , u3 } = {x1 , x3 , x5 }. 74 Note 1 contd. x2 − 3x3 + 21 x5 = 0 x4 + 2x5 = 0 Set the free variables as : u1 = x1 = a, u2 = x3 = b, u3 = x5 = c =⇒ x2 = 3b − 12 c, x4 = −2c Solution set S = (a, 3b − 21 c, b, −2c, c) : a, b, c ∈ R  75 Observations from Note 1  n−r X  xk1 + C1j uj = 0   )  x2 − 3x3 + 12 x5 = 0   j=1 =⇒ n−r general expression) x4 + 2x5 = 0 X  xk2 + C2j uj = 0      j=1 76 Note 2 Consider an m × n row-reduced echelon matrix R with r non-zero rows. Let rows 1, 2,... , r be the non-zero rows of R, and suppose that the leading non-zero entry of row i occurs in column ki. The system RX = 0 has r (non-trivial) equations. Let xki s are the pivot variables. Let u1 , u2 ,... , un−r denote the (n − r ) unknowns which are different from xk1 , xk2 ,... , xkr. Then r non-trivial equations of RX = 0 are of the form 77 Note 2 contd. n−r X xk1 + C1j uj = 0 j=1 n−r X xk2 + C2j uj = 0 j=1.................. n−r X xkr + Crj uj = 0 j=1 All the solutions of the system of equations RX = 0 are obtained by assigning any value whatsoever to u1 , u2 ,... , un−r , and then computing the corresponding values of xk1 , xk2 ,... , xkr. 78 Remarks (Note 2 contd.) Thus, we have (i) If n > r , then the system RX = 0 has at least one free variable and thus it has a non-trivial solution. (ii) If n = r , then the system RX = 0 has no free variable and thus it has only trivial solution. 79 Theorem 6 If A is an m × n matrix and m < n, then the homogeneous system of linear equations AX = 0 has a non-trivial solution. Proof: Let R be a row-reduced echelon matrix which is row-equivalent to A. Then the systems AX = 0 and RX = 0 have same solutions by Theorem 3. If r is the number of non-zero rows of R, then r ≤ m. Since m < n, we have r < n. Thus the system RX = 0 has n − r (≥ 1) free variables and it admits a non-trivial solution. Hence AX = 0 has a non-trivial solution. 80 Note If R is an n × n (square) row-reduced echelon matrix with n non-zero rows, then R = I ( the identity matrix). Because : (i) Every row has a leading one and (ii) k1 = 1 < k2 = 2 <... < kn = n. 81 Theorem 7 If A is an n × n (square) matrix, then A is row equivalent to the n × n identity matrix if and only if the system of equations AX = 0 has only the trivial solution. Proof. Case 1. Suppose that A is row-equivalent to the n × n identity matrix I. By Theorem 3, AX = 0 and IX = 0 have the same solution set. Thus the solution set of AX = 0 is S = {X : AX = 0} = {X : IX = 0} = {X : X = 0} = {0} Hence the system AX = 0 has only the trivial solution. 82 Proof of Theorem 7 contd. Case 2. Suppose that the system AX = 0 has only the trivial solution. Prove that A is row-equivalent to the n × n identity matrix. Let R be an n × n row-reduced echelon matrix which is row-equivalent to A. By Theorem 3, the systems AX = 0 and RX = 0 have exactly the same solutions. Since AX = 0 has only the trivial solution, RX = 0 has only the trivial solution. Hence the system RX = 0 has no free variables. Thus the number of free variables (of the system RX = 0), n − r = 0 where r is the number of non-zero rows of R. So R is an n × n row-reduced echelon matrix with n(= r ) non-zero rows and thus k1 = 1 < k2 = 2 <... < kn = n. This proves that R = I , an identity matrix. Hence A is row-equivalent to R = I. 83 Theorem 8 Let AX = b be a given system of equations, where A is an m × n matrix, X is an n × 1 vector and b is an m × 1 vector. Let RX = f be the row-reduced-echelon form of the system AX = b. Let there are r non-zero rows in the augmented matrix [R|f ]. Then the following are true. 1 No solution. If r < m (meaning that R actually has at least one row of all 0s) and at least one of the numbers fr +1 , fr +2 ,... , fm is not zero, then the system AX = b is inconsistent, i.e, no solution is possible. 2 Unique solution. If the system AX = b is consistent and r = n, then the system AX = b has a unique solution. 3 Infinitely many solutions. If the system AX = b is consistent and r < n, then the system AX = b has infinitely many solutions. 84 Reading assignment Section 1.5 Matrix multiplication 85 Assignment Solve all exercise problems in section 1.4 (pages 15-16) 86 Elementary matrices An m × m matrix is said to be an elementary matrix if it can be obtained from the m × m identity matrix by means of a single elementary row operation. Example : " # 1 0 I = (e : R1 ←− cR1 , c ̸= 0) 0 1 " # c 0 E = e(I ) = ( E is an elementary matrix) 0 1 87 Find all 2 × 2 elementary matrices " # " # c 0 1 0 , (Using Type 1, c ̸= 0) 0 1 0 c " # " # 1 c 1 0 , (Using Type 2) 0 1 c 1 " # 0 1 (Using Type 3) 1 0 Find all 3 × 3 elementary matrices. (Assignment) 88 Properties of elementary matrices Type 1   1 0 0   1 I = 0 1 0  e : R1 ←− cR1 , c = ̸ 0, e1 : R1 ←− R1   c 0 0 1     1 c 0 0 c 0 0 E = e(I ) =  0 1 0 , E1 = e1 (I ) =  0 1 0      0 0 1 0 0 1      1 c 0 0 c 0 0 1 0 0 EE1 =  0 1 0   0 1 0 = 0 1 0 =I      0 0 1 0 0 1 0 0 1 Similarly (verify), E1 E = I = EE1 89 Properties of elementary matrices   A11 A12 Let A =  A21 A22  , (e : R1 ←− cR1 , c ̸= 0)   A31 A32   cA11 cA12 e(A) =  A21 A22    A31 A32      c 0 0 A11 A12 cA11 cA12 e(I )A =  0 1 0   A21 A22  =  A21 A22  = e(A)      0 0 1 A31 A32 A31 A32 e(I )A = e(A) 90 Properties of elementary matrices Type 2   1 0 0 I = 0 1 0  (e : R1 ←− R1 + cR2 , e1 : R1 ←− R1 − cR2 )   0 0 1     1 c 0 1 −c 0 E = e(I ) =  0 1 0  , E1 = e1 (I ) =  0 1 0      0 0 1 0 0 1      1 c 0 1 −c 0 1 0 0 EE1 =  0 1 0   0 1 0 = 0 1 0 =I      0 0 1 0 0 1 0 0 1 Similarly (verify), E1 E = I = EE1 91 Properties of elementary matrices   A11 A12 Let A =  A21 A22  , (e : R1 ←− R1 + cR2 )   A31 A32   A11 + cA21 A12 + cA22 e(A) =  A21 A22    A31 A32      1 c 0 A11 A12 A11 + cA21 A12 + cA22 e(I )A =  0 1 0   A21 A22  =  A21 A22       0 0 1 A31 A32 A31 A32 e(I )A = e(A) 92 Properties of elementary matrices Type 3   1 0 0 I = 0 1 0  (e : R1 ←→ R2 , e1 : R1 ←→ R2 )   0 0 1     0 1 0 0 1 0 E = e(I ) =  1 0 0 , E1 = e1 (I ) =  1 0 0      0 0 1 0 0 1      0 1 0 0 1 0 1 0 0 EE1 =  1 0 0   1 0 0 = 0 1 0 =I      0 0 1 0 0 1 0 0 1 Similarly (verify), E1 E = I = EE1 93 Properties of elementary matrices   A11 A12 Let A =  A21 A22  , (e : R1 ←→ R2 )   A31 A32   A21 A22 e(A) =  A11 A12    A31 A32      0 1 0 A11 A12 A21 A22 e(I )A =  1 0 0   A21 A22  =  A11 A12       0 0 1 A31 A32 A31 A32 e(I )A = e(A) 94 Theorem 9 Let e be an elementary row operation and I be the m × m identity matrix. Then for every m × n matrix A, e(I )A = e(A) Proof: Assignment Note: For every elementary row operation e, there exists an inverse elementary operation of the same type e1 such that e(I )e1 (I ) = I = e1 (I )e(I ) (EE1 = I = E1 E ) 95 Corollary (to Theorem 9) Let A and B be m × n matrices over the field F. Then B is row-equivalent to A if and only if B = PA where P is a product of m × m elementary matrices. Proof: Case 1: Suppose that B is row-equivalent to A. Then B can be obtained from A by a finite sequence of elementary row operations, say A = A0 −→ A1 −→ A2 −→... −→ Ak−1 −→ Ak = B where ei (Ai−1 ) = Ai , ei is an elementary row operation for 1 ≤ i ≤ k. Note that ei (Ai−1 ) = ei (I )Ai−1 , by Theorem 9 and ei (I ) is an m × m elementary matrix. 96 Corollary contd. Clearly, A1 = e1 (A) = e1 (I )A , A2 = e2 (A1 ) = e2 (I )A1 =⇒ A2 = e2 (I )e1 (I )A Using similar arguments, B = Ak = ek (I )ek−1 (I )... e2 (I )e1 (I )A = PA where P = ek (I )ek−1 (I )... e2 (I )e1 (I ) is a product of m × m elementary matrices. Case 2 : Suppose that B = PA, where P is a product of m × m elementary matrices. Let P = Ek Ek−1... E2 E1 where Ei is an m × m elementary matrix for 1 ≤ i ≤ k. Since Ei is an elementary matrix, there exists an elementary row operation ei such that Ei = ei (I ). B = PA = ek (I )ek−1 (I )... e2 (I )e1 (I )A 97 Corollary contd. B = PA = ek (I )ek−1 (I )... e2 (I )e1 (I )A B = PA = ek (I )ek−1 (I )... e2 (I )e1 (A) B = PA = ek (I )ek−1 (I )... e2 (e1 (A))............... B = PA = ek (ek−1 (... e2 (e1 (A)))) Hence B can be obtained from A by a finite sequence of elementary row operations e1 , e2 ,... , ek. Then B is row-equivalent to A. 98 Problem     1 2 3 4 Show that A =  3 4  and B =  1 2  are     5 6 8 10 row-equivalent. Find a 3 × 3 matrix P such that B = PA. Solution : Let e1 : R1 ←→ R2 and e2 : R3 ←− R3 + R1 Clearly, B = e2 (e1 (A)) = e2 (e1 (I )A) = e2 (I )e1 (I )A = PA      1 0 0 0 1 0 0 1 0 P = e2 (I )e1 (I ) =  0 1 0   1 0 0  =  1 0 0       1 0 1 0 0 1 0 1 1 99 Definition Let A be an n × n matrix over the field F. An n × n matrix B such that BA = I is called a left inverse of A; an n × n matrix B such that AB = I is called a right inverse of A. If AB = I = BA, then B is called a two-sided inverse of A or simply the inverse of A and A is said to be invertible. Note: If A is an invertible matrix, then A has no zero row. 100 Lemma If A has a left inverse B and a right inverse C , then B = C. Proof Suppose that BA = I and AC = I. B = BI = B(AC ) = (BA)C = IC = C 101 Note: If A has a left inverse and a right inverse, then A is invertible and the inverse of A is denoted by A−1. Theorem 10 (i). If A is invertible, so is A−1 and (A−1 )−1 = A. (ii). If both A and B are invertible, so is AB, and (AB)−1 = B −1 A−1. Proof (AB)(B −1 A−1 ) = I = (B −1 A−1 )(AB). Note: Product of invertible matrices is invertible. 102 Theorem 11: An elementary matrix is invertible. Proof : Let E be an m × m elementary matrix corresponding to the elementary row operation e. Thus E = e(I ). By Theorem 2, there exists an elementary row operation e1 , same type as e, such that e(e1 (A)) = A = e1 (e(A)) for every matrix A. Let E1 = e1 (I ) where I is the m × m identity matrix. Then EE1 = e(I )E1 = e(E1 ) = e(e1 (I )) = I and E1 E = e1 (I )E = e1 (E ) = e1 (e(I )) = I. EE1 = I = E1 E. Hence E is an invertible matrix. 103 Thus an elementary matrix is invertible. Find inverses of all 2 × 2 elementary matrices " #−1 " # " #−1 " # 1 c 0 c 0 1 0 1 0 = , = 0 1 0 1 0 c 0 c1 " #−1 " # " #−1 " # 1 c 1 −c 1 0 1 0 = , = 0 1 0 1 c 1 −c 1 " #−1 " # 0 1 0 1 = 1 0 1 0 Find inverses of all 3 × 3 elementary matrices. (Assignment) 104 Theorem 12 If A is an n × n matrix, the following are equivalent. (i) A is invertible. (ii) A is row-equivalent to the n × n identity matrix. (iii) A is a product of elementary matrices. Proof: Let R be a row-reduced echelon n × n matrix which is row-equivalent to A. By Corollary to Theorem 9, R = Ek Ek−1... E2 E1 A − − − − − (a) where Ei is an elementary matrix. Note that the inverse of Ei is also an elementary matrix. Since Ei′ s are invertible, A = E1−1 E2−1... Ek−1 R − − − − (b) 105 Theorem 12 contd. (i) =⇒ (ii) Suppose that A is invertible. Using (a), R is a product of invertible matrices and by corolllary to Theorem 10, R is invertible. Note that an invertible matrix has no zero-row. So R is an n × n row-reduced echelon matrix with no zero row and k1 = 1 < k2 = 2 <... < kn = n. Hence R is the n × n identity matrix. A is row-equivalent to R = I. (ii) =⇒ (iii) Suppose that A is row-equivalent to R = I. By (b) A = E1−1 E2−1... Ek−1 R = E1−1 E2−1... Ek−1 I A = E1−1 E2−1... Ek−1 , a product of elementary matrices. 106 Theorem 12 contd. (iii) =⇒ (i) Suppose that A is a product of elementary matrices. By Theorem 11, an elementary matrix is invertible. By Corollary to Theorem 10, a product of invertible matrices is invertible. Hence A is invertible. 107 Corollaries (to Theorem 12) Let A be an n × n matrix. Consider the augmented matrix [A|I ]. Suppose that [A|I ] ∼ [I |B]. Note that A is row equivalent to I (thus A is invertible) and I is row equivalent to B. By Corollary to Theorem 9, there exists an n × n matrix P such that I = PA and B = PI =⇒ B = P and I = BA =⇒ A is invertible and B = A−1. Corollary 12.1. If A is an n × n matrix and if a sequence of elementary row operations reduces A to the indentity matrix, then that same sequence of operations when applied to I yields A−1. 108 Problem Find the inverse of   1 1 1 2 3 A=  1 1 1  2 3 4  1 1 1 3 4 5 Solution : Consider   1 1 1 2 3 1 0 0 [A|I ] =  1 1 1 0 1 0    2 3 4 1 1 1 3 4 5 0 0 1 1 1 R2 ←− R2 − R1 , R3 ←− R3 − R1 2 3 109 Solution contd.   1 1 1 2 3 1 0 0 1 1 ∼ 0 − 21 1 0    12 12 1 4 0 12 45 − 31 0 1 R2 ←− 12R2   1 1 1 2 3 1 0 0 ∼ 0 1 1 −6 12 0    1 4 0 12 45 − 13 0 1 1 1 R1 ←− R1 − R2 , R3 ←− R3 − R2 2 12 110 Solution contd.   1 0 − 16 4 −6 0 ∼ 0 1 1 −6 12 0    1 1 0 0 180 6 −1 1 R3 ←− 180R3   1 0 − 61 4 −6 0 ∼ 0 1 1 −6 12 0    0 0 1 30 −180 180 1 R2 ←− R2 − R3 , R1 ←− R1 + R3 6 111 Solution contd.   1 0 0 9 −36 30 [A|I ] ∼  0 1 0 −36 192 −180  = [I |B]   0 0 1 30 −180 180 By Corollary 12.1,   9 −36 30 A−1 = B =  −36 192 −180    30 −180 180 112 Problem 2 Find the inverse of   2 5 −1 A =  4 −1 2    6 4 1 Solution :   2 5 −1 1 0 0 [A|I ] =  4 −1 2 0 1 0    6 4 1 0 0 1 Take R3 ←− R3 − R1   2 5 −1 1 0 0 [A|I ] =  4 −1 2 0 1 0    4 −1 2 −1 0 1 113 Solution contd. Now, take R3 ←− R3 − R2. Then   2 5 −1 1 0 0 [A|I ] ∼  4 −1 2 0 1 0    0 0 0 −1 −1 1 Thanks to the last zero row, A is not row-equivalent to I and A is not invertible. 114 Theorem 13 For an n × n matrix A the following are equivalent. (i) A is invertible. (ii) The homogeneous system AX = 0 has only the trivial solution X = 0. (iii) The system of equations AX = B has a solution X for each n × 1 matrix B. Proof: (i) =⇒ (ii) Suppose that A is invertible. By Theorem 12, A is row-equivalent to I. By Theorem 3, AX = 0 and IX = 0 have exactly same solutions. The solution set of AX = 0 is S = {X : AX = 0} = {X : IX = 0} = {X : X = 0} = {0}. Hence the system AX = 0 has only the trivial solution X = 0. 115 Theorem 13 contd. (ii) =⇒ (i) Suppose that AX = 0 has only the trivial solution X = 0. By Theorem 7, A is row-equivalent to I. By Theorem 12, A is invertible. (i) =⇒ (iii) Suppose that A is invertible. That is A−1 exists. Consider the system AX = B. This implies that X = A−1 B is a solution for the system AX = B for each B. 116 Theorem 13 contd. (iii) =⇒ (i) Suppose that the system of equations AX = B has a solution X for each n × 1 matrix B. Let R be a row-reduced echelon matrix which is row-equivalent to A. By an corollary of Theorem 9, R = PA, where P is a product of elementary matrices. Since elementary matrices are invertible, so is their product P. AX = B has a solution X for each B. ⇐⇒ P(AX ) = PB has a solution X for each B. ⇐⇒ RX = PB has a solution X for each B (Note that R = PA). ⇐⇒ RX = E has a solution X for each E (= PB). 117 Theoem 13 contd. Now, take   0   0   ..  E = .      0  1 RX = E has a solution X. =⇒ The last row of R is non-zero. =⇒ R is an n × n row-reduced echelon matrix with no zero rows. =⇒ R = I. Hence A is row-equivalent to R = I. By Theorem 12, A is invertible. 118 Corollary 13.1 A square matrix with either a left or right inverse is invertible. Proof: Let A be an n × n matrix. Case 1. Suppose A has a left inverse, say B. That is BA = I. Consider the system AX = 0. That implies B(AX ) = B0 = 0. =⇒ (BA)X = 0. =⇒ IX = 0. =⇒ X = 0. Thus AX = 0 =⇒ X = 0 By Theorem 13, A is invertible. Case 2 : Suppose that A has a right inverse say C. i.e., AC = I. So A is a left inverse of C. By Case 1, C is invertible and C −1 = A. Hence A is invertible and A−1 = C. 119 Corollary 13.2 Let A = A1 A2... Ak where A1 , A2 ,... , Ak are n × n (square) matrices. If A is invertible then each Ai is invertible. Proof : A = A1 A2... Ak − − − (a) Suppose that A is invertible. By Theorem 13, AX = 0 =⇒ X = 0. We want to show that each Ai is invertible. First, we prove that Ak is invertible. Consider the system Ak X = 0. =⇒ A1 A2... Ak−1 (Ak X ) = 0. =⇒ AX = 0. =⇒ X = 0. Thus Ak X = 0 =⇒ X = 0 By Theorem 13, Ak is invertible. Since A and Ak are invertible, AA−1k = A1 A2... Ak−1 is invertible. By preceeding argument, Ak−1 is invertible. Continuing in this way, we conclude that each Ai is invertible. 120 Problem 1 Question. Prove or disprove that if A is an m × n matrix, B is an n × m matrix and n < m, then AB is not invertible. Solution: Since B is an n × m matrix and n < m, by Theorem 6, the homogeneous system BX = 0 has a non-trivial solution, say X ∗ ̸= 0. i.e. BX ∗ = 0. Consider the system (AB)X = 0. (AB)X ∗ = A(BX ∗ ) = A0 = 0. =⇒ X ∗ is a non-trivial solution of the homogeneous system (AB)X = 0. By Theorem 13, AB is not invertible. 121 Problem 2 1   32 −6  −4 0 5  Let A=    −3 6 −13   − 37 2 − 38 Does there exist a 3 × 4 matrix B such that (i) AB = 0 and (ii) B ̸= 0 ? 122 Solution of Problem 2 Find a non-trivial solution of the sytem AX = 0. Solution set, S = {( 45 a, 24 67 a, a) : a ∈ R} (Visit previous lecture notes.) Choose a = 24 =⇒ (30, 67, 24) is a solution.   30 30 30 30 =⇒ B =  67 67 67 67    24 24 24 24 Verify that AB = 0, and B ̸= 0 123 Problem 3 Prove of disprove that A is invertible and find A−1 if it exists where   1 2 3 4  0 2 3 4  A= .    0 0 3 4  0 0 0 4 124 Solution to Problem 3   1 −1 0 0  0 21 − 21 0  A−1 =    1 − 13   0 0 3  1 0 0 0 4 125