MATH 22A: LINEAR ALGEBRA Chapter 2
MATH 22A: LINEAR ALGEBRA Chapter 2 Steffen Borgwardt, UC Davis original version of these slides: Jes´ us De Loera, UC Davis January 31, 2015 MATH 22A: LINEAR ALGEBRA Chapter 2 CHAPTER 2 (2.1-2.7) SOLUTIONS OF LINEAR EQUATIONS MATH 22A: LINEAR ALGEBRA Chapter 2 Suppose you wish to solve x + 2 y + 3 z = 6, 2 x − 3 y + 2 z = 14, 3 x + y − z = −2 MATH 22A: LINEAR ALGEBRA Chapter 2 Suppose you wish to solve x + 2 y + 3 z = 6, 2 x − 3 y + 2 z = 14, 3 x + y − z = −2 GOAL: Find a point (x, y , z) that when substituted satisfies ALL of these equations simultaneously. MATH 22A: LINEAR ALGEBRA Chapter 2 Suppose you wish to solve x + 2 y + 3 z = 6, 2 x − 3 y + 2 z = 14, 3 x + y − z = −2 GOAL: Find a point (x, y , z) that when substituted satisfies ALL of these equations simultaneously. Idea 1: Eliminate a variable, say x in all but one equation: Key principle: linear combinations of the original equations give new equations that have the same solutions! MATH 22A: LINEAR ALGEBRA Chapter 2 Suppose you wish to solve x + 2 y + 3 z = 6, 2 x − 3 y + 2 z = 14, 3 x + y − z = −2 GOAL: Find a point (x, y , z) that when substituted satisfies ALL of these equations simultaneously. Idea 1: Eliminate a variable, say x in all but one equation: Key principle: linear combinations of the original equations give new equations that have the same solutions! The new system is x + 2y + 3z = 6 (−2)(Equ 1) + (Equ 2) = −7y − 4z = 2 (−3)(Equ 1) + (Equ 3) = −5y − 10z = −20 MATH 22A: LINEAR ALGEBRA Chapter 2 Interchange equations (Eq 2 become 3) and simplify: x + 2y + 3z = 6 −5y − 10z = −20 −→ y + 2z = 4 −7y − 4z = 2 MATH 22A: LINEAR ALGEBRA Chapter 2 Interchange equations (Eq 2 become 3) and simplify: x + 2y + 3z = 6 −5y − 10z = −20 −→ y + 2z = 4 −7y − 4z = 2 Eliminate y (using linear combinations of second third eqs): x + 2y + 3z = 6 y + 2z = 4 (7) · (Equ 2 + (Eq 3) = 10z = 30 MATH 22A: LINEAR ALGEBRA Chapter 2 Interchange equations (Eq 2 become 3) and simplify: x + 2y + 3z = 6 −5y − 10z = −20 −→ y + 2z = 4 −7y − 4z = 2 Eliminate y (using linear combinations of second third eqs): x + 2y + 3z = 6 y + 2z = 4 (7) · (Equ 2 + (Eq 3) = 10z = 30 New system is simply x + 2y + 3z = 6 y + 2z = 4 z =3 MATH 22A: LINEAR ALGEBRA Chapter 2 The system has a TRIANGULAR SHAPE . It allows the easy solution of the system. From the solution z = 3 we derive y = −2, from these two we get x = 1. MATH 22A: LINEAR ALGEBRA Chapter 2 The system has a TRIANGULAR SHAPE . It allows the easy solution of the system. From the solution z = 3 we derive y = −2, from these two we get x = 1. General Strategy Eliminate one variable at a time, until we arrive to a triangular shape system Do this performing LINEAR COMBINATIONS of the rows Interchange two equations Multiply an equation by a non-zero constant Add a multiple of one equation to another. MATH 22A: LINEAR ALGEBRA Chapter 2 The system has a TRIANGULAR SHAPE . It allows the easy solution of the system. From the solution z = 3 we derive y = −2, from these two we get x = 1. General Strategy Eliminate one variable at a time, until we arrive to a triangular shape system Do this performing LINEAR COMBINATIONS of the rows Interchange two equations Multiply an equation by a non-zero constant Add a multiple of one equation to another. WARNING In some circumstances NO SOLUTION is possible: Example: x + 2y = 10, 2x − 2 = −4, 3x + 5y = 20 If we eliminate x from the 2nd, 3rd equations, the new system is x + 2y = 10, y = 4, y = 10, which is IMPOSSIBLE. MATH 22A: LINEAR ALGEBRA Chapter 2 Matrix Notation for Equations Using matrix multiplication we can go from a system of equations to a matrix-vector equation Example x + 2 y + 3 z = 6, 2 x − 3 y + 2 z = 14 3 x + y − z = −2 1 2 3 6 x 2 −3 2 y = 14 z −2 3 1 −1 MATH 22A: LINEAR ALGEBRA Chapter 2 Matrix Notation for Equations Using matrix multiplication we can go from a system of equations to a matrix-vector equation Example x + 2 y + 3 z = 6, 2 x − 3 y + 2 z = 14 3 x + y − z = −2 1 2 3 6 x 2 −3 2 y = 14 z −2 3 1 −1 In matrix notation Ax = b. New Interpretation Solving a system of equations is the same as finding a special linear combination of the column vectors that gives the desired vector of right-hand sides. MATH 22A: LINEAR ALGEBRA Chapter 2 Suppose we want to solve a system of equations (YOU DON’T KNOW a,b,c,d yet) x + 3y + 2z − w = a −x − 3y − 3z + 3w + v = b 2x + 6y + z + 4w + 3v = c 3x + 9y + 8z − 7w + 2v = d MATH 22A: LINEAR ALGEBRA Chapter 2 Suppose we want to solve a system of equations (YOU DON’T KNOW a,b,c,d yet) x + 3y + 2z − w = a −x − 3y − 3z + 3w + v = b 2x + 6y + z + 4w + 3v = c 3x + 9y + 8z − 7w + 2v = d Using matrix notation (shorter!): 1 3 2 −1 0 a −1 −3 −3 3 1 b 2 6 1 4 3 c 3 9 8 −7 2 d MATH 22A: LINEAR ALGEBRA Chapter 2 1 3 2 −1 0 a −1 −3 −3 3 1 b 2 6 1 4 3 c 3 9 8 −7 2 d Now ROWS = EQUATIONS. MATH 22A: LINEAR ALGEBRA Chapter 2 1 3 2 −1 0 a −1 −3 −3 3 1 b 2 6 1 4 3 c 3 9 8 −7 2 d Now ROWS = EQUATIONS. We apply LEGAL ROW OPERATIONS until we are in a ECHELON SHAPE: 1 Interchange two ROWS MATH 22A: LINEAR ALGEBRA Chapter 2 1 3 2 −1 0 a −1 −3 −3 3 1 b 2 6 1 4 3 c 3 9 8 −7 2 d Now ROWS = EQUATIONS. We apply LEGAL ROW OPERATIONS until we are in a ECHELON SHAPE: 1 2 Interchange two ROWS Multiply a ROW by a non-zero constant MATH 22A: LINEAR ALGEBRA Chapter 2 1 3 2 −1 0 a −1 −3 −3 3 1 b 2 6 1 4 3 c 3 9 8 −7 2 d Now ROWS = EQUATIONS. We apply LEGAL ROW OPERATIONS until we are in a ECHELON SHAPE: 1 2 3 Interchange two ROWS Multiply a ROW by a non-zero constant Add a multiple of one ROW to another ROW. MATH 22A: LINEAR ALGEBRA Chapter 2 1 3 2 −1 0 a −1 −3 −3 3 1 b 2 6 1 4 3 c 3 9 8 −7 2 d MATH 22A: LINEAR ALGEBRA Chapter 2 1 −1 2 3 1 3 0 0 2 6 3 9 3 −1 0 a 2 −3 −3 6 1 9 8 2 −1 1 8 3 4 1 b 3 c −7 2 d −1 0 a 1 a+b 4 3 c −7 2 d 2 MATH 22A: LINEAR ALGEBRA Chapter 2 1 −1 2 3 1 3 0 0 2 6 3 −3 −3 6 1 9 8 2 −1 1 3 9 1 3 −1 0 a 2 8 2 3 4 1 b 3 c −7 2 d −1 0 a 1 a+b 4 3 c −7 2 d 2 −1 0 a 0 0 −1 2 1 a+b 0 0 −3 6 3 −2 a + c 3 9 8 −7 2 d MATH 22A: LINEAR ALGEBRA Chapter 2 1 3 2 −1 0 a 0 0 −1 2 1 a+b 0 0 −3 6 3 −2 a + c 3 9 8 −7 2 d MATH 22A: LINEAR ALGEBRA Chapter 2 1 3 0 0 0 0 3 9 1 3 0 0 0 0 0 0 2 −1 0 −1 2 1 −3 6 3 8 −7 2 2 −1 0 −1 2 1 −3 6 3 2 a −2 a + c d a a+b −2 a + c a+b −4 2 −3 a + d MATH 22A: LINEAR ALGEBRA Chapter 2 1 3 0 0 0 0 3 9 1 3 0 0 0 0 0 0 1 3 2 −1 0 −1 2 1 −3 6 3 8 −7 2 2 −1 0 −1 2 1 −3 6 3 2 2 a −2 a + c d a a+b −2 a + c a+b −4 2 −3 a + d −1 0 a 0 0 1 −2 −1 −a − b 0 0 −3 6 3 −2 a + c 0 0 2 −4 2 −3 a + d MATH 22A: LINEAR ALGEBRA Chapter 2 1 3 2 −1 0 a 0 0 1 −2 −1 −a − b 0 0 −3 6 3 −2 a + c 0 0 2 −4 2 −3 a + d MATH 22A: LINEAR ALGEBRA Chapter 2 1 3 2 −1 0 a 0 0 1 −2 −1 −a − b 0 0 −3 6 3 −2 a + c 0 0 2 −4 2 −3 a + d 1 3 2 −1 0 a 0 0 1 −2 −1 −a − b 0 0 0 0 0 −5 a − 3 b + c 0 0 2 −4 2 −3 a + d MATH 22A: LINEAR ALGEBRA Chapter 2 1 3 2 −1 0 a 0 0 1 −2 −1 −a − b 0 0 −3 6 3 −2 a + c 0 0 2 −4 2 −3 a + d 1 3 2 −1 0 a 0 0 0 −5 a − 3 b + c 2 −4 2 −3 a + d 2 −1 0 a 1 −2 −1 −a − b 0 0 0 −5 a − 3 b + c 0 0 0 0 4 −a + 2 b + d 0 0 0 0 0 0 1 3 0 0 0 0 1 −2 −1 −a − b MATH 22A: LINEAR ALGEBRA Chapter 2 1 3 2 −1 0 a 0 0 1 −2 −1 −a − b 0 0 0 0 0 −5 a − 3 b + c 0 0 0 0 4 −a + 2 b + d MATH 22A: LINEAR ALGEBRA Chapter 2 1 3 2 −1 0 0 0 0 0 0 1 3 0 0 0 0 0 a 0 0 0 −5 a − 3 b + c 0 0 4 −a + 2 b + d 2 −1 0 a 1 −2 −1 −a − b 0 0 4 −a + 2 b + d 1 −2 −1 0 0 0 0 0 −a − b −5 a − 3 b + c MATH 22A: LINEAR ALGEBRA Chapter 2 1 3 2 −1 0 0 0 0 0 0 1 3 0 0 0 0 0 a 0 0 0 −5 a − 3 b + c 0 0 4 −a + 2 b + d 2 −1 0 a 1 −2 −1 −a − b 0 0 4 −a + 2 b + d 1 −2 −1 0 0 0 0 0 −a − b −5 a − 3 b + c That’s it! The variable part is in ECHELON FORM Now we can ’read off’ the solution! Of course, the solution depends on the values of a, b, c, d In this example, a solution exists ONLY when −5a − 3b + c = 0 MATH 22A: LINEAR ALGEBRA Chapter 2 Suppose a = 0, b = 0, c = 0, d = 0 then the matrix becomes 1 3 2 −1 0 0 0 0 1 −2 −1 0 0 0 0 0 4 0 0 0 0 0 0 0 Now there are INFINITELY MANY SOLUTIONS! WHY? WHAT KIND? MATH 22A: LINEAR ALGEBRA Chapter 2 Suppose a = 0, b = 0, c = 0, d = 0 then the matrix becomes 1 3 2 −1 0 0 0 0 1 −2 −1 0 0 0 0 0 4 0 0 0 0 0 0 0 Now there are INFINITELY MANY SOLUTIONS! WHY? WHAT KIND? Suppose a = 1, b = 1, c = 3, d = 2 then the matrix becomes 1 3 2 −1 0 1 0 0 1 −2 −1 −2 0 0 0 0 4 3 0 0 0 0 0 −5 Here we have NO SOLUTION! WHY? MATH 22A: LINEAR ALGEBRA Chapter 2 WARNING There are MANY ways to get ECHELON FORM! MATH 22A: LINEAR ALGEBRA Chapter 2 WARNING There are MANY ways to get ECHELON FORM! QUESTION Can you select a, b, c, d to make it have a SINGLE solution? 1 3 2 −1 0 a 0 0 1 −2 −1 −a − b 0 0 0 0 4 −a + 2 b + d 0 0 0 0 0 −5 a − 3 b + c MATH 22A: LINEAR ALGEBRA Chapter 2 WARNING There are MANY ways to get ECHELON FORM! QUESTION Can you select a, b, c, d to make it have a SINGLE solution? 1 3 2 −1 0 a 0 0 1 −2 −1 −a − b 0 0 0 0 4 −a + 2 b + d 0 0 0 0 0 −5 a − 3 b + c System has a solution ONLY when −5a − 3b + c = 0 In that case the free variables are 2nd and 4rd columns (y,u) MATH 22A: LINEAR ALGEBRA Chapter 2 WARNING There are MANY ways to get ECHELON FORM! QUESTION Can you select a, b, c, d to make it have a SINGLE solution? 1 3 2 −1 0 a 0 0 1 −2 −1 −a − b 0 0 0 0 4 −a + 2 b + d 0 0 0 0 0 −5 a − 3 b + c System has a solution ONLY when −5a − 3b + c = 0 In that case the free variables are 2nd and 4rd columns (y,u) INFINITELY MANY SOLUTIONS, but 2-dimensional, because there are 2 free variables! These solutions form an (affine) plane. No matter how we choose a, b, c, d, if we there is one solution, there are INFINITELY MANY SOLUTIONS. MATH 22A: LINEAR ALGEBRA Chapter 2 Given a system of m equations and n unknowns. (Now m 6= n is OK!) Apply elementary row operations to the matrix! MATH 22A: LINEAR ALGEBRA Chapter 2 Given a system of m equations and n unknowns. (Now m 6= n is OK!) Apply elementary row operations to the matrix! Definition An m × n matrix is in echelon form if it has an staircase structure. ∗ ? ? ? ? ? ? ? ... ? 0 0 ∗ ? ? ? ? ? ... ? 0 0 0 0 0 0 ∗ ? ... ? .. .. .. .. .. .. .. .. . . .. . . . . . . . . . . 0 0 0 0 0 0 0 ∗ ... ? 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Rows full of zeros are at the bottom. MATH 22A: LINEAR ALGEBRA Chapter 2 Given a system of m equations and n unknowns. (Now m 6= n is OK!) Apply elementary row operations to the matrix! Definition An m × n matrix is in echelon form if it has an staircase structure. ∗ ? ? ? ? ? ? ? ... ? 0 0 ∗ ? ? ? ? ? ... ? 0 0 0 0 0 0 ∗ ? ... ? .. .. .. .. .. .. .. .. . . .. . . . . . . . . . . 0 0 0 0 0 0 0 ∗ ... ? 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Rows full of zeros are at the bottom. In a non-zero row, the first non-zero entry is called a PIVOT. MATH 22A: LINEAR ALGEBRA Chapter 2 Given a system of m equations and n unknowns. (Now m 6= n is OK!) Apply elementary row operations to the matrix! Definition An m × n matrix is in echelon form if it has an staircase structure. ∗ ? ? ? ? ? ? ? ... ? 0 0 ∗ ? ? ? ? ? ... ? 0 0 0 0 0 0 ∗ ? ... ? .. .. .. .. .. .. .. .. . . .. . . . . . . . . . . 0 0 0 0 0 0 0 ∗ ... ? 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Rows full of zeros are at the bottom. In a non-zero row, the first non-zero entry is called a PIVOT. Below each pivot there is a column of zeros. A pivot lies to the right of the pivot in the row above. MATH 22A: LINEAR ALGEBRA Chapter 2 KEY THEOREM version1 Theorem Any matrix A can be reduced to the echelon form by a finite sequence of legal row operations MATH 22A: LINEAR ALGEBRA Chapter 2 KEY THEOREM version1 Theorem Any matrix A can be reduced to the echelon form by a finite sequence of legal row operations Definition In echelon form, the variables corresponding to the columns containing a pivot are basic or pivot variables, MATH 22A: LINEAR ALGEBRA Chapter 2 KEY THEOREM version1 Theorem Any matrix A can be reduced to the echelon form by a finite sequence of legal row operations Definition In echelon form, the variables corresponding to the columns containing a pivot are basic or pivot variables, Variables corresponding to variables without a pivot are called free variables. MATH 22A: LINEAR ALGEBRA Chapter 2 KEY THEOREM version1 Theorem Any matrix A can be reduced to the echelon form by a finite sequence of legal row operations Definition In echelon form, the variables corresponding to the columns containing a pivot are basic or pivot variables, Variables corresponding to variables without a pivot are called free variables. Definition The rank of A is the number of basic variables. Rank is the same as the number of pivots. MATH 22A: LINEAR ALGEBRA Chapter 2 KEY THEOREM version1 Theorem Any matrix A can be reduced to the echelon form by a finite sequence of legal row operations Definition In echelon form, the variables corresponding to the columns containing a pivot are basic or pivot variables, Variables corresponding to variables without a pivot are called free variables. Definition The rank of A is the number of basic variables. Rank is the same as the number of pivots. From the echelon form, the solution to a system of equations proceeds by back substitution procedure. MATH 22A: LINEAR ALGEBRA Chapter 2 KEY THEOREM version1 Theorem Any matrix A can be reduced to the echelon form by a finite sequence of legal row operations Definition In echelon form, the variables corresponding to the columns containing a pivot are basic or pivot variables, Variables corresponding to variables without a pivot are called free variables. Definition The rank of A is the number of basic variables. Rank is the same as the number of pivots. From the echelon form, the solution to a system of equations proceeds by back substitution procedure. Solve each equation for the pivot variable, then the result is substituted into the preceding row before that one is solved. MATH 22A: LINEAR ALGEBRA Chapter 2 KEY THEOREM version1 Theorem Any matrix A can be reduced to the echelon form by a finite sequence of legal row operations Definition In echelon form, the variables corresponding to the columns containing a pivot are basic or pivot variables, Variables corresponding to variables without a pivot are called free variables. Definition The rank of A is the number of basic variables. Rank is the same as the number of pivots. From the echelon form, the solution to a system of equations proceeds by back substitution procedure. Solve each equation for the pivot variable, then the result is substituted into the preceding row before that one is solved. Final solution gives basic variables as combinations of the free variables. MATH 22A: LINEAR ALGEBRA Chapter 2 KEY THEOREM version1 Theorem Any matrix A can be reduced to the echelon form by a finite sequence of legal row operations Definition In echelon form, the variables corresponding to the columns containing a pivot are basic or pivot variables, Variables corresponding to variables without a pivot are called free variables. Definition The rank of A is the number of basic variables. Rank is the same as the number of pivots. From the echelon form, the solution to a system of equations proceeds by back substitution procedure. Solve each equation for the pivot variable, then the result is substituted into the preceding row before that one is solved. Final solution gives basic variables as combinations of the free variables. Free variables can take ANY value and parametrize all solutions of the system. MATH 22A: LINEAR ALGEBRA Chapter 2 Theorem A system Ax = b of m linear equations and n unknowns has either 1 2 3 Exactly one solution (NO free variables) Infinitely many solutions (ONE OR MORE free variables) No solution at all. (Row of zeros ending with non-zero constant). MATH 22A: LINEAR ALGEBRA Chapter 2 Theorem A system Ax = b of m linear equations and n unknowns has either 1 2 3 Exactly one solution (NO free variables) Infinitely many solutions (ONE OR MORE free variables) No solution at all. (Row of zeros ending with non-zero constant). The set of all vectors x that satisfy Ax = b is called the SOLUTION SPACE. MATH 22A: LINEAR ALGEBRA Chapter 2 Theorem A system Ax = b of m linear equations and n unknowns has either 1 2 3 Exactly one solution (NO free variables) Infinitely many solutions (ONE OR MORE free variables) No solution at all. (Row of zeros ending with non-zero constant). The set of all vectors x that satisfy Ax = b is called the SOLUTION SPACE. Geometric meaning: Each free variable is one extra dimension of the solution space MATH 22A: LINEAR ALGEBRA Chapter 2 Theorem A system Ax = b of m linear equations and n unknowns has either 1 2 3 Exactly one solution (NO free variables) Infinitely many solutions (ONE OR MORE free variables) No solution at all. (Row of zeros ending with non-zero constant). The set of all vectors x that satisfy Ax = b is called the SOLUTION SPACE. Geometric meaning: Each free variable is one extra dimension of the solution space IMPORTANT CASE: IF the right-hand side vector b = ZERO? HOMOGENEOUS SYSTEM MATH 22A: LINEAR ALGEBRA Chapter 2 Theorem A system Ax = b of m linear equations and n unknowns has either 1 2 3 Exactly one solution (NO free variables) Infinitely many solutions (ONE OR MORE free variables) No solution at all. (Row of zeros ending with non-zero constant). The set of all vectors x that satisfy Ax = b is called the SOLUTION SPACE. Geometric meaning: Each free variable is one extra dimension of the solution space IMPORTANT CASE: IF the right-hand side vector b = ZERO? HOMOGENEOUS SYSTEM Question For what kind of matrices can a homogeneous system have finite solutions? MATH 22A: LINEAR ALGEBRA Chapter 2 Theorem A system Ax = b of m linear equations and n unknowns has either 1 2 3 Exactly one solution (NO free variables) Infinitely many solutions (ONE OR MORE free variables) No solution at all. (Row of zeros ending with non-zero constant). The set of all vectors x that satisfy Ax = b is called the SOLUTION SPACE. Geometric meaning: Each free variable is one extra dimension of the solution space IMPORTANT CASE: IF the right-hand side vector b = ZERO? HOMOGENEOUS SYSTEM Question For what kind of matrices can a homogeneous system have finite solutions? Definition: The solution space of Ax = 0 is called the NULLSPACE of A, denoted N(A). MATH 22A: LINEAR ALGEBRA Chapter 2 Theorem A system Ax = b of m linear equations and n unknowns has either 1 2 3 Exactly one solution (NO free variables) Infinitely many solutions (ONE OR MORE free variables) No solution at all. (Row of zeros ending with non-zero constant). The set of all vectors x that satisfy Ax = b is called the SOLUTION SPACE. Geometric meaning: Each free variable is one extra dimension of the solution space IMPORTANT CASE: IF the right-hand side vector b = ZERO? HOMOGENEOUS SYSTEM Question For what kind of matrices can a homogeneous system have finite solutions? Definition: The solution space of Ax = 0 is called the NULLSPACE of A, denoted N(A). For your education: The rest of the world calls the nullspace, the kernel of A. MATH 22A: LINEAR ALGEBRA Chapter 2 MATH 22A: LINEAR ALGEBRA Chapter 2 MATH 22A: LINEAR ALGEBRA Chapter 2 Recall For an m × n matrix A and an n × p matrix B: Say B has column vectors B = [v1 v2 v3 . . . vp ], then AB = [Av1 Av2 Av3 ... Avp ] MATH 22A: LINEAR ALGEBRA Chapter 2 Recall For an m × n matrix A and an n × p matrix B: Say B has column vectors B = [v1 v2 v3 . . . vp ], then AB = [Av1 Av2 Av3 ... Avp ] NOTE: To multiply matrices, take the dot product of each row of A with each column of B, MATH 22A: LINEAR ALGEBRA Chapter 2 The entry (AB)ij equals (row i of A) · (column j of B) MATH 22A: LINEAR ALGEBRA Chapter 2 The entry (AB)ij equals (row i of A) · (column j of B) Question How many multiplications are necessary when multiplying m × n , n × p matrices? MATH 22A: LINEAR ALGEBRA Chapter 2 The entry (AB)ij equals (row i of A) · (column j of B) Question How many multiplications are necessary when multiplying m × n , n × p matrices? mpn MATH 22A: LINEAR ALGEBRA Chapter 2 The entry (AB)ij equals (row i of A) · (column j of B) Question How many multiplications are necessary when multiplying m × n , n × p matrices? mpn Properties of multiplication: (AB)C=A(BC) A(B+C)=AB+AC (A+B)C=AC+BC Ap = AAA · · · A with p factors. (Ap )(Aq ) = Ap+q (Ap )q = Apq MATH 22A: LINEAR ALGEBRA Chapter 2 Elimination Matrices The identity matrix I has only 1’s on the diagonal, ai,i = 1, zero’s elsewhere. MATH 22A: LINEAR ALGEBRA Chapter 2 Elimination Matrices The identity matrix I has only 1’s on the diagonal, ai,i = 1, zero’s elsewhere. The matrix Ei,j (λ) that subtracts a multiple λ of row j from row i has The entry −λ in the i, j position, aij = −λ, Diagonal entries are 1. Zeroes elsewhere! MATH 22A: LINEAR ALGEBRA Chapter 2 Elimination Matrices The identity matrix I has only 1’s on the diagonal, ai,i = 1, zero’s elsewhere. The matrix Ei,j (λ) that subtracts a multiple λ of row j from row i has The entry −λ in the i, j position, aij = −λ, Diagonal entries are 1. Zeroes elsewhere! Example 1 0 0 1 −2 1 y1 0 1 0 0 5 −1 y3 0 −1 1 0 5 −2 + q y2 − 2 y1 = MATH 22A: LINEAR ALGEBRA Chapter 2 Elimination Matrices The identity matrix I has only 1’s on the diagonal, ai,i = 1, zero’s elsewhere. The matrix Ei,j (λ) that subtracts a multiple λ of row j from row i has The entry −λ in the i, j position, aij = −λ, Diagonal entries are 1. Zeroes elsewhere! Example 1 0 0 1 −2 1 y1 0 1 0 0 5 −1 y3 0 −1 1 0 5 −2 + q y2 − 2 y1 1 −2 0 0 5 0 1 y1 −1 y3 = −1 + q −y3 + y2 − 2 y1 MATH 22A: LINEAR ALGEBRA Chapter 2 Suppose a matrix E substracts 7 times row i from row j of an M × N matrix. MATH 22A: LINEAR ALGEBRA Chapter 2 Suppose a matrix E substracts 7 times row i from row j of an M × N matrix. Question 1 What is E ? MATH 22A: LINEAR ALGEBRA Chapter 2 Suppose a matrix E substracts 7 times row i from row j of an M × N matrix. Question 1 What is E ? Question 2 What is the matrix E −1 that reverses the step (E −1 E = I ) MATH 22A: LINEAR ALGEBRA Chapter 2 Suppose a matrix E substracts 7 times row i from row j of an M × N matrix. Question 1 What is E ? Question 2 What is the matrix E −1 that reverses the step (E −1 E = I ) Question 3 True or false: EE −1 = I ? MATH 22A: LINEAR ALGEBRA Chapter 2 Suppose a matrix E substracts 7 times row i from row j of an M × N matrix. Question 1 What is E ? Question 2 What is the matrix E −1 that reverses the step (E −1 E = I ) Question 3 True or false: EE −1 = I ? What is the effect of E (EA)? MATH 22A: LINEAR ALGEBRA Chapter 2 True / False challenge (A − B)2 = A2 − 2AB − B 2 . MATH 22A: LINEAR ALGEBRA Chapter 2 True / False challenge (A − B)2 = A2 − 2AB − B 2 . (A − B)2 = (A2 − B 2 ). MATH 22A: LINEAR ALGEBRA Chapter 2 True / False challenge (A − B)2 = A2 − 2AB − B 2 . (A − B)2 = (A2 − B 2 ). (A − B)2 = A(A − B) − B(A − B). MATH 22A: LINEAR ALGEBRA Chapter 2 True / False challenge (A − B)2 = A2 − 2AB − B 2 . (A − B)2 = (A2 − B 2 ). (A − B)2 = A(A − B) − B(A − B). If A2 is defined then A is necessarily square matrix. MATH 22A: LINEAR ALGEBRA Chapter 2 True / False challenge (A − B)2 = A2 − 2AB − B 2 . (A − B)2 = (A2 − B 2 ). (A − B)2 = A(A − B) − B(A − B). If A2 is defined then A is necessarily square matrix. If AB and BA are defined then A and B are square. MATH 22A: LINEAR ALGEBRA Chapter 2 True / False challenge (A − B)2 = A2 − 2AB − B 2 . (A − B)2 = (A2 − B 2 ). (A − B)2 = A(A − B) − B(A − B). If A2 is defined then A is necessarily square matrix. If AB and BA are defined then A and B are square. If AB and BA are defined then AB and BA are square MATH 22A: LINEAR ALGEBRA Chapter 2 True / False challenge (A − B)2 = A2 − 2AB − B 2 . (A − B)2 = (A2 − B 2 ). (A − B)2 = A(A − B) − B(A − B). If A2 is defined then A is necessarily square matrix. If AB and BA are defined then A and B are square. If AB and BA are defined then AB and BA are square If AB = B then A = I MATH 22A: LINEAR ALGEBRA Chapter 2 True / False challenge (A − B)2 = A2 − 2AB − B 2 . (A − B)2 = (A2 − B 2 ). (A − B)2 = A(A − B) − B(A − B). If A2 is defined then A is necessarily square matrix. If AB and BA are defined then A and B are square. If AB and BA are defined then AB and BA are square If AB = B then A = I If A is 2 × 4, B is 4 × 7 and C is 7 × 10, (AB)C has fewer multiplications than A(BC ). MATH 22A: LINEAR ALGEBRA Chapter 2 True or False OR fill the blank 1 A system Ax = 0 of m equations in n unknowns is called ????? MATH 22A: LINEAR ALGEBRA Chapter 2 True or False OR fill the blank 1 A system Ax = 0 of m equations in n unknowns is called ????? 2 The space of solutions of Ax = 0 is called the ????? MATH 22A: LINEAR ALGEBRA Chapter 2 True or False OR fill the blank 1 A system Ax = 0 of m equations in n unknowns is called ????? 2 The space of solutions of Ax = 0 is called the ????? 3 If u1 and u2 are both solutions of Ax = 0, 8u1 − 11u2 is a solution too. MATH 22A: LINEAR ALGEBRA Chapter 2 True or False OR fill the blank 1 A system Ax = 0 of m equations in n unknowns is called ????? 2 The space of solutions of Ax = 0 is called the ????? 3 If u1 and u2 are both solutions of Ax = 0, 8u1 − 11u2 is a solution too. 4 It always has a trivial solution. MATH 22A: LINEAR ALGEBRA Chapter 2 True or False OR fill the blank 1 A system Ax = 0 of m equations in n unknowns is called ????? 2 The space of solutions of Ax = 0 is called the ????? 3 If u1 and u2 are both solutions of Ax = 0, 8u1 − 11u2 is a solution too. 4 It always has a trivial solution. 5 It has a non-trivial solution (6= 0) ⇐⇒ rank(A) < n. MATH 22A: LINEAR ALGEBRA Chapter 2 True or False OR fill the blank 1 A system Ax = 0 of m equations in n unknowns is called ????? 2 The space of solutions of Ax = 0 is called the ????? 3 If u1 and u2 are both solutions of Ax = 0, 8u1 − 11u2 is a solution too. 4 It always has a trivial solution. 5 It has a non-trivial solution (6= 0) ⇐⇒ rank(A) < n. 6 If m < n then the system has always a non-trivial solution. MATH 22A: LINEAR ALGEBRA Chapter 2 True or False OR fill the blank 1 A system Ax = 0 of m equations in n unknowns is called ????? 2 The space of solutions of Ax = 0 is called the ????? 3 If u1 and u2 are both solutions of Ax = 0, 8u1 − 11u2 is a solution too. 4 It always has a trivial solution. 5 It has a non-trivial solution (6= 0) ⇐⇒ rank(A) < n. 6 If m < n then the system has always a non-trivial solution. 7 If m = n then the system has a non-trivial solution if and only if A can be row reduced until it has a row of zeros. MATH 22A: LINEAR ALGEBRA Chapter 2 Inverse matrix We say that a square n × n matrix is A invertible when there is another matrix A−1 such that AA−1 = A−1 A = I MATH 22A: LINEAR ALGEBRA Chapter 2 Inverse matrix We say that a square n × n matrix is A invertible when there is another matrix A−1 such that AA−1 = A−1 A = I a b Example For a 2 × 2 matrix its inverse is c d 1 d −b ad − bc −c a MATH 22A: LINEAR ALGEBRA Chapter 2 Inverse matrix We say that a square n × n matrix is A invertible when there is another matrix A−1 such that AA−1 = A−1 A = I a b Example For a 2 × 2 matrix its inverse is c d 1 d −b ad − bc −c a Observation Not all matrices have inverses MATH 22A: LINEAR ALGEBRA Chapter 2 Inverse matrix We say that a square n × n matrix is A invertible when there is another matrix A−1 such that AA−1 = A−1 A = I a b Example For a 2 × 2 matrix its inverse is c d 1 d −b ad − bc −c a Observation Not all matrices have inverses Observation The inverse matrix, if it exists is UNIQUE. MATH 22A: LINEAR ALGEBRA Chapter 2 Inverse matrix We say that a square n × n matrix is A invertible when there is another matrix A−1 such that AA−1 = A−1 A = I a b Example For a 2 × 2 matrix its inverse is c d 1 d −b ad − bc −c a Observation Not all matrices have inverses Observation The inverse matrix, if it exists is UNIQUE. Observation If A is invertible there is one and only one solution to Ax = b, which is x = A−1 b. MATH 22A: LINEAR ALGEBRA Chapter 2 Inverse matrix We say that a square n × n matrix is A invertible when there is another matrix A−1 such that AA−1 = A−1 A = I a b Example For a 2 × 2 matrix its inverse is c d 1 d −b ad − bc −c a Observation Not all matrices have inverses Observation The inverse matrix, if it exists is UNIQUE. Observation If A is invertible there is one and only one solution to Ax = b, which is x = A−1 b. Observation Suppose there is a non-zero vector x with Ax = 0, then A is not invertible. MATH 22A: LINEAR ALGEBRA Chapter 2 Inverse matrix We say that a square n × n matrix is A invertible when there is another matrix A−1 such that AA−1 = A−1 A = I a b Example For a 2 × 2 matrix its inverse is c d 1 d −b ad − bc −c a Observation Not all matrices have inverses Observation The inverse matrix, if it exists is UNIQUE. Observation If A is invertible there is one and only one solution to Ax = b, which is x = A−1 b. Observation Suppose there is a non-zero vector x with Ax = 0, then A is not invertible. Question What is the inverse of AB? MATH 22A: LINEAR ALGEBRA Chapter 2 Inverse matrix We say that a square n × n matrix is A invertible when there is another matrix A−1 such that AA−1 = A−1 A = I a b Example For a 2 × 2 matrix its inverse is c d 1 d −b ad − bc −c a Observation Not all matrices have inverses Observation The inverse matrix, if it exists is UNIQUE. Observation If A is invertible there is one and only one solution to Ax = b, which is x = A−1 b. Observation Suppose there is a non-zero vector x with Ax = 0, then A is not invertible. Question What is the inverse of AB? MATH 22A: LINEAR ALGEBRA Chapter 2 What is the inverse of A = 1 2 ? 3 4 MATH 22A: LINEAR ALGEBRA Chapter 2 1 2 What is the inverse of A = ? 3 4 a b −1 It is a matrix A = and we must have c d 1 2 a b 1 0 −1 AA = = 3 4 c d 0 1 MATH 22A: LINEAR ALGEBRA Chapter 2 1 2 What is the inverse of A = ? 3 4 a b −1 It is a matrix A = and we must have c d 1 2 a b 1 0 −1 AA = = 3 4 c d 0 1 This is the same as a + 2c b + 2d 1 0 = 3a + 4c 3b + 4d 0 1 MATH 22A: LINEAR ALGEBRA Chapter 2 1 2 What is the inverse of A = ? 3 4 a b −1 It is a matrix A = and we must have c d 1 2 a b 1 0 −1 AA = = 3 4 c d 0 1 This is the same as a + 2c b + 2d 1 0 = 3a + 4c 3b + 4d 0 1 Finding the inverse is the same as solving a + 2c = 1 b + 2d = 0 3a + 4c = 0 3b + 4d = 1 MATH 22A: LINEAR ALGEBRA Chapter 2 1 2 What is the inverse of A = ? 3 4 a b −1 It is a matrix A = and we must have c d 1 2 a b 1 0 −1 AA = = 3 4 c d 0 1 This is the same as a + 2c b + 2d 1 0 = 3a + 4c 3b + 4d 0 1 Finding the inverse is the same as solving a + 2c = 1 b + 2d = 0 3a + 4c = 0 3b + 4d = 1 Key Point: We just need to solve a linear system....Which we know how to do! MATH 22A: LINEAR ALGEBRA Chapter 2 When are square matrices invertible? MATH 22A: LINEAR ALGEBRA Chapter 2 When are square matrices invertible? We say that a square n × n matrix is singular when the number of pivots is less than n. Otherwise, it is non-singular. MATH 22A: LINEAR ALGEBRA Chapter 2 When are square matrices invertible? We say that a square n × n matrix is singular when the number of pivots is less than n. Otherwise, it is non-singular. Theorem A square matrix is invertible if and only if A is non-singular. MATH 22A: LINEAR ALGEBRA Chapter 2 When are square matrices invertible? We say that a square n × n matrix is singular when the number of pivots is less than n. Otherwise, it is non-singular. Theorem A square matrix is invertible if and only if A is non-singular. We are going to give a proof using an Algorithm. The Gauss-Jordan method. MATH 22A: LINEAR ALGEBRA Chapter 2 When are square matrices invertible? We say that a square n × n matrix is singular when the number of pivots is less than n. Otherwise, it is non-singular. Theorem A square matrix is invertible if and only if A is non-singular. We are going to give a proof using an Algorithm. The Gauss-Jordan method. The Gauss-Jordan method solves the equation AA−1 = I , which is the same as n different systems of equations with A as a matrix and the columns of I as the right-hand side vectors. MATH 22A: LINEAR ALGEBRA Chapter 2 When are square matrices invertible? We say that a square n × n matrix is singular when the number of pivots is less than n. Otherwise, it is non-singular. Theorem A square matrix is invertible if and only if A is non-singular. We are going to give a proof using an Algorithm. The Gauss-Jordan method. The Gauss-Jordan method solves the equation AA−1 = I , which is the same as n different systems of equations with A as a matrix and the columns of I as the right-hand side vectors. Gauss-Jordan is a practical method to find inverses that is faster. MATH 22A: LINEAR ALGEBRA Chapter 2 Given A an n × n matrix, we look for another n × n matrix B = (bij ) with AB = I . MATH 22A: LINEAR ALGEBRA Chapter 2 Given A an n × n matrix, we look for another n × n matrix B = (bij ) with AB = I . b1j b2j Say the columns of B are xj = b3j .. . bnj MATH 22A: LINEAR ALGEBRA Chapter 2 Given A an n × n matrix, we look for another n × n matrix B = (bij ) with AB = I . b1j b2j Say the columns of B are xj = b3j .. . bnj 0 .. . The columns of the identity matrix are ej = 1 .. . 0 MATH 22A: LINEAR ALGEBRA Chapter 2 Given A an n × n matrix, we look for another n × n matrix B = (bij ) with AB = I . b1j b2j Say the columns of B are xj = b3j .. . bnj 0 .. . The columns of the identity matrix are ej = 1 .. . 0 Key Point When we multiply AB = I , in particular Axj = ej MATH 22A: LINEAR ALGEBRA Chapter 2 Finding the inverse is the same as solving the n systems of equations Ax1 = e1 , Ax2 = e2 , . . . , Axn = en MATH 22A: LINEAR ALGEBRA Chapter 2 Finding the inverse is the same as solving the n systems of equations Ax1 = e1 , Ax2 = e2 , . . . , Axn = en Each individual system COULD be solved SEPARATELY....we set up augmented matrices [A |ei ] and do row reduction. MATH 22A: LINEAR ALGEBRA Chapter 2 Finding the inverse is the same as solving the n systems of equations Ax1 = e1 , Ax2 = e2 , . . . , Axn = en Each individual system COULD be solved SEPARATELY....we set up augmented matrices [A |ei ] and do row reduction. This is a BAD IDEA! MATH 22A: LINEAR ALGEBRA Chapter 2 Finding the inverse is the same as solving the n systems of equations Ax1 = e1 , Ax2 = e2 , . . . , Axn = en Each individual system COULD be solved SEPARATELY....we set up augmented matrices [A |ei ] and do row reduction. This is a BAD IDEA! GREAT IDEA: Solve all n systems SIMULTANEOUSLY, we form an n × 2n matrix [A|e1 e2 . . . en ] MATH 22A: LINEAR ALGEBRA Chapter 2 Finding the inverse is the same as solving the n systems of equations Ax1 = e1 , Ax2 = e2 , . . . , Axn = en Each individual system COULD be solved SEPARATELY....we set up augmented matrices [A |ei ] and do row reduction. This is a BAD IDEA! GREAT IDEA: Solve all n systems SIMULTANEOUSLY, we form an n × 2n matrix [A|e1 e2 . . . en ] This is just the matrix [A I] MATH 22A: LINEAR ALGEBRA Chapter 2 Finding the inverse is the same as solving the n systems of equations Ax1 = e1 , Ax2 = e2 , . . . , Axn = en Each individual system COULD be solved SEPARATELY....we set up augmented matrices [A |ei ] and do row reduction. This is a BAD IDEA! GREAT IDEA: Solve all n systems SIMULTANEOUSLY, we form an n × 2n matrix [A|e1 e2 . . . en ] This is just the matrix [A I] We can row reduce until we either manage to arrive MATH 22A: LINEAR ALGEBRA Chapter 2 Finding the inverse is the same as solving the n systems of equations Ax1 = e1 , Ax2 = e2 , . . . , Axn = en Each individual system COULD be solved SEPARATELY....we set up augmented matrices [A |ei ] and do row reduction. This is a BAD IDEA! GREAT IDEA: Solve all n systems SIMULTANEOUSLY, we form an n × 2n matrix [A|e1 e2 . . . en ] This is just the matrix [A I] We can row reduce until we either manage to arrive to [I | B] in row echelon form (FOUND INVERSE) to last row of zeros with a non zero right side (NO INVERSE) MATH 22A: LINEAR ALGEBRA Chapter 2 Let us compute the inverse of 1 1 1 0 2 3 5 5 1 1 1 1 | 1 0 0 0 2 3 | 0 1 0 5 5 1 | 0 0 1 MATH 22A: LINEAR ALGEBRA Chapter 2 Let us compute the inverse of 1 1 1 0 2 3 5 5 1 1 1 1 | 1 0 0 0 2 3 | 0 1 0 5 5 1 | 0 0 1 1 1 1 | 1 0 0 0 2 3 | 0 1 0 0 0 −4 | −5 0 1 Already in row reduced form, but now we keep going! We want to get the identity: MATH 22A: LINEAR ALGEBRA Chapter 2 1 1 1 | 1 0 0 0 2 3 | 0 1 0 0 0 −4 | −5 0 1 MATH 22A: LINEAR ALGEBRA Chapter 2 1 1 1 | 1 0 0 0 2 3 | 0 1 0 0 0 −4 | −5 0 1 1 1 1 | 1 0 0 0 1 3 | 0 1 0 2 2 0 0 −4 | −5 0 1 MATH 22A: LINEAR ALGEBRA Chapter 2 1 1 1 | 1 0 0 0 2 3 | 0 1 0 0 0 −4 | −5 0 1 1 1 1 | 1 0 0 0 1 3 | 0 1 0 2 2 0 0 −4 | −5 0 1 1 0 − 21 | 1 − 12 1 0 1 3 | 0 2 2 0 0 −4 | −5 0 0 0 1 MATH 22A: LINEAR ALGEBRA Chapter 2 1 1 1 | 1 0 0 0 2 3 | 0 1 0 0 0 −4 | −5 0 1 1 1 1 | 1 0 0 0 1 3 | 0 1 0 2 2 0 0 −4 | −5 0 1 1 0 − 21 | 1 − 12 1 0 1 3 | 0 2 2 0 0 −4 | −5 0 1 0 − 21 0 1 3 2 0 0 1 | 1 − 21 | 0 12 | 54 0 0 0 1 0 0 − 41 MATH 22A: LINEAR ALGEBRA Chapter 2 1 1 1 | 1 0 0 0 2 3 | 0 1 0 0 0 −4 | −5 0 1 1 1 1 | 1 0 0 0 1 3 | 0 1 0 2 2 0 0 −4 | −5 0 1 1 0 − 21 | 1 − 12 1 0 1 3 | 0 2 2 0 0 −4 | −5 0 1 0 − 21 0 1 3 2 0 0 1 | 1 − 21 | 0 12 | 54 0 0 0 1 0 0 − 41 MATH 22A: LINEAR ALGEBRA Chapter 2 1 0 − 21 0 1 3 2 0 0 1 | 1 − 21 | 0 12 | 54 0 0 0 − 41 MATH 22A: LINEAR ALGEBRA Chapter 2 1 0 − 21 0 1 3 2 0 0 1 1 0 − 21 0 1 0 0 0 1 | 1 − 21 | 0 12 | 54 0 | 1 | − 15 8 5 | 4 0 0 − 41 − 12 0 3 8 0 − 41 1 2 MATH 22A: LINEAR ALGEBRA Chapter 2 1 0 − 21 0 1 3 2 0 0 1 1 0 − 21 0 1 0 0 0 1 | 1 − 21 | 0 12 | 54 0 | 1 | − 15 8 5 | 4 1 0 0 | 13 8 0 1 0 | − 15 8 5 0 0 1 | 4 0 0 − 41 − 12 0 3 8 0 − 41 1 2 − 12 − 81 0 − 41 1 2 3 8 MATH 22A: LINEAR ALGEBRA Chapter 2 1 0 − 21 0 1 3 2 0 0 1 1 0 − 21 0 1 0 0 0 1 | 1 − 21 | 0 12 | 54 0 | 1 | − 15 8 5 | 4 1 0 0 | 13 8 0 1 0 | − 15 8 5 0 0 1 | 4 0 0 − 41 − 12 0 3 8 0 − 41 1 2 − 12 − 81 0 − 41 1 2 3 8 We have found the INVERSE! MATH 22A: LINEAR ALGEBRA Chapter 2 1 2 −3 | 1 0 0 1 −2 1 | 0 1 0 5 −2 −3 | 0 0 1 MATH 22A: LINEAR ALGEBRA Chapter 2 1 2 −3 | 1 0 0 1 −2 1 | 0 1 0 5 −2 −3 | 0 0 1 1 2 −3 | 1 0 0 0 −4 4 | −1 1 0 5 −2 −3 | 0 0 1 MATH 22A: LINEAR ALGEBRA Chapter 2 1 2 −3 | 1 0 0 1 −2 1 | 0 1 0 5 −2 −3 | 0 0 1 1 2 −3 | 1 0 0 0 −4 4 | −1 1 0 5 −2 −3 | 0 0 1 1 2 −3 | 1 0 0 0 −4 4 | −1 1 0 0 −12 12 | −5 0 1 MATH 22A: LINEAR ALGEBRA Chapter 2 1 2 −3 | 1 0 0 1 −2 1 | 0 1 0 5 −2 −3 | 0 0 1 1 2 −3 | 1 0 0 0 −4 4 | −1 1 0 5 −2 −3 | 0 0 1 1 2 −3 | 1 0 0 0 −4 4 | −1 1 0 0 −12 12 | −5 0 1 1 2 −3 | 1 0 0 0 −4 4 | −1 1 0 0 0 0 | −2 −3 1 NO INVERSE POSSIBLE! MATH 22A: LINEAR ALGEBRA Chapter 2 A = LU or HOW TO FACTORIZE A MATRIX We already saw that Row operations = Matrix Multiplication We use Elimination Matrices to create zeros and Permutation Matrices to swap rows. The identity matrix I has only 1’s on the diagonal, ai,i = 1, zeros elsewhere. MATH 22A: LINEAR ALGEBRA Chapter 2 A = LU or HOW TO FACTORIZE A MATRIX We already saw that Row operations = Matrix Multiplication We use Elimination Matrices to create zeros and Permutation Matrices to swap rows. The identity matrix I has only 1’s on the diagonal, ai,i = 1, zeros elsewhere. The matrix Ei,j (λ) that subtracts a multiple λ of row j from row i has The entry −λ in the i, j position, aij = −λ, Diagonals entries are 1. Zeros elsewhere! MATH 22A: LINEAR ALGEBRA Chapter 2 A = LU or HOW TO FACTORIZE A MATRIX We already saw that Row operations = Matrix Multiplication We use Elimination Matrices to create zeros and Permutation Matrices to swap rows. The identity matrix I has only 1’s on the diagonal, ai,i = 1, zeros elsewhere. The matrix Ei,j (λ) that subtracts a multiple λ of row j from row i has The entry −λ in the i, j position, aij = −λ, Diagonals entries are 1. Zeros elsewhere! Example 1 1 1 −2 s 0 −1 1 2 1 3 6 2 0 0 MATH 22A: LINEAR ALGEBRA Chapter 2 We subtract 2 times row 1 from row 3 via matrix multiplication MATH 22A: LINEAR ALGEBRA Chapter 2 We subtract 2 times row 1 from row 3 via matrix multiplication 1 0 −2 0 0 1 0 1 0 MATH 22A: LINEAR ALGEBRA Chapter 2 We subtract 2 times row 1 from row 3 via matrix multiplication 1 0 −2 0 0 1 0 0 1 2 0 1 1 1 −2 −1 1 1 3 6 2 s 0 = 0 MATH 22A: LINEAR ALGEBRA Chapter 2 We subtract 2 times row 1 from row 3 via matrix multiplication 1 0 −2 0 0 1 0 0 1 2 0 1 1 1 −2 −1 1 1 3 6 2 s 1 0 = 0 0 0 1 1 −2 s −1 1 6 0 −1 6 −2 s 1 Then subtract row 2 from row 3 by matrix multiplication. MATH 22A: LINEAR ALGEBRA Chapter 2 We subtract 2 times row 1 from row 3 via matrix multiplication 1 0 −2 0 0 1 0 0 1 2 0 1 1 1 −2 −1 1 1 3 6 2 s 1 0 = 0 0 0 1 1 −2 1 0 0 0 0 −1 1 6 0 −1 6 −2 s 1 Then subtract row 2 from row 3 by matrix multiplication. s 0 −1 1 1 MATH 22A: LINEAR ALGEBRA Chapter 2 We subtract 2 times row 1 from row 3 via matrix multiplication 1 0 −2 0 0 1 0 0 1 2 0 1 1 1 −2 −1 1 1 3 6 2 s 1 0 = 0 0 0 1 1 −2 1 0 0 0 0 1 0 0 −1 1 0 1 1 −2 s −1 1 6 0 = −1 1 6 −2 s 1 −1 1 6 0 −1 6 −2 s 1 Then subtract row 2 from row 3 by matrix multiplication. s MATH 22A: LINEAR ALGEBRA Chapter 2 We subtract 2 times row 1 from row 3 via matrix multiplication 1 0 −2 0 0 1 0 0 1 2 0 1 1 1 −2 −1 1 1 3 6 2 s 1 0 = 0 0 0 1 −2 1 s −1 1 6 0 −1 6 −2 s 1 Then subtract row 2 from row 3 by matrix multiplication. 1 0 0 0 0 1 0 0 −1 1 0 1 1 1 −2 −1 1 6 −1 1 6 s 1 = 0 −2 s 0 0 1 −2 s −1 1 6 0 0 0 0 −2 s 1 MATH 22A: LINEAR ALGEBRA Chapter 2 The matrices we use are special: MATH 22A: LINEAR ALGEBRA Chapter 2 The matrices we use are special: An n × n matrix A is upper triangular if every entry aij with j > i is zero. MATH 22A: LINEAR ALGEBRA Chapter 2 The matrices we use are special: An n × n matrix A is upper triangular if every entry aij with j > i is zero. An n × n matrix A is lower triangular if every entry aij with j < i is zero. MATH 22A: LINEAR ALGEBRA Chapter 2 The matrices we use are special: An n × n matrix A is upper triangular if every entry aij with j > i is zero. An n × n matrix A is lower triangular if every entry aij with j < i is zero. Proposition If A, B are upper triangular matrices, then their product is upper triangular. Same for lower triangular! MATH 22A: LINEAR ALGEBRA Chapter 2 The matrices we use are special: An n × n matrix A is upper triangular if every entry aij with j > i is zero. An n × n matrix A is lower triangular if every entry aij with j < i is zero. Proposition If A, B are upper triangular matrices, then their product is upper triangular. Same for lower triangular! Proposition If A is upper (lower) triangular non-singular, then A−1 is upper triangular, too. MATH 22A: LINEAR ALGEBRA Chapter 2 The matrices we use are special: An n × n matrix A is upper triangular if every entry aij with j > i is zero. An n × n matrix A is lower triangular if every entry aij with j < i is zero. Proposition If A, B are upper triangular matrices, then their product is upper triangular. Same for lower triangular! Proposition If A is upper (lower) triangular non-singular, then A−1 is upper triangular, too. A matrix is elementary if it is obtained from the identity matrix by a single legal row operation. MATH 22A: LINEAR ALGEBRA Chapter 2 The matrices we use are special: An n × n matrix A is upper triangular if every entry aij with j > i is zero. An n × n matrix A is lower triangular if every entry aij with j < i is zero. Proposition If A, B are upper triangular matrices, then their product is upper triangular. Same for lower triangular! Proposition If A is upper (lower) triangular non-singular, then A−1 is upper triangular, too. A matrix is elementary if it is obtained from the identity matrix by a single legal row operation. Lemma Let e be an elementary row operation (swaps, row addition, etc), and let E be the elementary matrix that results from applying e to the m × m identity I . Then for every m × n matrix A, e(A) = E (A). MATH 22A: LINEAR ALGEBRA Chapter 2 The matrices we use are special: An n × n matrix A is upper triangular if every entry aij with j > i is zero. An n × n matrix A is lower triangular if every entry aij with j < i is zero. Proposition If A, B are upper triangular matrices, then their product is upper triangular. Same for lower triangular! Proposition If A is upper (lower) triangular non-singular, then A−1 is upper triangular, too. A matrix is elementary if it is obtained from the identity matrix by a single legal row operation. Lemma Let e be an elementary row operation (swaps, row addition, etc), and let E be the elementary matrix that results from applying e to the m × m identity I . Then for every m × n matrix A, e(A) = E (A). Lemma Every elementary matrix has an inverse and that inverse is also an elementary matrix! MATH 22A: LINEAR ALGEBRA Chapter 2 Matrix factorization Theorem If A, B are m × n matrices. Then B is obtained from A via elementary row operations if and only if B = Ek Ek−1 · · · E2 E1 A, where the Ei are elementary matrices. MATH 22A: LINEAR ALGEBRA Chapter 2 Matrix factorization Theorem If A, B are m × n matrices. Then B is obtained from A via elementary row operations if and only if B = Ek Ek−1 · · · E2 E1 A, where the Ei are elementary matrices. Theorem Every matrix A can be written as Ek Ek−1 · · · E2 E1 A = R where R is in row echelon form. MATH 22A: LINEAR ALGEBRA Chapter 2 Matrix factorization Theorem If A, B are m × n matrices. Then B is obtained from A via elementary row operations if and only if B = Ek Ek−1 · · · E2 E1 A, where the Ei are elementary matrices. Theorem Every matrix A can be written as Ek Ek−1 · · · E2 E1 A = R where R is in row echelon form. Corollary Suppose that A is a square n × n invertible matrix, suppose that A can be put in row echelon form WITHOUT SWAPS OF ROWS. Call the upper triangular matrix U that has the pivots on its diagonal. Then A can be written as the product of LU where L is a lower triangular matrix with 1’s on the diagonal. MATH 22A: LINEAR ALGEBRA Chapter 2 Matrix factorization Theorem If A, B are m × n matrices. Then B is obtained from A via elementary row operations if and only if B = Ek Ek−1 · · · E2 E1 A, where the Ei are elementary matrices. Theorem Every matrix A can be written as Ek Ek−1 · · · E2 E1 A = R where R is in row echelon form. Corollary Suppose that A is a square n × n invertible matrix, suppose that A can be put in row echelon form WITHOUT SWAPS OF ROWS. Call the upper triangular matrix U that has the pivots on its diagonal. Then A can be written as the product of LU where L is a lower triangular matrix with 1’s on the diagonal. In that case, when A non-singular n × n and A = LU we can solve the system Ax = b as follows: 1 2 Solve Lc = b, solve Ux = c, MATH 22A: LINEAR ALGEBRA Chapter 2 Example 6 −2 −4 4 3 −3 −6 1 Consider A = −12 8 21 −8 −6 0 −10 7 MATH 22A: LINEAR ALGEBRA Chapter 2 Example −2 6 −4 4 3 −3 −6 1 Consider A = −12 8 21 −8 −6 0 −10 7 We say that we can decompose A = LU where 1 0 0 0 1/2 1 0 0 L= −2 −2 1 0 −1 1 −2 1 6 −2 −4 4 0 −2 −4 −1 U= 0 0 5 −2 0 0 0 8 MATH 22A: LINEAR ALGEBRA Chapter 2 Example −2 6 −4 4 3 −3 −6 1 Consider A = −12 8 21 −8 −6 0 −10 7 We say that we can decompose A = LU where 1 0 0 0 6 −2 −4 4 1/2 1 0 −2 −4 −1 0 0 L= U= −2 −2 1 0 0 0 5 −2 −1 1 −2 1 0 0 0 8 2 −4 We can solve for b = 8 . −43 MATH 22A: LINEAR ALGEBRA Chapter 2 For solving Ax = b, we break it in two steps: First Lz = b, then Ux = z. MATH 22A: LINEAR ALGEBRA Chapter 2 For solving Ax = b, we break it in two steps: First Lz = b, then Ux = z. 1 0 0 0 2 z1 1/2 1 0 0 z2 = −4 −2 −2 1 0 z3 8 −43 z4 −1 1 −2 1 MATH 22A: LINEAR ALGEBRA Chapter 2 For solving Ax = b, we break it in two steps: First Lz = b, then Ux = z. 1 0 0 0 2 z1 1/2 1 0 0 z2 = −4 −2 −2 1 0 z3 8 −43 z4 −1 1 −2 1 z1 = 2 z1 2 + z2 = −4 −2 z1 − 2 z2 + z3 = 8 −z1 + z2 − 2 z3 + z4 = −43 From here z1 = 2, z2 = −5, z3 = 2, z4 = −32. MATH 22A: LINEAR ALGEBRA Chapter 2 For solving Ax = b, we break it in two steps: First Lz = b, then Ux = z. 1 0 0 0 2 z1 1/2 1 0 0 z2 = −4 −2 −2 1 0 z3 8 −43 z4 −1 1 −2 1 z1 = 2 z1 2 + z2 = −4 −2 z1 − 2 z2 + z3 = 8 −z1 + z2 − 2 z3 + z4 = −43 From here z1 = 2, z2 = −5, z3 = 2, z4 = −32. Next we solve Ux = z. MATH 22A: LINEAR ALGEBRA Chapter 2 6 −2 −4 4 2 x1 0 −2 −4 −1 x2 −5 = 2 x3 0 0 5 −2 x4 −32 0 0 0 8 MATH 22A: LINEAR ALGEBRA Chapter 2 6 −2 −4 4 2 x1 0 −2 −4 −1 x2 −5 = 2 x3 0 0 5 −2 x4 −32 0 0 0 8 This gives the triangular system: 8 x4 = −32 5 x3 − 2 x4 = 2 −2 x2 − 4 x3 − x4 = −5 6 x1 − 2 x2 − 4 x3 + 4 x4 = 2 MATH 22A: LINEAR ALGEBRA Chapter 2 6 −2 −4 4 2 x1 0 −2 −4 −1 x2 −5 = 2 x3 0 0 5 −2 x4 −32 0 0 0 8 This gives the triangular system: 8 x4 = −32 5 x3 − 2 x4 = 2 −2 x2 − 4 x3 − x4 = −5 6 x1 − 2 x2 − 4 x3 + 4 x4 = 2 Solution is x1 = 9/2, x2 = 69/10, x3 = −6/5, x4 = −4 MATH 22A: LINEAR ALGEBRA Chapter 2 6 −2 −4 4 2 x1 0 −2 −4 −1 x2 −5 = 2 x3 0 0 5 −2 x4 −32 0 0 0 8 This gives the triangular system: 8 x4 = −32 5 x3 − 2 x4 = 2 −2 x2 − 4 x3 − x4 = −5 6 x1 − 2 x2 − 4 x3 + 4 x4 = 2 Solution is x1 = 9/2, x2 = 69/10, x3 = −6/5, x4 = −4 But how did you get U, L? MATH 22A: LINEAR ALGEBRA Chapter 2 6 −2 −4 4 2 x1 0 −2 −4 −1 x2 −5 = 2 x3 0 0 5 −2 x4 −32 0 0 0 8 This gives the triangular system: 8 x4 = −32 5 x3 − 2 x4 = 2 −2 x2 − 4 x3 − x4 = −5 6 x1 − 2 x2 − 4 x3 + 4 x4 = 2 Solution is x1 = 9/2, x2 = 69/10, x3 = −6/5, x4 = −4 But how did you get U, L? U is just what you get at the end of ROW REDUCTION as the ROW ECHELON FORM. MATH 22A: LINEAR ALGEBRA Chapter 2 6 −2 −4 4 2 x1 0 −2 −4 −1 x2 −5 = 2 x3 0 0 5 −2 x4 −32 0 0 0 8 This gives the triangular system: 8 x4 = −32 5 x3 − 2 x4 = 2 −2 x2 − 4 x3 − x4 = −5 6 x1 − 2 x2 − 4 x3 + 4 x4 = 2 Solution is x1 = 9/2, x2 = 69/10, x3 = −6/5, x4 = −4 But how did you get U, L? U is just what you get at the end of ROW REDUCTION as the ROW ECHELON FORM. To compute L we need to compute the elementary matrices! MATH 22A: LINEAR ALGEBRA Chapter 2 6 −2 −4 4 2 x1 0 −2 −4 −1 x2 −5 = 2 x3 0 0 5 −2 x4 −32 0 0 0 8 This gives the triangular system: 8 x4 = −32 5 x3 − 2 x4 = 2 −2 x2 − 4 x3 − x4 = −5 6 x1 − 2 x2 − 4 x3 + 4 x4 = 2 Solution is x1 = 9/2, x2 = 69/10, x3 = −6/5, x4 = −4 But how did you get U, L? U is just what you get at the end of ROW REDUCTION as the ROW ECHELON FORM. To compute L we need to compute the elementary matrices! Multiplied together they give L−1 , so we need to multiply their inverses to get L. MATH 22A: LINEAR ALGEBRA Chapter 2 We proceed to select pivots and then “ZERO OUT” below each one of them. MATH 22A: LINEAR ALGEBRA Chapter 2 We proceed to select pivots and then “ZERO OUT” below each one of them. 6 −2 −4 4 3 −3 −6 1 A= −12 8 21 −8 −6 0 −10 7 MATH 22A: LINEAR ALGEBRA Chapter 2 We proceed to select pivots and then “ZERO OUT” below each one of them. 6 −2 −4 4 3 −3 −6 1 A= −12 8 21 −8 −6 We need to 1 1/2 L= −2 −1 0 −10 7 figure out how to get 0 0 0 1 0 0 −2 1 0 1 −2 1 MATH 22A: LINEAR ALGEBRA Chapter 2 We proceed to select pivots and then “ZERO OUT” below each one of them. 6 −2 −4 4 3 −3 −6 1 A= −12 8 21 −8 −6 0 −10 7 We need to figure out how to get 1 0 0 0 1/2 1 0 0 L= −2 −2 1 0 −1 1 −2 1 STEP 1: Compute all elementary (elimination) matrices in order (going down). STEP 2: Find their inverses. STEP 3: Multiply the inverses to get L. MATH 22A: LINEAR ALGEBRA Chapter 2 TRANSPOSES Given an p × q matrix A, its transpose AT is a q × p matrix whose rows are the columns of A and vice versa. MATH 22A: LINEAR ALGEBRA Chapter 2 TRANSPOSES Given an p × q matrix A, its transpose AT is a q × p matrix whose rows are the columns of A and vice versa. 95 11 −49 −47 40 −81 91 −51 77 68 95 −10 31 1 1 95 −81 −51 11 91 −49 68 −47 −10 40 31 77 95 1 1 MATH 22A: LINEAR ALGEBRA Chapter 2 TRANSPOSES Given an p × q matrix A, its transpose AT is a q × p matrix whose rows are the columns of A and vice versa. 95 11 −49 −47 40 −81 91 −51 77 68 95 −10 31 1 1 95 −81 −51 11 91 −49 68 −47 −10 40 31 77 95 1 1 The transpose of a matrix is very useful: 1 2 3 (A + B)T = AT + B T (AB)T = B T AT (A−1 )T = (AT )−1 MATH 22A: LINEAR ALGEBRA Chapter 2 It is very rare that it happens, but if A = AT then we say A is symmetric. This means aji = aij . MATH 22A: LINEAR ALGEBRA Chapter 2 It is very rare that it happens, but if A = AT then we say A is symmetric. This means aji = aij . The identity matrix is symmetric! MATH 22A: LINEAR ALGEBRA Chapter 2 It is very rare that it happens, but if A = AT then we say A is symmetric. This means aji = aij . The identity matrix is symmetric! NOTE: If R is any matrix R T R and RR T are symmetric! This is going to be super useful later! For symmetric matrices we can do row reduction faster. MATH 22A: LINEAR ALGEBRA Chapter 2 It is very rare that it happens, but if A = AT then we say A is symmetric. This means aji = aij . The identity matrix is symmetric! NOTE: If R is any matrix R T R and RR T are symmetric! This is going to be super useful later! For symmetric matrices we can do row reduction faster. More importantly if we do the row reduction of a symmetric matrix A = LU , L, U are always not symmetric, but we can decompose U = DLT 1 2 3 1 0 0 1 2 3 2 7 0 = 2 1 0 0 3 −6 3 0 −2 3 −2 1 0 0 −23 MATH 22A: LINEAR ALGEBRA Chapter 2 We rewrite as 1 0 0 1 2 3 2 1 0 0 3 −6 = 0 0 −23 3 −2 1 MATH 22A: LINEAR ALGEBRA Chapter 2 We rewrite as 1 0 0 1 2 3 2 1 0 0 3 −6 = 0 0 −23 3 −2 1 We can then divide into two matrices 1 0 2 1 3 −2 out to leave 1’s on the diagonal and break U 0 1 0 0 1 2 3 0 0 0 3 0 1 −2 1 0 0 −23 0 0 1 MATH 22A: LINEAR ALGEBRA Chapter 2 We rewrite as 1 0 0 1 2 3 2 1 0 0 3 −6 = 0 0 −23 3 −2 1 We can then divide into two matrices 1 0 2 1 3 −2 out to leave 1’s on the diagonal and break U 0 1 0 0 1 2 3 0 0 0 3 0 1 −2 1 0 0 −23 0 0 1 We obtain a super nice form LDLT where D is a diagonal matrix, L is lower diagonal matrix. MATH 22A: LINEAR ALGEBRA Chapter 2 PERMUTATION MATRICES To do the swaps we need the most beautiful matrices: permutation matrices MATH 22A: LINEAR ALGEBRA Chapter 2 PERMUTATION MATRICES To do the swaps we need the most beautiful matrices: permutation matrices A permutation matrix is one that has the rows of the identity matrix in any possible order. MATH 22A: LINEAR ALGEBRA Chapter 2 PERMUTATION MATRICES To do the swaps we need the most beautiful matrices: permutation matrices A permutation matrix is one that has the rows of the identity matrix in any possible order. The inverse of a permutation matrix P is another permutation matrix, in fact P −1 = P T . Why? MATH 22A: LINEAR ALGEBRA Chapter 2 PERMUTATION MATRICES To do the swaps we need the most beautiful matrices: permutation matrices A permutation matrix is one that has the rows of the identity matrix in any possible order. The inverse of a permutation matrix P is another permutation matrix, in fact P −1 = P T . Why? HOW many n × n permutation matrices are there? Why? MATH 22A: LINEAR ALGEBRA Chapter 2 PERMUTATION MATRICES To do the swaps we need the most beautiful matrices: permutation matrices A permutation matrix is one that has the rows of the identity matrix in any possible order. The inverse of a permutation matrix P is another permutation matrix, in fact P −1 = P T . Why? HOW many n × n permutation matrices are there? Why? Sometimes to get to row echelon form we need to use permutations to swap rows! MATH 22A: LINEAR ALGEBRA Chapter 2 PERMUTATION MATRICES To do the swaps we need the most beautiful matrices: permutation matrices A permutation matrix is one that has the rows of the identity matrix in any possible order. The inverse of a permutation matrix P is another permutation matrix, in fact P −1 = P T . Why? HOW many n × n permutation matrices are there? Why? Sometimes to get to row echelon form we need to use permutations to swap rows! In that case A = LU does not work! So in between we may need to swap. MATH 22A: LINEAR ALGEBRA Chapter 2 PA = LU decomposition One way to still get a nice decomposition: collect all the permutation matrices. We can do all the row exchanges in advance. Say 0 1 1 −1 1 0 3 −4 A= 0 0 0 2 0 1 0 1 MATH 22A: LINEAR ALGEBRA Chapter 2 PA = LU decomposition One way to still get a nice decomposition: collect all the permutation matrices. We can do all the row exchanges in advance. Say 0 1 1 −1 1 0 3 −4 A= 0 0 0 2 0 1 0 1 Multiply A by a permutation P, and then do the LU decomposition: 1 0 3 −4 1 0 0 0 1 0 3 −4 0 1 1 −1 PA = = 0 0 0 1 0 0 0 2 0 1 0 1 0 0 1 0 0 1 0MATH122A: LINEAR ALGEBRA 0 0 Chapter 0 22 0 1 0 0 0 1 1 −1 The LU decomposition 0 1 PA = 0 of PA equals 1 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 1 1 −1 1 0 3 −4 0 0 0 2 0 1 0 1 1 0 3 −4 0 1 0 0 0 1 1 −1 LU = 0 1 1 0 0 0 −1 2 0 0 0 1 0 0 0 2 MATH 22A: LINEAR ALGEBRA Chapter 2 The LU decomposition 0 1 PA = 0 of PA equals 1 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 1 1 −1 1 0 3 −4 0 0 0 2 0 1 0 1 1 0 3 −4 0 1 0 0 0 1 1 −1 LU = 0 1 1 0 0 0 −1 2 0 0 0 1 0 0 0 2 Theorem If A is an invertible matrix, there is always a permutation P such that PA = LU, with L, U being lower and upper triangular matrices. MATH 22A: LINEAR ALGEBRA Chapter 2
© Copyright 2024