Linear Equations & Systems of Linear Equations PDF

Week 1 Session Content: Linear Equations & System of Linear Equations: Linear Equation: A linear equation in the variables x1, x2, …, xn is an equation that can be written as a1x1 + a2x2 + … + anxn = b Where, a1, a2, …, an -> Coefficients of a linear equation. X1,...

Week 1 Session Content: Linear Equations & System of Linear Equations: Linear Equation: A linear equation in the variables x1, x2, …, xn is an equation that can be written as a1x1 + a2x2 + … + anxn = b Where, a1, a2, …, an -> Coefficients of a linear equation. X1, x2, …, xn -> Variables. b -> Constant. Example: 1. 2x + 3y = 5 2. 3x1 + 10x2 = 100 3. 2x1 + 3x2 + (2 + 8i) x3 = 5 + 10i is a linear equation with more than two variables. What can form Non-Linear Equations? 2z2 + 3z + 10 = 0 2xy + 3z + 5 = 0 Applications of Linear equations: 1. One day Mr. Jones has $25 in his wallet. He wants to buy fruits. He went to the grocery store. He found that there were only three fruits available: Banana ($2.25/ Kg), Kiwi ($3.5/ Kg), Orange ($0.75/ Kg). How much weight of each of these fruits Mr. it as a Linear equation. Sol: Total amount Mr. Jones has = $25 Let, The quantity of Bananas, Kiwis, and Oranges Mr. Jones has purchased be = x, y, & z respectively.  ➔ The total amount spent on Bananas = 2.25 x ➔ The total amount spent on Kiwis = 3.5 y ➔ The total amount spent on Oranges = 0.75 z The scenario can be expressed as 2.25 x + 3.5 y + 0.75 z = 25 Apart from solving day to day problems like this, Linear Equations also find diverse applications in: ➔ Business & Economics (supply & demand analysis, profit & loss analysis, etc…) ➔ Engineering & Physics (Electrical circuits, structural analysis, Force & motion, etc…) ➔ Computer Science (Algorithm efficiency, ML, Graphics & Game development) ➔ Medicine & Biology (Medical dosage calculations, population dynamics, etc,..) System of Linear Equations: The system of linear equations is also known as a linear system. It is the collection of one or more linear equations involving the same set of variables. a11 x1 + a12 x2 + … + a1n xn = b1 a21 x1 + a22 x2 + … + a2n xn = b2 …. …. am1 x1 + am2 x2 + … + amn xn = bm Here, there are m linear equations and n variables. Example: Two variables & two equations 2x + 3y = 7 7x – 3y = -7 Example problem: A museum has opened in the city. They charge $20 per adult and $10 per child. The museum sold in total 210 tickets on the first day, and they earned $2800. Pose this as a linear system of equations. Sol: Cost of ticket per adult = $20 Cost of ticket per child = $10 Total tickets sold = 210 Let, the number of tickets sold for adults and children be x, y respectively. ➔ The total tickets sold on day 1 can be expressed as: x + y = 210 ➔ The amount earned on day 1 can be expressed as: 20x + 10 y = 2800 Geometric view of a system of linear equations with two variables: If we consider the equation of a straight line passing through two points (x1, y1) and (x2, y2) (𝑥 – 𝑥1) (𝑦 – 𝑦1) = 𝑥2−𝑥1 𝑦2−𝑦1 𝑦2 – 𝑦1 The slope of this straight line is given by m = 𝑥2−𝑥1 If we rewrite the equation of the straight line passing through two points, then we can write it as: 𝑦2 – 𝑦1 (y – y1) = (x – x1) 𝑥2−𝑥1 (y – y1) = m (x – x1) The standard form of straight line is: ax + by + c = 0 This straight line represents a linear equation. System of Linear Equations: 1. Consider the system of two linear equations: a11 x + a12 y = b1 a21 x + a22 y = b2 This system represents a system of two straight lines. 2. If we consider a system of linear equation with three variables: a11 x + a12 y + a13 z = b1 This system represents a plane upon the x, y, and z axes respectively. Matrix Notation: If we consider a system of Linear equations containing ‘m’ equations and ‘n’ variables, a11 x1 + a12 x2 + … + a1n xn = b1 a21 x1 + a22 x2 + … + a2n xn = b2 …. …. am1 x1 + am2 x2 + … + amn xn = bm we can represent it in the form of a matrix ➔ It is a compact way to record a system of linear equations. ➔ A rectangular array of real or complex numbers. ➔ Arranged in the form of rows and columns Dimension of the matrix: This matrix can be thought of as the m x n matrix where m represents the number of rows and n represents the number of columns present in the matrix and m x n is called as the order of the matrix. Entries/ Elements of the matrix: The entries in the matrix are called as the elements of the matrix and they are denoted by aij where, i represents the position of the row and j represents the position of the column of the element aij. Coefficient matrix: If we consider the system of linear equations: a11 x1 + a12 x2 + … + a1n xn = b1 a21 x1 + a22 x2 + … + a2n xn = b2 …. …. am1 x1 + am2 x2 + … + amn xn = bm Here, the values of a11, a12, …, amn are the values of the coefficients present in the linear equations. If we represent them in the form of a matrix, then the resultant matrix is called as the coefficient matrix. 𝑎11 𝑎12 … 𝑎1𝑛 𝑎21 𝑎22 … 𝑎2𝑛 A=[ ]. … … … 𝑎𝑚1 𝑎𝑚2 … 𝑎𝑚𝑛 Example: If we consider the following system of linear equations: 2x + 3y = 5 3x + 10 y = 20 5x + 4y = -10 Then the resulting coefficient matrix of the system would be 2 3 A = [3 10] 5 4 Augmented Matrix: An Augmented matrix is obtained by adding a column containing the constant terms from the right sides of the equations to the coefficient matrix. 𝑎11 𝑎12 … 𝑎1𝑛 𝑎21 𝑎22 … 𝑎2𝑛 A=[ ]. … … … 𝑎𝑚1 𝑎𝑚2 … 𝑎𝑚𝑛 Here, the order of this matrix is m x (n + 1) Example: If we consider the following system of linear equations: 2x + 3y = 5 3x + 10 y = 20 5x + 4y = -10 Then the augmented matrix would be 2 3 5 [3 10 20 ] 5 4 −10 Matrix Notation & Vector Notation: Vector Notation: If one of the dimensions of a matrix is ‘one’. Then such a matrix is called as a vector. ➔ If the matrix has only one row, then it is called as a row vector. ➔ If the matrix has only one column, then it is called as a column vector. Example: ➔ A = [1 2 3] is called as a row vector as it has only one row. 2 ➔ A = is called as a column vector as it has only one column. 5 Matrix notation of system of Linear equations: If we consider the system of linear equations: a11 x1 + a12 x2 + … + a1n xn = b1 a21 x1 + a22 x2 + … + a2n xn = b2 …. …. am1 x1 + am2 x2 + … + amn xn = bm The matrix notation of Linear equations is expressed as AX = B Where, A is the coefficient matrix, X is the column vector containing the variables, B is the column vector containing the Constants, 𝑎11 𝑎12 … 𝑎1𝑛 𝑥1 𝑏1 𝑎21 𝑎22 … 𝑎2𝑛 𝑥2 𝑏2 A=[ ] X=[ ] B=[ ]. … … … … … 𝑎𝑚1 𝑎𝑚2 … 𝑎𝑚𝑛 𝑥𝑚 𝑏𝑚 Example: If we consider the following system of linear equations: 2x + 3y = 5 3x + 10 y = 20 5x + 4y = -10 2 3 𝑥 5 A = [3 10] X = [𝑦] B = [ 20 ] 5 4 −10 Types of Matrices: 1. Square Matrix: A matrix with the same number of rows and columns. Example: 2. Rectangular Matrix: A matrix with a different number of rows and columns. Example: 3. Row Matrix/ Row Vector: A matrix with only one row. Example: 4. Column Matrix/ Column Vector: A matrix with only one column. Example: 5. Zero Matrix (Null Matrix): A matrix in which all elements are zero. Example: Diagonal of a matrix : The diagonal of a matrix, specifically the principal diagonal (or main diagonal), consists of the elements that extend from the top left corner to the bottom right corner of a square matrix. In a square matrix of order n, A = [aij]nxn the principal diagonal elements are those for which the row index i is equal to the column index j, i.e., a11, a22, …, ann. Trace Of a Matrix : The Trace of a matrix is defined as the sum of all the principal diagonal elements of a matrix. 6. Diagonal Matrix: A square matrix in which all the elements outside the principal diagonal are zero. Example: 7. Scalar Matrix: A diagonal matrix in which all the elements of the principal diagonal are equal. Example: 8. Identity Matrix (Unit Matrix): A square matrix in which all the elements of the principal diagonal are 1 and all other elements are 0. Example:  9. Upper Triangular Matrix: A square matrix in which all the elements below the principal diagonal are zero. Example: 10. Lower Triangular Matrix: A square matrix in which all the elements above the principal diagonal are zero. Example: Transpose of a Matrix : The Transpose of a matrix is a mathematical operation that involves flipping the rows and columns of the original matrix. It is denoted by the symbol AT or A/ Properties of Transpose of a matrix : ➔ Transpose of a Transpose: (AT)T.= A ➔ Transpose of a Sum: (A+B)T = AT + BT ➔ Transpose of a Product: (AB)T = BT. AT ➔ Transpose of a Scalar Multiple: (kA)T=kAT 11. Symmetric Matrix: A square matrix that is equal to its transpose. (AT = A) Example: Note: ➔ If A is a square matrix, then A + AT is the Symmetric Matrix. ➔ If A is a Symmetric Matrix, the (i,j)th element of A is same as the (j,i)th element of A. Example: Here we can observe that a21 = a12 = 2, a13 = a31 = 0, a32 = a23 = -1. 12. Skew-Symmetric Matrix: A square matrix that is equal to the negative of its transpose. (AT = - A) Example: Note: ➔ If A is a square matrix, then A – AT is the Skew – Symmetric Matrix. ➔ If A is a Skew-Symmetric Matrix, the (i,j)th element of A is the negative of the (j,i)th element of A. ➔ Example: Fun fact: Every matrix A can be expressed as a sum of Symmetric and Skew Symmetric matrices by the following method: A = ½ (A + AT) + ½ (A – AT); Where, A + AT is the Symmetric component and A – AT is the Skew-Symmetric component. Equality Of Matrices: Matrices A and B are said to be equal if A and B are of the same order and the corresponding elements of A and B are the same. Example: Addition of Matrices: Let A and B be matrices of the same order. Then the sum of A and B, denoted by A + B, is defined as the matrix of the same order in which each element is the sum of the corresponding elements of A and B. C = A + B => cij = aij + bij Example: Properties for Sum of Matrices: 1. Addition of matrices is commutative. i.e., A + B = B + A 2. Addition of matrices obeys Associative Property i.e., A + (B + C) = (A + B) +C 3. Additive identity: If A is a m × n matrix and O is the (m × n) null matrix, A + O = O + A = A. 4. Additive inverse: If A is an (m × n) matrix then there is a unique m × n matrix B such that A + B = B + A = O, O being the m × n null matrix. Note: The sum of any two matrices A and B is only defined when they are of the same order Scalar multiplication of Matrix: Let A be a matrix of order m × n and k be a scalar (i.e., real or complex number). Then the m × n matrix obtained by multiplying each element of A by k is called a scalar multiple of A and is denoted by k A. If A = [aij]mxn, then kA = [kaij]mxn Example: Properties of scalar multiplication of Matrices: For any scalar values k, m;  1. Distributive Property over Matrix Addition: k(A+B) = kA + kB 2. Distributive Property over Scalar Addition: (k + m) A = kA + mA 3. Associative Property of Scalar Multiplication: k(mA) = (km)A 4. Multiplicative Identity Property: 1A = A Multiplication of Matrices: Multiplication of Matrix and a Vector: Viewing a Matrix as a Column vector: Any coefficient matrix of the form 𝑎11 𝑎12 … 𝑎1𝑛 𝑎21 𝑎22 … 𝑎2𝑛 A=[ ] can be viewed in the following ways:. … … … 𝑎𝑚1 𝑎𝑚2 … 𝑎𝑚𝑛 1. Row vector consisting Column Vectors: If we try to rewrite the way in which the elements are expressed in A, such that all the columns are represented by a unique element and if we collect all these unique elements and arrange in the form of a row vector, it would look like the following: A = [ai1 ai2 … ain ] where i = 1, 2, …, m 2. Column vector consisting Row vectors: If we try to rewrite the elements in A, such that all the rows are represented by a unique element for each row, and if we collect all these unique elements and represent them in the form of a column vector, then it would look like the following: 𝑎1𝑖 𝑎2𝑖 A = 𝑎3𝑖 where i = 1, 2, …, n … [𝑎𝑚𝑖 ] Multiplying a row vector and a column vector together: 𝑏1 𝑏2 [a1 a2 … am] x [ ] = a1b1 + a2b2 + … + ambm … 𝑏𝑚 here, the order of the row vector is 1 x m and the order of the column vector is m x 1. Note: We perform this operation only when the number of columns of the first matrix is equal to the number of rows of the second matrix. Example: Multiply the following: 4 [1 2 3] and 6 Pre multiply a column vector with a matrix: Let A be a matrix of the size m x n Let V be a column vector of size n x 1 Then, R = AV is a vector of size m x 1 Example: Compute the following: 1 2 3 1 [−2 1 2] x −3 −2 1 3 Multiplication of two matrices: Consider two matrices: A of size m x n B of size n x p Then C = A x B is a matrix of the size m x p Note: The no. of columns (n) on the left side matrix (A) = no. of rows (n) on the right side matrix (B). 𝑎11 𝑎12 … 𝑎1𝑛 𝑏11 𝑏12 … 𝑏1𝑝 𝑎21 𝑎22 … 𝑎2𝑛 𝑏21 𝑏22 … 𝑏2𝑝 A=[ ] B=[ ]. … … …. … … … 𝑎𝑚1 𝑎𝑚2 … 𝑎𝑚𝑛 𝑏𝑛1 𝑏𝑛2 … 𝑏𝑛𝑝 𝑎11 𝑎12 … 𝑎1𝑛 𝑎21 𝑎22 … 𝑎2𝑛 [𝑏1 ⇨ = [ ] 𝑏2 … 𝑏𝑝]. … … … 𝑎𝑚1 𝑎𝑚2 … 𝑎𝑚𝑛 ⇨ AB = [𝐴𝑏1 𝐴𝑏2 … 𝐴𝑏𝑝 ] Example: Multiply the following matrices: 3 −1 2 −2 −1 A=[ ] B=[ ] 5 2 1 3 4 Row-column rule for computing AB If the product AB is defined, then the entry in row i and column j of AB is the sum of the products of the corresponding entries from row i of A and column j of B. (AB)ij = ai1b1j + ai2b2j + … + ainbnj Example: Find the entry in row 1 and column 3 of AB 3 −1 2 −2 −1 A=[ ] B=[ ] 5 2 1 3 4 Properties of multiplication of Matrices: 1. Associative Law: For any three matrices A, B and C, we have (AB)C = A (BC) 2. Distributive Law: For any three matrices A, B and C, we have - A(B + C) = AB + AC (Left Distributive Law) - (A + B)C = AC + BC (Right Distributive Law) 3. Existence of multiplicative identity: IA = AI = A. 4. For any Scalar k: k(AB) = (kA)B = A(kB) Determinants: For every square matrix A, there is a number associated called as the determinant of A denoted by |A| This number will help in finding the solution of a system of linear equation or characterize the solution. How to find the determinant? The determinant of 1 x 1 matrix is defined as: |a11| = a11 The determinant of a 2 x 2 matrix is defined as Example: Find the determinant of the matrix: 𝑆𝑖𝑛𝜃 −𝐶𝑜𝑠𝜃 [ ] 𝐶𝑜𝑠𝜃 𝑆𝑖𝑛𝜃 Minor and Cofactor of an element: Let A be a square matrix, the minor Mij of the element aij is defined as the determinant of the matrix obtained from A by deleting the row i and column j. The cofactor of aij is defined as Cij = (-1)i+j Mij Example: Determine the minor and cofactor of the element a12 of the following matrix: 1 0 2 [0 2 1] 2 1 0 Definition of Determinant: The determinant of a square matrix is the sum of fthe products of the elements of the first row and their cofactors.  If A is 3 x 3 |A| = a₁₁C₁₁ + a₁₂C₁₂ + a₁₃C₁₃ If A is 4 x 4 |A| = a₁₁C₁₁ + a₁₂C₁₂ + a₁₃C₁₃ + a₁₄C₁₄ : : If A is n x n |A| = a₁₁C₁₁ + a₁₂C₁₂ + a₁₃C₁₃ +... + a₁ₙC₁ₙ Example: Evaluate the determinant of 1 2 −1 A = [2 1 0 ] 1 1 4 Broader definition of determinant: The determinant of a square matrix is the sum of the products of the elements of am row or column and their co-factors. Ith row expansion: |A| = ai1Ci1 + ai2Ci2 + … + ainCin Jth column expansion |A| = a1jC1j + a2jC2j + … + anjCnj Example: Find the determinant of the following matrix using the 2nd column expansion. 3 0 2 A = [4 0 5 ] 2 1 −4 Determinants and its properties: Property 1: If the rows and columns of a determinant are interchanged, then the value of the determinant remains unchanged. |A| = |AT| Explanation: 𝑎1 𝑎2 𝑎3 Let D = |𝑏1 𝑏2 𝑏3| 𝑐1 𝑐2 𝑐3 Expanding based on the first row D = a1(b2c3 – b3c2) – a2(b1c3 – b3c1) + a3(b1c2 – b2c1) Interchanging the rows and columns of D. 𝑎1 𝑏1 𝑐1 T D = |𝑎2 𝑏2 𝑐2| 𝑎3 𝑏3 𝑐3 Expanding based on the first column: DT = a1(b2c3 – b3c2) – a2(b1c3 – b3c1) + a3(b1c2 – b2c1) =D Property – 2: If two rows/ columns of a matrix are interchanged to produce another matrix B, then |B| = - |A| Explanation: 𝑎1 𝑎2 𝑎3 Let |A| = |𝑏1 𝑏2 𝑏3| 𝑐1 𝑐2 𝑐3 Expanding based on the first row, |A| = a1(b2c3 – b3c2) – a2(b1c3 – b3c1) + a3(b1c2 – b2c1) Interchanging the first row and second row. 𝑏1 𝑏2 𝑏3 |B| = |𝑎1 𝑎2 𝑎3| 𝑐1 𝑐2 𝑐3 Expanding based on the second row, |B| = -a1(b2c3 – b3c2) + a2(b1c3 – b3c1) – a3(b1c2 – b2c1) = - |A| Example: 2 1 1 1 1 2 Consider | A | = | 0 4 2| and | B | = |2 4 0 | here, we attain B by interchanging −2 0 3 3 0 −2 the column 1 and 3 from A. Verify if the property 2 obeys? Property – 3: If any two rows/ columns of a determinant are identical, then their corresponding elements are equal, then the value of the determinant is zero. Reasoning: This property holds because if we interchange the identical rows of |A|, the determinant remains unchanged. According to property 2, the value of the determinant after the exchange will be of the same magnitude but a different sign. Example: 2 1 2 |A|=| 0 4 0 | −2 0 −2 Verify property 3? Property – 4: If each element of a row/ column of a determinant is multiplied by a constant k, then its value gets multiplied by k. Explanation: 𝑎1 𝑎2 𝑎3 Let D = |𝑏1 𝑏2 𝑏3| 𝑐1 𝑐2 𝑐3 Expanding based on the first row, D = a1(b2c3 – b3c2) – a2(b1c3 – b3c1) + a3(b1c2 – b2c1) Let, 𝑘𝑎1 𝑘𝑎2 𝑘𝑎3 D’ = | 𝑏1 𝑏2 𝑏3 | 𝑐1 𝑐2 𝑐3 Expanding based on the firs row, D’ = ka1(b2c3 – b3c2) – ka2(b1c3 – b3c1) + ka3(b1c2 – b2c1) = kD Property – 5: If some or all elements of a row/ column of a determinant are expressed as sum of two or more terms, then the determinant can be expressed as sum of two or more determinants. Example: Find the value of 𝑎1 𝑎2 𝑎3 |A| = |𝑎1 + 𝑘𝑐1 𝑎2 + 𝑘𝑐2 𝑎3 + 𝑘𝑐3| 𝑐1 𝑐2 𝑐3 Here, 𝑎1 𝑎2 𝑎3 𝑎1 𝑎2 𝑎3 |A| = |𝑏1 𝑏2 𝑏3| + |𝑘𝑐1 𝑘𝑐2 𝑘𝑐3| [By property 5] 𝑐1 𝑐2 𝑐3 𝑐1 𝑐2 𝑐3 𝑎1 𝑎2 𝑎3 𝑎1 𝑎2 𝑎3 |𝑏1 𝑏2 𝑏3| + k | 𝑐1 𝑐2 𝑐3 | 𝑐1 𝑐2 𝑐3 𝑐1 𝑐2 𝑐3 ⇨ 0 + 0 = 0 [Property 3] Property 6: Let A be a square matrix If a multiple of one row/ column of A is added to another row/ column to produce a matrix B then |B| = |A| Explanation: Let  𝑎1 𝑎2 𝑎3 |A| = |𝑏1 𝑏2 𝑏3| 𝑐1 𝑐2 𝑐3 If we apply the row operation R1 -> R1 + k R3 𝑎1 + 𝑘𝑐1 𝑎2 + 𝑘𝑐2 𝑎3 + 𝑘𝑐3 We get |B| = | 𝑏1 𝑏2 𝑏3 | 𝑐1 𝑐2 𝑐3 𝑎1 𝑎2 𝑎3 𝑐1 𝑐2 𝑐3 = |𝑏1 𝑏2 𝑏3| + k |𝑏1 𝑏2 𝑏3| [by properties 5 and 4] 𝑐1 𝑐2 𝑐3 𝑐1 𝑐2 𝑐3 𝑎1 𝑎2 𝑎3 = |𝑏1 𝑏2 𝑏3| + 0 [by property 3] 𝑐1 𝑐2 𝑐3 = |A| Property – 7: If A and B are two n x n matrices, then |AB| = |A| |B| 5 −3 2 0 Example: Verify the property – 7 for A = [ ] and B = [ ] 0 −5 1 8 Note: If A and B are two n x n matrices, then | A + B | is not equals to |A| + |B|  Week 2 Reading Material Solving a Linear system by using equations: What is the solution of a Linear system? It is the list of numbers corresponding to each variable that satisfies all the equations present in the system. If we consider the following system, a11 x1 + a12 x2 + … + a1n xn = b1 a21 x1 + a22 x2 + … + a2n xn = b2 …. …. am1 x1 + am2 x2 + … + amn xn = bm Then the corresponding values for the variables, x1, x2, …, xn is called as the solution for the Linear system. Solution set: The set of all possible solutions is called as the solution set of the linear system of equations. Two linear systems are said to be equivalent if they have the same solution set. What are the possibilities for the solution set? A system of linear equations can have either: 1. No solution (Inconsistent) 2. Exactly one solution (Unique solution) 3. Infinitely many solutions. Example: Find the solution for the system of linear equations: 5x + 10y + z = 17 x+y+z=4 4x + 8y + 3z = 18 Elementary row operations: There are namely three kinds of operations we can perform upon the rows/ columns of a matrix: 1. Replacement: We can replace one row by the sum of itself and a multiple of another row. 2. Interchange: We can interchange two rows. 3. Scaling: We can scale by multiplying all entries in a row by a non-zero constant. Row equivalent matrices: Two matrices are called are row equivalent if there is a sequence of elementary row operations that transforms one matrix into the other. Solving a Linear system by row operations using a matrix (Gauss Jordan Method): If we consider the following system of Linear equations, a11 x1 + a12 x2 + … + a1n xn = b1 a21 x1 + a22 x2 + … + a2n xn = b2 …. …. am1 x1 + am2 x2 + … + amn xn = bm Then we can express this in the form of an augmented matrix: 𝑎11 𝑎12 … 𝑎1𝑛 𝑏1 𝑎21 𝑎22 … 𝑎2𝑛 𝑏2 [ ]. … … … … 𝑎𝑚1 𝑎𝑚2 … 𝑎𝑚𝑛 𝑏𝑚 Which has the order m x (n + 1) (or) In this method we try to transform the augmented matrix 𝑎1 𝑏1 𝑐1 𝑑1 [ 𝑎2 𝑏2 𝑐2 𝑑2 ] 𝑎3 𝑏3 𝑐3 𝑑3 to the form 1 0 0 𝛼 [0 1 0 𝛽] 0 0 1 𝛾 Method: For solving a system of three linear equations in three unknowns by Gauss-Jordan method, elementary row operations are performed on the augmented matrix as indicated below. Step 1: (i) Transform the element in (1,1) position to 1, by a suitable elementary row transformation using the element at (2,1) or (3,1) position or other wise. (ii) Transform the non-zero elements, if any at (2,1) or (3,1) positions as zeros (other elements of the first column) by using the element 1 at (1,1) position. If, at the end of step 1, there is a non-zero element at (2,2) or (3,2) position, go to step 2. Otherwise skip it. Step 2: (i) Transform the element in (2,2) position to 1, by a suitable elementary row transformation using the element at (3,2) position or other wise. (ii) Transform the non-zero elements, if any, of the second column (i.e., the non-zero elements,if any, at (1,2) or (3, 2) positions) as zeros, by using the element 1 at (2,2) position. At the end of step 2, or after skipping it for reasons specified above, examine the element at (3,3) position. If it is non zero, go to step 3. Otherwise, stop. Step 3: (i) Transform the element in (3, 3) position to 1, by dividing R3 with a suitable number. (ii) Transform the other non-zero elements if any of the third column (that is, the non-zero elements, if any, at (1,3) or (2, 3) positions) as zeros, by using the 1 present at (3,3) position. Example: Solve the following equations by Gauss - Jordan method 3x + 4y + 5z = 18 2x - y + 8z = 13 5x - 2y + 7z = 20 The augmented matrix is 3 4 5 18 [2 − 1 8 13] 5 −2 7 20 On applying R1 → R1 – R 1 5 −3 5 ~ [2 − 1 8 13 ] 5 −2 7 20 On applying R2 → R2 - 2R1 , R3 → R3 - 5R1 , we get 1 5 −3 5 ~ [ 0 − 11 14 3] 0 − 27 22 − 5 On applying R1 → -5R2 + 2R3 , we get 1 5 −3 5 ~ [0 1 − 26 − 25 ] 0 − 27 22 −5 On applying R1 → R1 - 5R2 , R3 → R3 + 27R2 , we get 1 0 127 130 ~ [0 1 − 126 − 25 ] 0 0 − 680 − 680 On applying R3 → R3 ፥ (-680) , we get 1 0 127 130 ~ [ 0 1 − 26 − 25 ] 0 0 1 1 On applying R1 → R1 - 127 R3, R2 → R2 + 26R3 , we get 1 0 0 3 ~ [0 1 0 1] 0 0 1 1 Hence the solution is x = 3, y = 1, z = 1 Solving linear system using equations:  In this method we solve the system of linear equations by the elimination method wherein we eliminate variables in the set of equations by performing algebraic operations and subsequently reducing the equations to find the values of them. Let us understand this idea in a better sense with the help of an example: 4x – 2y + 3z = 1 …(1) x + 3y – 4z = -7 …(2) 3x + y + 2z = 5 …(3) Let us begin by eliminating the variable x by using the equations (1) and (2). In order to do this, let’s consider the operation (1) – 4 x (2)  4x – 2y + 3z = 1 - 4x – 12y + 16z = 28 -14y + 19z = 29 …(4) Now, let us eliminate the same variable x by using the equations (2) and (3). We can do this by the operation (3) – 3 x (2)  3x + y + 2z = 5 - 3x - 9y + 12z = 21 -8y + 14z = 26 …(5) Now, from the newly obtained equations eq (4) and (5) let’s eliminate the y term. We can do this by the operation 8 x (4) - 14 x (5)  - 112 y + 152z = 232 + 112 y – 196 z = -364 -44 z = -132 => z = 3. Now, since we have the value z = 3 we can substitute it in eq (5)  -8 y + 14(3) = 26  -8y + 42 = 26  - 8 y = - 16  Y=2 Now, since we have the values of y and z, we can substitute them in eq (1) to find the value of x  4 x – 2y + 3z = 1  4x – 2(2) + 3(3) = 1  4x -4 +9 = 1  4x + 5 = 1  4x = 1 – 5   4x = -4  X = -1 Therefore, we can conclude that the solution set of the system of linear equations is X = -1, Y = 2, Z = 3. Existence & Uniqueness Question: Existence Question: Can we always find at least one solution to the system? Uniqueness Question: Does the system have exactly one unique solution? Existence: Consider the following system of linear equations. Is the following system consistent? y – 4z = 8 2x – 3y + 2z = 1 5x – 8y + 7z = 1 Graphical view: If we try to represent the equations in the form of a graph, then it would look like the following: Algebraic view: Let us consider the augmented matrix formed by the following equations: 0 1 −4 8 [2 −3 2 1] 5 −8 7 1 If we perform row operations on this augmented matrix, we observe that there is no solution to the system of equations. Uniqueness: Consider the following system of equations: 5x + 10y + z = 17 (Red) x + y + z = 4 (Yellow) 4x + 8y + 3z = 18 (Blue) Geometrical view: Here, we can see that the planes intersect each other at one point. Algebraic view: Let us consider the augmented matrix of the given system of linear equations: 5 10 1 17 [1 1 1 4] 4 8 3 18 If we perform row operations on this augmented matrix, after a series of row operations we observe that the solution is x = 1, y = 1, z = 2 Echelon form and Reduced Echelon form: Basic definitions: 1. Non-zero row/ column: A row or column that contains at least one non-zero entry. 2. Leading entry: Leftmost nonzero entry in a nonzero row. Example: 2 1 3 A = [0 0 1] 0 0 0 - Here, R1 and R2 are nonzero rows, R3 is a zero row. - The element 2 in R1 is the leading entry in R1. - The element 1 in R2 is the leading entry in R2. Echelon form: A rectangular matrix is in echelon form (or row echelon form) if: 1. All nonzero rows are above zero rows (if any). 2. Each leading entry of a row is in a column to the right of the leading entry of the previous rows. 3. All the entries in a column below a leading entry are zero. Example: 1 4 8 −1 −4 0 2 5 2 0 [ ] 0 0 0 3 1 0 0 0 0 −1 Reduced Echelon form: If a matrix in echelon form satisfies the following additional conditions, then it is in reduced echelon form (reduced row echelon form). 1. The leading entry in each nonzero row is 1. 2. Each leading 1 is the only nonzero entry in its column. Example: 1 0 8 0 0 0 1 5 0 0 [ ] 0 0 0 1 0 0 0 0 0 1 Uniqueness of Reduced Echelon form: Any nonzero matrix maybe transformed into an echelon matrix using row operations. Different row operations may lead to different echelon matrices. Theorem: Each matrix is row equivalent to one and only one reduced echelon matrix. Example: Reduce the following matrix to echelon form: 1 2 3 4 A = [4 5 6 7] 6 7 8 9 And after attaining different echelon forms, attain the reduced echelon form. Pivot Position: As we know that the reduced echelon form is always unique, The leading entries of each row are always in the same position in any echelon form obtained from any matrix. Pivot Position: A pivot position in a matrix A is a location in A that corresponds to a leading 1 in the reduced echelon form of A. Example: 1 0 −1 −2 A = [0 1 2 3] 0 0 0 0 Pivot Column: Each leading 1 is the only nonzero entry in its column in the reduced echelon form. Pivot column: A pivot column in a matrix A is a column of A that contains a pivot position. Example: 1 0 −1 −2 A = [0 1 2 3] 0 0 0 0 If we consider the original matrix A 1 2 3 4 A = [4 5 6 7] 6 7 8 9 a11 and a21 are the pivot positions C1 and C2 are the pivot columns. Row Reduction Algorithm What is row reduction algorithm? It is a step-by-step process through which we can obtain the reduced echelon form of any matrix. This algorithm can be expressed in two phases: 1. Forward phase. 2. Backward phase. Forward phase: Step 1: - Being with the leftmost nonzero column. This will be a pivot column. - The pivot position is at the top. Example: 0 3 −6 6 4 −5 A = [3 −7 8 −5 8 9 ] 3 −9 12 −9 6 15  0 3 −6 6 4 −5 A = [3 −7 8 −5 8 9 ] 3 −9 12 −9 6 15 Here, C1 is the pivot column and the position of element 0 is the pivot position. (a11) Step 2: - Select a nonzero entry in the pivot column as a pivot. - Interchange rows to move this entry into the pivot position. Note: A computer program selects the largest value column entry as a pivot. Example: 0 3 −6 6 4 −5 A = [3 −7 8 −5 8 9 ] 3 −9 12 −9 6 15 Here, a11 is the pivot position and since in C1, the largest value is 3, we can choose it as the pivot. We interchange rows 1 and 3 to place the pivot in the pivot position. 3 −9 12 −9 6 15 A = [3 −7 8 −5 8 9 ] 0 3 −6 6 4 −5 Step 3: Use row replacement operations to create zeros in all positions below the pivot. 3 −9 12 −9 6 15 A = [3 −7 8 −5 8 9 ] 0 3 −6 6 4 −5 Here, the element 3 at a11 is the pivot hence, we need to convert the elements below a11 in C1 to zeros This can be done by a simple row operation R2 -> R2 - R1 3 −9 12 −9 6 15 A = [0 2 −4 4 2 −6] 0 3 −6 6 4 −5 Step 4: - Cover the rows containing the pivot position and all rows above it if any. - Apply steps 1-3 to the submatrix that remains. - Repeat the process until there are no more nonzero rows to modify. 3 −9 12 −9 6 15 A = [0 2 −4 4 2 −6] 0 3 −6 6 4 −5 Now we consider the highlighted submatrix from A and perform the steps 1 – 3 Here, 3 −9 12 −9 6 15 A = [0 2 −4 4 2 −6] 0 3 −6 6 4 −5 Here, the elements a22, a32 form the leftmost nonzero column in the submatrix. Here, 3 −9 12 −9 6 15 A = [0 2 −4 4 2 −6] 0 3 −6 6 4 −5 Here, the element 2 in C2 will be the pivot element and it’s position will be the pivot position. Hence, C2 will be a pivot column.  We need to turn the element below it into zero by using row operations. 3 −9 12 −9 6 15 A = [0 2 −4 4 2 −6] 0 3 −6 6 4 −5 R3 -> 2 R3 – 3 R2 3 −9 12 −9 6 15 A = [0 2 −4 4 2 −6] 0 0 0 0 2 8 R3 -> R3 / 2 3 −9 12 −9 6 15 A = [0 2 −4 4 2 −6] 0 0 0 0 1 4 Now, we need to consider the following submatrix:  3 −9 12 −9 6 15 A = [0 2 −4 4 2 −6] 0 0 0 0 1 4 Here, from step 1 we need to consider the left most nonzero column in the submatrix Which is the element 1. Hence, this becomes the pivot element and its position is the pivot position. Backward Phase: Step 5: Beginning with the rightmost pivot and working upwards and to the left, create zeros above each pivot. If a pivot is not 1, make it 1 by scaling operation. 3 −9 12 −9 6 15 A = [0 2 −4 4 2 −6] 0 0 0 0 1 4 Here, the column C5 is a pivot column and the element 1 is the pivot element. We need to make the entries above it zero. 3 −9 12 −9 6 15 A = [0 2 −4 4 2 −6] 0 0 0 0 1 4 R1 -> R1 – 6 R3 R2 -> R2 – 2 R3 3 −9 12 −9 0 −9 A = [0 2 −4 4 0 −14] 0 0 0 0 1 4 Now, since the pivot element in C5 is 1 and the values above it are all zeros, we can consider the pivot column to the left of C5 3 −9 12 −9 0 −9 A = [0 2 −4 4 0 −14] 0 0 0 0 1 4 Here, the next pivot column is C2 and the pivot element in C2 is the element 2 We need to make the pivot element 1 We can do it by R2 -> R2 / 2 3 −9 12 −9 0 −9 A = [0 1 −2 2 0 −7] 0 0 0 0 1 4 In C2, the element above 1 must be zero and we can convert it to zero by the operation: R1 -> R1 + 9 R2 3 0 −6 9 0 −72 A = [0 1 −2 2 0 −7 ] 0 0 0 0 1 4 Here, the next pivot column is C1 and the pivot position is the position of element 3, we need to turn element 3 into 1. We can do this by the operation: R1 -> R1 / 3 1 0 −2 3 0 −24 A = [0 1 −2 2 0 −7 ] 0 0 0 0 1 4 The final matrix attained here is in the reduced echelon form with C1, C2 and C5 as the pivot columns. 1 0 −2 3 0 −24 A = [0 1 −2 2 0 −7 ] 0 0 0 0 1 4 Existence and Uniqueness theorem: Consider the row reduced echelon form of an augmented matrix: 1 0 −5 1 A = [0 1 1 4] 0 0 0 0 If we consider the corresponding equation, it is of the form: x1 – 5 x2 = 1 x2 + x3 = 4 0=0 Basic Variables and Free variables: Basic variables: The variables corresponding to the pivot column in the matrix are called as the basic variables. Free variables: All other variables apart from basic variables are called as the free variables. 1 0 −5 1 A = [0 1 1 4] 0 0 0 0 If we consider the above reduced echelon form, Basic variables: x1 and x2 (The variables corresponding to the pivot columns) Free variables: x3 (The variables corresponding to the non-pivot columns). Solution of linear systems: Whenever the system is consistent, i.e., it has a solution then we can express the basic variables in terms of free variables. If we consider the equations from the previous example, x1 – 5 x2 = 1 x2 + x3 = 4 0=0 Here, x1 = 1 + 5 x2 x2 = 4 – x3 x3 is a free variable. Here, the system has a solution and we can see that the system has infinitely many solutions as x3 can take any value and we would have corresponding values for x1 and x2 So, we can think of this situation as For each choice of free variable, There are values of basic variables, And together they produce a solution. Existence and Uniqueness Theorem: A linear system is consistent if and only if in the augmented matrix: 1. Rightmost column is not a pivot column. 2. An echelon form has no row of the form: [0 … 0 b] where b ≠ 0 For a consistent linear system, the solution set contains: A unique solution when there are no free variables. Infinitely many solutions, when there is at least one free variable. Matrix of Co-factors, Adjoint, & Inverse: Multiplicative identity of any number: The value when multiplied to that number produces the number itself. For real numbers, it is 1. For any square matrix A, it is the identity matrix I  A I = I A = A. Multiplicative Inverse: It is the number when multiplied to the original number produces the multiplicative identity. For any real number x ≠ 0, 1/ x is the multiplicative inverse.  x. 1/ x = 1 An n x n matrix A is said to be invertible if there is an n x n matrix C such that CA = AC =I Where, I is the n x n identity matrix. C is the inverse of matrix A. Inverse is unique: The inverse of a matrix, if it exists is unique. A -> Matrix A-1 -> Inverse of A. B -> another inverse of A. B = B.I = B (A.A-1) = (BA).A-1 = I. A-1 = A-1 Note: - A matrix is called as a singular matrix if it is noninvertible. - A matrix is called as nonsingular matrix if it is invertible. Example: 1 1 1 1 − A= [√2 1 √2 1 ] and C = [−√21 √2 1] √2 √2 √2 √2 Here, 1 0 AC = CA = [ ] 0 1 Thus C = A-1 Matrix of cofactors: Let A be a n x n matrix and Cij be the cofactor of aij The matrix whose (i, j)th element is Cij is called the matrix of cofactors of A. 𝐶11 𝐶12 … 𝐶1𝑛 𝐶21 𝐶22 … 𝐶2𝑛 [ ] … … … … 𝐶𝑛1 𝐶𝑛2 … 𝐶𝑛𝑛 Adjoin of matrix: Adjoint of a matrix A is defined as the transpose of the matrix of cofactors of A. 𝐶11 𝐶21 … 𝐶𝑛1 𝐶12 𝐶22 … 𝐶𝑛2 Adj (A) = [ ] … … … … 𝐶1𝑛 𝐶2𝑛 … 𝐶𝑛𝑛 Computing Inverse of a matrix: Let A be a square matrix with | A | ≠ 0. Matrix A is invertible with 𝐴𝑑𝑗(𝐴) A-1 = |𝐴| Example: Find the inverse of the matrix 2 1 3 A = [1 −1 1 ] 1 4 −2 Solution: Step 1: Finding the Determinant of A: det(A) = 2((-1)(-2) - 1(4)) – 1(1(-2) - 1(1)) + 3(1(4) – (-1)(1)) det(A) = 2(2-4) – 1(-2-1) + 3(4+1) det(A) = 2(-2) – 1(-3) + 3(5) det(A) = -4 + 3 + 15 = 14 so, det(A) = 14. Step 2: Finding the Adjoint of A: Cofactor 𝐶11 (minor of element 2): −1 1 𝐶11 = det ( ) = (-1) (-2) – (1) (4) = 2 - 4 = -2 4 −2 Cofactor 𝐶12 (minor of element 1): 1 1 𝐶12 = det ( ) = (1) (-2) – (1) (1) = -2 – 1 = -3 1 −2 And since it’s in the second column, we apply a negative sign: 𝐶12 = 3. Cofactor 𝐶13 (minor of element 3): 1 −1 𝐶13 = det ( ) = (1) (4) – (-1) (1) = 4 + 1 = 5 1 4  Cofactor 𝐶21 (minor of element 1): 2 3 𝐶21 = det ( ) = (1) (-2) – (3) (4) = - 2 – 12 = -14 4 −2 And since it’s in the second row, we apply a negative sign: 𝐶21 = 14. Cofactor 𝐶22 (minor of element -1): 2 3 𝐶22 = det ( ) = (2) (-2) – (3) (1) = - 4 – 3 = -7 1 −2 Cofactor 𝐶23 (minor of element 1): 2 1 𝐶23 = det ( ) = (2) (4) – (1) (1) = 8 – 1 = 7 1 4 And since it’s in the third column, we apply a negative sign: 𝐶23 = -7 Cofactor 𝐶31 (minor of element 1): 1 3 𝐶31 = det ( ) = (1) (1) = (3) (-1) = 1 + 3 = 4 −1 1 Cofactor 𝐶32 (minor of element 4): 2 3 𝐶32 = det ( ) = (2) (1) – (3) (1) = 2 – 3 = -1 1 1 And since it’s in the second row, we apply a negative sign: 𝐶32 = 1 Cofactor 𝐶33 (minor of element -2): 2 1 𝐶33 = det ( ) = (2) (-1) – (1) (1) = - 2 – 1 = -3 1 −1 Thus, the cofactor matrix is: −2 3 5 (14 − 7 − 7) 4 1 −3 The Adjoint of the matrix is found by the Transpose of the Cofactor matrix: −2 14 4 adj(A) = ( 3 −7 1 ) 5 −7 −3 Therefore, the inverse of the matrix A is: −2 14 4 1 𝐴−1 = 14 ( 3 − 7 1 ) 5 −7 −3 Solving Linear system using Inverse of a matrix: The general representation of a linear system in matrix notation can be thought of as AX = B Where, A is the coefficient matrix. X is the column vector of variables. B is the column vector of constants. 𝑎11 𝑎12 … 𝑎1𝑛 𝑥1 𝑏1 𝑎21 𝑎22 … 𝑎2𝑛 𝑥2 𝑏2 A=[ ] X=[ ] B=[ ]. … … … … … 𝑎𝑚1 𝑎𝑚2 … 𝑎𝑚𝑛 𝑥𝑚 𝑏𝑚 Consider the matrix equation AX = B where, if A is non-singular i.e., |A| ≠ 0. Then we can find A-1  For each b in Rn the equation AX = b has a unique solution X = A-1b Proof: Let AX = b where b is in Rn Step 1: To prove that X = A-1b is a solution: It is a solution, then it must satisfy the linear system of equations. AX = A(A-1b) = (AA-1)b = I.b = b Step 2: To prove that this solution is unique. Let U be any solution, then AU = b. Multiply A-1 on both sides. A-1 AU = A-1b  IU = A-1b  U = A-1b (or) Consider the matrix equation AX = D, where A is non-singular. Then we can find 𝐴−1 AX = D ↔ 𝐴−1 (AX) = 𝐴−1 D ↔ ( 𝐴−1 A) X = 𝐴−1 D ↔ IX = 𝐴−1 D (I is the unit matrix). ↔ X = 𝐴−1 D From this x, y and z are known. Example: 3x + 4y + 5z = 18 2x – y + 8z = 13 5x – 2y + 7z = 20 3 4 5 𝑥 18 Let A = [ 2 − 1 8 ] ; X = [𝑦] and D = 5 −2 7 𝑧 20 Then we can write the given equations in the form AX = D. 3 4 5 det A = [ 2 − 1 8 ] = 136 ≠ 0 5 −2 7 Hence we can solve the given equations by ‘Matrix inversion method’. 9 − 38 37 We have Adj A = [26 − 4 − 14] 1 26 − 11 From matrix inversion method, 9 − 38 37 18 3 𝐴𝑑𝑗 𝐴 1 X = A-1 D =.D= [26 − 4 − 14] = det 𝐴 136 1 26 − 11 20 1 ⸫ x = 3, y = 1 and z = 1 is the solution of the given systems of equations. Solving Linear system using Cramer’s rule: Ai (b) For any n x n matrix A and any b in Rn, let Ai (b) be the matrix obtained from A by replacing column i by the vector b. Ai (b) = [a1 a2 … b … an] Here, the ith column is replaced by b. Cramer’s rule: If A is an invertible n x n matrix. For any b in Rn, the equation AX = b has the unique solution with entries |𝐴𝑖 (𝑏)| Xi = |𝐴| (or) Consider the system of equations a1x + b1y + c1z = d1 a2x + b2y + c2z = d2 a3x + b3y + c3z = d3 𝑎1 𝑏1 𝑐1 Where A = [𝑎2 𝑏2 𝑐2 ] is non-singular. 𝑎3 𝑏3 𝑐3 𝑥 𝑑1 Let X = [𝑦] be the solution of the equation AX = D, where D = [𝑑2] 𝑧 𝑑3 𝑎1 𝑏1 𝑐1 Let ∆ = |𝑎2 𝑏2 𝑐2| 𝑎3 𝑏3 𝑐3 𝑑1 𝑏1 𝑐1 ∆1 x= where ∆1 = |𝑑2 𝑏2 𝑐2| ∆ 𝑑3 𝑏3 𝑐3 𝑎1 𝑑1 𝑐1 ∆2 y= where ∆2 = |𝑎2 𝑑2 𝑐2| ∆ 𝑎3 𝑑3 𝑐3  𝑎1 𝑏1 𝑑1 ∆3 z= where ∆3 = |𝑎2 𝑏2 𝑑2| ∆ 𝑎3 𝑏3 𝑑3 Example: Solve the following simultaneous linear equations by using Cramer's rule. 3x + 4y + 5z = 18 2x – y + 8z = 13 5x – 2y + 7z = 20 3 4 5 𝑥 18 Let A = [2 −1 8] ; X = [ ] and D = 𝑦 5 −2 7 𝑧 20 Then we can write the given equations in the form of matrix equation as AX = D. 3 4 5 ∆ = det A = |2 −1 8| 5 −2 7 −1 8 2 8 2 −1 =3| |-4| |+5| | −2 7 5 7 5 −2 = 3 ( -7 + 16 ) – 4 ( 14 – 40 ) + 5 ( - 4 + 5) = 27 + 104 + 5 = 136 ≠ 0. Hence we can solve the given equation by using Cramer’s rule. 18 4 5 ∆1 = |13 −1 8| = 408 20 −2 7 3 18 5 ∆2 = |2 13 8| = 136 5 20 7 3 4 18 ∆3 = |2 −1 13| = 136. 5 −2 20 Hence by Cramer’s rule, ∆1 408 ∆2 136 ∆3 136 x= = = 3; y = = = 1 and z = = = 1. ∆ 136 ∆ 136 ∆ 136 ⸫ The solution of the given system of equations is x = 3, y = 1 = z. Note: Observe that Cramer's Rule and Matrix inversion method can be applied only when the coefficient matrix A is non-singular. Gauss Jordan can be used even if the matrix is singular.  Week 3 Reading Material Motivation for vector spaces: If we had to solve the system of equations 1 1 𝑥− 𝑦 = √2 √2 √2 1 1 𝑥+ 𝑦 = −√2 √2 √2 We can rewrite this as 1 −1 x [√2 + y [ √2 √2 ] 1] 1 ]=[ −√2 √2 √2 Let us look into another similar problem Find the value of x and y X (2t2 – 3t + 4) + y(-5t + 7) = 2t2 – 8t + 11 Is there a generalization which works for both the equations? This leads us to the notion of vector spaces. Vector Space: A vector space is a non-empty set V consisting of objects called vectors on which namely two operations are defined, addition and multiplication by scalar (real numbers). These vector spaces are subject to ten axioms/ rules which must be satisfied by all the vectors present in V and for all the scalars used. Let u, v, and w be the vectors in V; c and d be any scalars. Axioms corresponding to vector spaces: The axioms corresponding to the vector spaces can be segregated as follows: 1. Closure axioms: - Axiom 1: The sum of two vectors u and v, denoted by u + v must be in V (vector space).  - Axiom 2: The scalar multiplication of u by a scalar c, denoted by cu must be in V. 2. Addition axioms: - Axiom 3: The commutative property of addition is u + v = v + u. - Axiom 4: The associativity property of addition is (u + v) + w = u + (v + w). - Axiom 5: Additive identity – There is a zero vector 0 in V such that u + 0 = u. - Axiom 6: Additive inverse – for each vector u in V, there is a vector – u in V such that u + (- u) = 0. 3. Scalar multiplication axioms: - Axiom 7: c (u + v) = cu + cv. - Axiom 8: (c + d) u = cu + cd. - Axiom 9: c (du) = (cd) u. - Axiom 10: 1 u = u Examples: 1. Prove that Rn is a vector space, where: 𝑥1 𝑥2 n R = {. Such that x1, x2, x3, …, xn belong to real numbers}. [𝑥𝑛] Sol: In order to show that Rn is a vector space, we need to check if it satisfies all the ten axioms.  Axiom 1: The sum of the vectors u and v => u + v must be in Rn  𝑥1 𝑦1 𝑥2 𝑦2 n Let us consider two vectors from R such that u =. and v =.... [𝑥𝑛] [𝑦𝑛] 𝑥1 + 𝑦1 𝑥2 + 𝑦2 Now if we compute their sum i.e u + v, we get u + v =... [𝑥𝑛 + 𝑦𝑛] Since the values of xi and yi are all real numbers, such that i = 1, 2 , 3,.., n.  their sum will also be a real number and hence the resulting vector u + v will be in Rn.  Axiom 2: The scalar multiplication of a vector u with a scalar c denoted by cu must be in Rn. 𝑥1 𝑥2 Let us consider u =. and a scalar value c.. [𝑥𝑛] 𝑐𝑥1 𝑐𝑥2  Their product cu =.. Since all the values of xi are real numbers. [𝑐𝑥𝑛] and c is a scalar the product of cxi will be a real number. Hence, cu will be in Rn.  Axiom 3: The commutative property over addition must be obeyed such that u + v must be equal to v + u. 𝑥1 𝑦1 𝑥2 𝑦2 If we consider u =. and v =. , then their sum.. [𝑥𝑛] [𝑦𝑛] 𝑥1 + 𝑦1 𝑦1 + 𝑥1 𝑥2 + 𝑦2 𝑦2 + 𝑥2 u+v=. and the sum v + u =.... [𝑥𝑛 + 𝑦𝑛] [𝑦𝑛 + 𝑥𝑛]  Since the values of xi and yi are real  u + v = v + u.  Axiom 4: The associative property over addition must be obeyed i.e, (u + v) + w = u + (v + w) Since, real numbers are commutative over addition, we can clearly conclude that they obey associative property.  (u + v) + w = u + (v + w)  Axiom 5: Additive identity (there must be a zero vector in R n such that u + 0 = u) 𝑥1 0 𝑥1 𝑥2 0 𝑥2  u+0=. +. =.... [𝑥𝑛] [ 0] [𝑥𝑛] Since, Rn is a vector containing real entries, the zero vector is also present in Rn.  Axiom 6: Additive inverse (there must be a vector -u in Rn such that u + (- u) = 0) 𝑥1 −𝑥1 𝑥2 −𝑥2 If u =. , then Rn will contain -u =. since Rn has real values... [𝑥𝑛] [−𝑥𝑛]  Rn will have a vector -u for every vector u in it.  Axiom 7: c (u + v) = cu + cv, where c is a scalar value; u and v are vectors. 𝑥1 𝑦1 𝑥2 𝑦2 Consider u =. and v =... [𝑥𝑛] [𝑦𝑛] 𝑥1 𝑦1 𝑥1 + 𝑦1 𝑐(𝑥1 + 𝑦1) 𝑥2 𝑦2 𝑥2 + 𝑦2 𝑐(𝑥2 + 𝑦2)  c (u + v) = c (. +. ) = c (. )=..... [𝑥𝑛] [𝑦𝑛] [ 𝑥𝑛 + 𝑦𝑛 ] [ 𝑐(𝑥𝑛 + 𝑦𝑛)]  𝑐𝑥1 + 𝑐𝑦1 𝑐𝑥1 𝑐𝑦1 𝑐𝑥2 + 𝑐𝑦2 𝑐𝑥2 𝑐𝑦2 . =. +. = cu + cv... [ 𝑐𝑥𝑛 + 𝑐𝑦𝑛] [𝑐𝑥𝑛] [𝑐𝑦𝑛] Therefore, c (u + v) = cu + cv.  Axiom 8: (c + d) u = cu + du, where c and d are scalars; u is a vector This can be verified in a similar way as shown above. Therefore, Rn satisfies axiom 8.  Axiom 9: c(du) = (cd) u  Axiom 10: 1u = u Since, Rn contains real values, the product of any vector contained in Rn with 1 will result in the vector itself. Since, Rn satisfies all the ten axioms of a vector space,  Rn is a vector space. 2. For n >= 0, the set Pn of polynomials of degree at most n consists of all polynomials of the form P(t) = a0 + a1t + a2t2 + …. + antn where the values of all the ai and t belongs to real numbers. Check if P n forms a vector space. Sol: To verify if the above polynomial forms a vector space or not, let us consider two polynomial equations P(t) = a0 + a1t + a2t2 + …. + antn ------ (1) Q(t) = b0 + b1t + b2t2 + …. + bntn ------ (2)  Axiom 1: P(t) + Q(t) must belong to Pn P(t) + Q(t) = (a0 + b0) + (a1 + b1)t +…. +(an + bn)tn  Here, since the values of ai and bi are all real numbers, hence their sum will also result in a real number and the coefficients of the terms in the polynomial will still remain real.  P(t) + Q(t) will belong to Pn.  Axiom 2: The scalar multiplication of P(t) with some scalar c must be in P n denoted by cP(t) cPn = c (a0 + a1t + a2t2 + …. + antn) = ca0 + ca1t + ca2t2 + …. + cantn Since, c is a scalar and all the ai’s are real values the cai’s will be real resulting in cP(t) belonging to Pn.  Axiom 3: commutative property over addition is obeyed. P(t) + Q(t) = Q(t) + P(t).  Axiom 4: The associative property over addition is obeyed. (P(t) + Q(t)) + R(t) = P(t) + (Q(t) + R(t)).  Axiom 5: Additive identity (there must be a zero polynomial in P n) such that 0(t) + P(t) = P(t). This is possible as 0 polynomial can be constructed by assigning all the ai values to zero  a0 = a1 = … = an = 0.  Axiom 6: Additive inverse of P(t) must be in Pn. The additive inverse of P(t) is -P(t) and this lies in P n as the ai’s can take any real values and this means they can take the values of -ai’s for corresponding coefficients.  Axiom 7: c (P(t) + Q(t)) = cP(t) + cQ(t) where c is a scalar value.  Axiom 8: (c + d) P(t) = cP(t) + dP(t). where c and d are scalar values.  Axiom 9: c(dP(t)) = (cd) P(t) where c and d are scalar values.  Axiom 10: 1P(t) = P(t). This can be achieved as product of a polynomial with 1 will result in polynomial itself. Since, Pn satisfies all the axioms of a vector space  Pn is a vector space. Since, we have discussed a couple of examples for vector spaces let’s look into examples which would not be vector spaces.  𝑥1 3. V = { [𝑥2]; such that x1 + x2 + x3 = 1} 𝑥3 𝑥1 𝑦1 Sol: Let us consider two vectors u = 𝑥2 and v = 𝑦2] such that the condition for u is x1 [ ] [ 𝑥3 𝑦3 + x2 + x3 = 1 and the condition for v is y1 + y2 + y3 = 1. Let us verify if V obeys all the axioms of a vector space using u and v.  Axiom 1: If u and v are in V, then u + v must be in V. 𝑥1 + 𝑦1  u + v = [𝑥2 + 𝑦2] such that the sum of these entries is equal to 1. 𝑥3 + 𝑦3  (x1 + y1) + (x2 + y2) + (x3 + y3) must be equal to 1 ----(1) If we consider the LHS of the above equation, then we can express it equivalently as (x1 + x2 + x3) + (y1 + y2 + y3) = 1 + 1 = 2. Which violates the condition stated in (1). Therefore, u + v does not belong to V.  V is not a vector space. Subspace of a vector space: Is it possible that a subset of a vector space is also a vector space? How can we verify this? Vector Subspace: A subspace of a vector space V is a subset H of V that has three properties: 1. The zero vector of V is in H (Axiom 5) => {0} belongs to V. 2. H is closed under vector addition (Axiom 1) => u + v belongs to V. 3. H is closed under multiplication by scalars (Axiom 2) => cu belongs to V. Addition axioms and scalar multiplication axioms are automatically true in H because they apply to all elements of V including those in H. The set consisting of only the zero vector in a vector space V is a subspace of V. It is called as the zero subspace and written as {0}. Examples: 1. The vector space R2 is not a subspace of R3 because R2 is not a subset of R3 as the vectors in R3 have three entries, whereas the vectors in R2 have only two entries. 𝑥1 𝑥1 R2 = [ ] whereas R3 = [ 𝑥2 ] 𝑥2 𝑥3 𝑠 2. Let H = {[ 𝑡 ] S.t s and t are real}. H is a subset of R3, then prove that H is a subspace 0 3 of R. Sol: In order to prove that H is a subspace of R3, we need to verify the three axioms of the vector subspace. 0 i. Zero vector will belong to H because the values of s and t are real. 0 (Axiom 5). 𝑢1 𝑣1 ii. Let us consider two vectors u = [𝑢2] and v = [𝑣2] such that they belong 0 0 𝑢1 + 𝑣1 to H, then u + v = [𝑢2 + 𝑣2] and this will belong to H for any real values 0 of u and v. (Axiom 1). 𝑢1 𝑐𝑢1 iii. If u = [𝑢2] belongs to H, then cu = [𝑐𝑢2] will also belong to H. (Axiom 0 0 2). Since, H obeys all the properties of a subspace H is a subspace of R 3. 𝑥1 3. Check if V = { [ ] such that x1 >= 0 and x2 >= 0}is a subspace of R2 𝑥2 Sol: Here to check if V is a subspace of R2, we need to check if it obeys the above stated three axioms.  The zero vector of V belongs to R2 0 Here, the zero vector or V is [ ] will belong to R2 as x1 and x2 values can be 0 greater than or equal to zero.  𝑥1 𝑦1  The addition of any two vectors u = [ ] and v = [ ] will result in a value greater 𝑥2 𝑦2 than or equal to zero and hence u + v will belong to V. 𝑐𝑥1  The scalar multiplication of V with any scalar value c will result in [ ] but here, 𝑐𝑥2 if the values of c are negative scalars, then the scalar multiplication will not obey that the entries in V are either positive or zero and hence V does not satisfy the condition cv belongs to V.  V is not a vector subspace of R. A subspace spanned by a set: Geometrical view of vector operation in 2D: Let’s take two vectors from ℝ2, the 2 - dimensional real vector space. For example, let : 1 u=( ) 2 3 v=( ) 4 These vectors u and v are elements of ℝ2. They can be added together or multiplied by scalars to demonstrate the properties of the ℝ2, vector space. Addition and Scalar multiplication of vectors: These vectors u and v are elements of ℝ2. They can be added together or multiplied by scalars to demonstrate the properties of the ℝ2, vector space. Let’s see some basic operations with these vectors: 1) Addition : 1 3 1+3 4 u+v=( )+( )=( )=( ) 2 4 2+4 6 2) Scalar Multiplication : 1 2.1 2 2u = 2 ( ) = ( )=( ) 2 2.2 4 If we try and represent the addition operation of the vectors in a 2 – D coordinate system using u = (1, 2) and v = (3, 4) and u + v = (4, 6); we get the following graph. u + v (Green) u (Red) v (Blue) Here, u and v form the adjacent sides of a parallelogram and u + v represents the diagonal. Similarly, if we try to represent the multiplication of a vector with some scalar in a 2 – D coordinate system, we can attain the following graph. Here, the vector u = (1, 2) after being multiplied with a scalar value 2, turned into (2, 4) which can be clearly seen in the graph as a scaling up operation upon the vector u. Similarly, if we multiply the vector with a negative scalar quantity the vector gets scaled down. Linear combination of vectors: Let v1, v2, …, vn be vectors in a vector space V. The vector v in V is a linear combination of v1, v2, …, vn if there exists some scalars c1, c2, …, cn such that v = c1v1 + c2v2 + …. + cnvn Example: 1 u=( ) 2 3 v=( ) 4 A linear combination of these two vectors can be written as : w = au + bv where a and b are scalars. Let’s choose a = 2 and b = -1: w = 2u – 1v substituting the values of u and v: 1 3 w=2( )–1( ) 2 4 2.1 3 w=( ) − ( ) 2.2 4 2 3 w=( )-( ) 4 4 2−3 w=( ) 4−4 −1 w=( ) 0 So, the linear combination 2u – 1v results in the vector: −1 w=( ) 0 Span of vectors: Let v1, v2, …, vn be vectors in a vector space V. The set of all linear combinations of v1, v2, …, vn is denoted by span {v1, v2, …, vn} and is called subset of V spanned by the vectors v1, v2, …, vn. Example: If we consider the vector space R2, this entire 2 D plane is spanned by v1 = (1, 0) and v2 = (0, 1). - Any vector v = {x1, x2} from this space R2 can be written as,  v = (x1, x2) = x1(1, 0) + x2(0, 1)  x1v1 + x2v2. Theorem: If v1, v2, …, vn are in a vector space V, then span {v1, v2, …, vn} is a subspace of V. Example: Given v1 and v2 are in a vector space V. Let H = span{v1, v2}. Show that H is a subspace of V. Sol: In order to show that H is a subspace of V, we need to show that, Step 1: The zero vector of V is in H. Since, 0 = 0.v1 + 0.v2 so 0 is in the span{v1,v2} = H (since, expressing 0 vector as a linear combination of v1 and v2) Step 2: H must be closed under addition. Let u and w be two vectors from H. It means u = a1v1 + a2v2 and w = b1v1 + b2v2.  u + w = (a1 + b1) v1 + (a2 + b2) v2.  u + w is also in H = Span {v1, v2}. Step 3: H must be closed under scalar multiplication. Let u be a vector from H. It means u = a1v1 + a2v2 (since, any vector from H can be expressed as a linear combination of v1, v2) If we compute the scalar multiplication of u with a scalar c,  cu = c.a1v1 + c.a2v2.  cu is also in H = Span {v1, v2}. Since, H obeys all the three properties of a subspace, H is subspace of V. Linear Transformation: A linear transformation T maps a vector space V into another vector space W by preserving the structure. Here, The vector space V is called as the Domain. The vector space W is called as the Co-Domain. Linear Transformation can also be thought of as a rule that assigns each vector x in V to a unique vector T(x) in W. Such that the following conditions are met: 1. T(u + v) = T(u) + T(v) for all u and v ∈ V 2. T(cu) = cT(u) for all u ∈ V and scalars c. X1 T(X1) X2 T(X2) ….. ….. Xn T(Xn).. Analogy for understanding a Linear Transformation: We can think of matrix multiplication as a Linear transformation as the matrix A when multiplied to some vector X, it produces a new vector b Ax = b Example: 1 4 −3 1 3 1 1. [ ] [ ] = 2 0 5 1 1 8 1 A X b 1 4 −3 1 3 4 0 2. [ ][ ]=[ ] 2 0 5 1 −1 0 3 A u 0 We can think of this situation as multiplication of matrix A transforms x into b and transforms u into the zero vector. Example: 1. Let T: R3 -> R2 be a transformation defined by 𝑥 𝑥 + 2𝑦 T [𝑦 ] = [ ] 𝑦 + 2𝑧 𝑧 Show that T is a linear transformation. Solution : Step 1: Show T(u + v) = T(u) + T(v). 𝑢1 𝑣1 Let u = [𝑢2] and v = [𝑣2]. 𝑢3 𝑣3 T: ℝ3 → ℝ2 𝑥 𝑥 + 2𝑦 T [𝑦] = [ ] 𝑦 + 2𝑧 𝑧 𝑢1 + 𝑣1 Now u + v = [𝑢2 + 𝑣2] 𝑢3 + 𝑣3 𝑢1 + 𝑣1 T (u + v) = T [𝑢2 + 𝑣2] 𝑢3 + 𝑣3  𝑢1 + 𝑣1 + 2(𝑢2 + 𝑣2) =[ ] 𝑢2 + 𝑣2 + 2(𝑢3 + 𝑣3) 𝑢1 + 2𝑢2 𝑣1 + 2𝑣2 =[ ] + [ ] = T (u) + T (v) 𝑢2 + 2𝑢3 𝑣2 + 2𝑣3 Step 2: Show T(cu) = cT (u). 𝑢1 Let u = [𝑢2] 𝑢3 𝑐𝑢1 + 2𝑐𝑢3 T(cu) = [ ] 𝑐𝑢2 + 2𝑐𝑢3 𝑢1 + 2𝑢2 = c[ ] 𝑢2 + 2𝑢3 = c T(u). Let T : ℝ3 → ℝ2 be a transformation defined by 𝑥 𝑥 + 2𝑦 T[ 𝑦 ] = [ ] 𝑦 + 2𝑧 𝑧 Write this transformation as 𝑥 1 2 0 𝑦 𝑥 + 2𝑦 [ ][ ]=[ ] 0 1 2 𝑧 𝑦 + 2𝑧 Kernel of Linear Transformation: If a linear transformation is a matrix transformation - Kernel is the Null space. - Range is the column space of that matrix. Every matrix transformation is a linear transformation. If a linear transformation is a matrix transformation, then kernel is the null space and range is the column space of that matrix. Linear Dependence & Independence, Basis: Linearly Independent: An indexed set of vectors {v1, v2, …, vn} in V is said to be linearly independent if the vector equation c1v1 + c2v2 + … + cnvn = 0 has only the trivial solution  c1 = c2 =.. = cn = 0. Linearly Dependent: An indexed set of vectors {v1, v2, …, vn} in V is said to be linearly dependent if the vector equation c1v1 + c2v2 + … + cnvn = 0 has a nontrivial solution that is, if there are some values of c 1, c2, …, cn not all zero satisfying above equation. An indexed set of vectors {v1, v2, …, vn} of two or more vectors, with v1 not equal to 0 is linearly dependent if and only if some vj (with j > 1) is a linear combination of the preceding vectors v1, v2, …, vj-1.  vj = c1v1 + c2v2 + … + cnvn Example: 2 0 4 Check if u = , v = , and w = 1 2 0 are linearly dependent or independent. Definition of Basis: Let H be a subspace of vector space V. An indexed set of vectors B = {b1, b2, …, bn} in V is a basis for H if B is a linearly independent set The subspace spanned by B coincides with H; that is H = Span{b1, b2, …, bn} Example: Let e1, e2, …, en be the column vectors of the n x n identity matrix. 1 0 0 0 0 0 e1 = [ ], e2 = [ ], …, en = [ ]...... 0 1 1 Here, all these values of ei belong to Rn 1 0 0 0 0 0 0 0 x1 [ ] + x2 [ ] + … + xn [ ] = [ ]........ 0 1 1 0 x1 = x2 = … = xn = 0 is the only solution Observation 2: 𝑢1 𝑢2 Any vector u = [ ] ∈ Rn is expressible as a linear combination of e1, e2, …, en as.. 𝑢𝑛 𝑢1 1 0 0 𝑢2 0 1 0 [ ] = u1 [ ] + u2 [ ] + … + un [ ]........ 𝑢𝑛 0 0 1 Example: Standard basis of Rn The spanning set theorem: Let S = {v1, v2, …, vn} be a set in V, and H = Span {v1, v2, …, vn}., 1. If, S = {v1, v2, …, v(k – 1), vk, …., vn} -> Span H If we assume that vk can be expressed as a linear combination of the remaining vectors in S,  S = {v1, v2, …, v(k-1), v(k+1), …, vn} -> Span H 2. If H ≠ {0}, some subset of S is a basis for H. Proof of spanning set theorem:  Part 1: By rearranging the list of vectors in s, if necessary, Vn is a linear combination of the remaining vectors is S.  It means Vn = c1v1 + c2v2 + … + cn-1vn-1 Let u be vector in H, so u = a1v1 + a2v2 + …. + anvn = a1v1 + a2v2 + …. + an ( c1v1 + c2v2 + … + cn-1vn-1 ) Thus, any vector of H can be expressed as a linear combination of v1, v2, …, vn-1 and hence H = Span { v1, v2, …, vn-1 }.  Part 2: If the original spanning set S is linearly independent, then it is already a basis for H.  The dependent vectors in S can be deleted till vectors in the spanning set are not linearly independent.  With two or more vectors, there will be a basis for H.  Spanning set with one vector, a non-zero vector as H ≠ {0}, is linearly independent and is a basis for H. Example: 0 2 6  Let v1 = [ 2 ] , v2 = , v3 = [ 16 ] , and H = Span {v1, v2, v3 }. −1 0 −5 Show that  Span {v1, v2, v3 } = Span { v1, v2 } Find a basis for H. Null Space of a Matrix: Homogeneous Equation: An equation in which the constant value in the equation is zero Example: x – 3y – 2z = 0 -5x + 9y + z = 0 We can express this as AX = 0 where, 𝑥 0 1 −3 −2 A= [ ] , X = [ 𝑦 ], 0 = [ 0 ] −5 9 1 𝑧 0 The null space of an m x n matrix A is the set of all solutions to the homogeneous equation AX = 0 Example: Consider the following set of homogeneous equations x – 3y – 2z = 0 -5x + 9y + z = 0 We can express this as AX = 0 where, 𝑥 0 1 −3 −2 A= [ ] , X = [ 𝑦 ], 0 = [ 0 ] −5 9 1 𝑧 0 The set of all values of x, y, and z that satisfy AX = 0 is called as the Null Space of the matrix A. Representation: Nul(A) = {x | x ∈ Rn and AX = 0} Theorem: The null space of an m x n matrix A is a subspace of Rn Proof: The null space of matrix A is the solution space of AX = 0 Step 1: Show zero vector of Rn is in Nul (A) Since Amxn 0nx1 = 0, zero vector of Rn is in Nul(A). Step 2: Show Nul (A) is closed under addition. Let u and w be two vectors from Nul (A). Then Au = 0 and Aw = 0. Show that u + w ∈ Nul (A). Since, A (u + w) = Au + Aw = 0 Conclusion: u + w ∈ Nul(A) Step 3: Show Nul(A) is closed under scalar multiplication. Let u is a vector from Nul(A). Then Au = 0. Show that cu ∈ Nul(A), where c is a scalar. Since, A(cu) = cAu = 0 Conclusion: cu ∈ Nul(A). Therefore, Nul(A) is a subspace of R n. How to check if some vector belongs to the null space of a matrix or not? Step 1: Consider the given vector as the values for the variables in the linear system. Step 2: Evaluate the product of Matrix and the vector. (A v), where v is the given vector. Step 3: If Av = 0, then it belongs to the null space of the matrix A, else it does not. Example: 5 1 −3 −2 Verify if x1 = [ 3 ] ∈ Nul (A) where A = [ ] −5 9 1 −2 Sol: Step 1: Let us consider the given vector as the values for X 5  X=[ 3 ] −2 Step 2: Let us evaluate the product of AX 5 1 −3 −2  [ ][ 3 ] −5 9 1 −2 5− 9+4 0 =[ ]=[ ] −25 + 27 − 2 0 =0 Step 3: Here, the value of Ax1 = 0 Therefore, x1 belongs to the Null space of the matrix A. How to find the basis/ set of all solutions to a given Matrix? Step 1: Reduce the augmented matrix of Ax = 0 into reduced echelon form. Step 2: Decompose the vector giving the general solution into linear combination of vectors where the weights are the free variables. The vectors here form the basis of Nul A Example: Find the spanning set/ basis for the null space of the matrix: −3 6 −1 1 −7 A= [ 1 −2 2 3 −1] 2 −4 5 8 −4 Sol: Consider the augmented matrix of AX = 0  −3 6 −1 1 −7 0 ~ A = [ 1 −2 2 3 −1 0] 2 −4 5 8 −4 0 R2 ↔ R1 1 −2 2 3 −1 0 ~ A = [−3 6 −1 1 −7 0] 2 −4 5 8 −4 0 R2 → R2 + 3R1 ; R3 → R3 – 2R1 Pivot 1 −2 2 3 −1 0 A = [0 0 5 10 −10 0] 0 0 1 2 −2 0 R2 → R2/5 1 −2 2 3 −1 0 A = [0 0 1 2 −2 0] 0 0 1 2 −2 0 Pivot Pivot 1 −2 2 3 −1 0 A = [0 0 1 2 −2 0] 0 0 1 2 −2 0 R3 → R3 – R2 1 −2 2 3 −1 0 A = [0 0 1 2 −2 0] 0 0 0 0 0 0 1 −2 2 3 −1 0 A = [0 0 1 2 −2 0] 0 0 0 0 0 0 R3 R1 → R1 – 2R2 1 −2 0 −1 3 0 A = [0 0 1 2 −2 0] 0 0 0 0 0 0 This is the reduced Echelon form C1 C3  1 −2 0 −1 3 0 A = [0 0 1 2 −2 0] x1 → is a variable corresponding to c1 0 0 0 0 0 0 x3 → is a variable corresponding to c3 Final reduced Echelon form x1, x3 → Basic variables x2, x4, x5 → Free variables Now we need to express basic variables in terms of free variables x3 = -2x4 + 2x5 x1 = 2x2 + x4 – 3x5 𝑥1 2𝑥2 + 𝑥4 − 𝑥5 𝑥2 𝑥2 𝑥3 = −2𝑥4 + 2𝑥5 𝑥4 𝑥4 [𝑥5 ] [ 𝑥5 ] 2 1 −1 1 0 0 x2 0 + x4 −2 + x5 2 0 1 0 [ 0] 2 1 −1 1 0 0 x2 0 + x4 −2 + x5 2 u, v, w are the basis of Nul(A) 0 1 0 [ 0] u v w Column Space of a Matrix: The column space of an m x n matrix A is the set of all linear combinations of the columns of A If A = [a1 … an] Col(A) = Span{a1,…, an} Let b ∈ Col(A) It means b = x1a1 + …. + xnan = Ax 𝑥1 Where, x = [ … ] 𝑥𝑛 Thus Col(A) = {b | b = Ax for some x ∈ Rn Theorem: The column space of an m x n matrix A is a subspace of Rm Proof: The column space of matrix A is all vectors b for which Ax = b has a solution Step 1: Show zero vector of Rm is in Col(A) Since, Am x 1 0n x 1 = 0m x 1, zero vector of Rm is in Col(A) Step 2: Show Col(A) is closed under addition. Let u and w are two vectors from Col(A) Then Ax1 = u and Ax2 = w. Show that u + w ∈ Col(A). Since, A(x1 + x2) = Ax1 + Ax2 = u + w Conclusion u + w ∈ Col(A). Step 3: Show Col(A) is closed under scalar multiplication. Let u is a vector from Col(A). Then Ax = u. We can show that cu ∈ Col(A), where c is a scalar. Since, A(cx) = cAx = cu We conclude cu ∈ Col(A). Thus, Col(A) is a subspace of R m Example: Find a matrix A such that W = Col(A), where Solution: 6𝑎 − 𝑏 W = {[ 𝑎 + 𝑏 ] |𝑎, 𝑏 ∈ ℝ} −7𝑎 6 −1 = Span {[ 1 ] , [ 1 ]} −7 0 6 −1 Thus, A = [ 1 1 ] is the desired matrix. −7 0 Theorem: The column space of an m x n matrix A is all of R m if and only if the equation Ax = b has a solution for each b ∈ Rm. Steps for finding Basis/ set of all linear combinations for Col A: Step 1: Reduce it to the reduced Echelon form. Any linear dependence relation among the columns of A can be expressed as Ax = 0 When matrix A is row reduced to matrix B, - The columns of B differ from A - The same equation Ax = 0 and Bx = 0 have the same set of solutions. Note: Elementary row operations on a matrix do not affect the linear dependence relationship among the columns of the matrix. Step 2: Other columns can be expressed as linear combination of pivot columns. The pivot columns of a matrix A form the basis for Col A. Example: Find a basis for Col A  −3 6 −1 1 −7 A= [ 1 −2 2 3 −1] 2 −4 5 8 −4 In the same previous example, once we have obtained the Reduced Echelon form, we need to identify the pivot columns 1 −2 0 −1 3 [0 0 1 2 −2] R3 0 0 0 0 0 Pivot Columns The corresponding columns C1 and C3 in the original matrix will be the basis for the column space of A C1 C3 −3 6 −1 1 −7 [1 −2 2 3 −1] 2 −4 5 8 −4 −3 −1 {[ 1 ] , [ 2 ]} basis of col(A). 2 5 How to verify if some vector belongs to the Col (A)? We need to consider the given vector as b and represent the situation as AX = b and check if the augmented matrix Ab is consistent or not. If the system is consistent, then the vector b belongs to the Col (A) else it does not. Contrast between Nul (A) and Col (A): 1. If the Null space of A is a subspace of Rk, what is k? If the column space of A is a subspace of Rk, what is k? 2 4 −2 1 A = [−2 −5 7 3] 3 7 −8 6 Answer: The columns of A each have three entries. So, col(A) is linear combinations of column vectors of A. So, it is a subspace of ℝk where k = 3. Answer: The null space of A must be a solution to A3x4 X4x1 = 03x1 So, it is a subspace of ℝk where k = 4. Note: When the matrix is not a square matrix, the column space and null space are subspaces of different vector spaces. Contrast between Nul A and Col A Nul(A) Col(A) A subspace of ℝn A subspace of ℝm Implicitly defined; that is, the vectors in Explicitly defined; that is it is told how to Nul(A) must easily Ax = 0 build vectors in Col(A). Takes time to find the vectors in Nul(A). Easy to find vectors in Col(A) No obvious relation between Nul(A) and An obvious relation between Col(A) and the entries in A. the entries in A. A typical vector v in Nul(A) has the A typical vector in Col(A) has the property that Av = 0. property that Ax=v is consistent. Given a specific vector v, it is easy to Given a specific vector v, it may take time check if v is Nul(A). Just check if Av = 0. to check if v is in Col(A). Need to solve Ax=v. Nul(A) = {0}if and only if the equation Col(A) = ℝm if and only if the equation Ax = 0 has only the trivial solution. Ax = b has a solution for every b ∈ ℝm. Dimension of a Vector Space: Basis: Let H be a subspace of a vector space V. An indexed set of vectors B = {b1, b2, …, bn} in V is a basis for H if: 1. B is a linearly independent set. 2. The subspace spanned by B coincides with H; this is H = Span {b1, b2, …, bn} The unique representation theorem: Let B = {b1, b2, …, bn} be a basis for a vector space V. Then, for each x in V, there exists a unique set of scalars c1, c2, …, cn such that X = c1b1 + c2b2 + … + cnbn The set of scalars c1, c2, …, cn is called the coordinate of x relative to the basis B. Example: 1 1 Consider a basis B = {b1, b2} for R2, where b1 = [ ] and b2 = [ ]. Let x in R2 has 0 2 −2 coordinates relative the basis B, [x]B = [ ]. Find x. 3 An important view of Basis: B is a basis for the vector space V. - If one more vector say w is added to B from V, then the set is:  Not linearly independent because B spans v  An linear combination of the element of B Theorem: Let B = {b1, b2, …, bn} be a basis for a vector space V. Then, any set in V containing more than n vectors must be linearly dependent. Theorem: If a vector space V has a basis of n vectors, then every basis of V must contain exactly n vectors. Note: The basis is not necessarily unique. Dimension of a vector space: If V is a vector space spanned by a basis of n vectors, then its dimension is said to be n.  Finite dimensional: If the basis is of finite size.  Zero dimensional: The dimension of zero vector space {0}  Infinite dimensional: If V is not spanned by a finite set. Example: The subspace of R3 0 – dimensional subspace: The origin 1 – dimensional subspace: a line through origin. 2 – dimensional subspace: subspace spanned by two linearly independent vectors. 3 – dimensional subspace: entire R3 Row space & Rank Theorem: Row space: The set of all linear combinations of the row vectors of a matrix is called the row space of A. It is denoted as Row A. Since, each vector is a vector in R n, Row A is a subspace of Rn. Example: Consider the following matrix: 1 −2 3 2 1 1 −1 2 7 −3 A= [ ] 1 0 1 12 −7 1 −2 3 3 3 Here, the matrix has four row vectors r1 = [1 −2 3 2 1] r2 = [1 −1 2 7 −3] r3 = [1 0 1 12 −7] r4 = [1 −2 3 3 3] Here, each row is a vector in R5 Here, Row A = Span {r1, r2, r3, r4} How to find the basis of Row A? Theorem: If two matrices A and B are row equivalent, then their row spaces are the same. If B is in echelon form, the nonzero rows of B form a basis for the row space of A as well as for that of B. Step 1: Reduce the matrix to echelon form. Step 2: Report the nonzero rows as the basis of Row A. 1 −2 3 2 1 1 −1 2 7 −3 A= [ ] 1 0 1 12 −7 1 −2 3 3 3 Problem: 1 −2 3 2 1 1 −1 2 7 −3 1. If A = [ ] 1 0 1 12 −7 1 −2 3 3 3 Find the basis of Row A Rank of a Matrix: The rank of a matrix A is the dimension of the column space of A. 1 −2 3 2 1 1 −1 2 7 −3 A= [ ] 1 0 1 12 −7 1 −2 3 3 3 Solution: Step 1: Reduce it to echelon form 1 0 1 12 −7 0 1 −1 5 −4 A= [ ] 0 0 0 1 2 0 0 0 0 0 Step 2: Report the nonzero rows as the basis of Row A. 1 0 1 12 −7 0 1 −1 5 −4 A= [ ] 0 0 0 1 2 0 0 0 0 0 (1, 0, 1, 12, −7 ), Basis for Row A = {(0, 1, −1, 5, −4),} (0, 0, 0, 1 ,2) The Rank theorem: The dimension of the column space and the row space of an m x n matrix A are equal. This common dimension, the rank of A, also equals the number of pivot positions in A and satisfy the equation Rank A + Dim Nul A = n Examples:  Could a 6 x 9 matrix have a two-dimensional null space?  If the 6 x 9 matrix has a two-dimensional null space, then the rank of the matrix is 9 – 2 = 7  Columns of this matrix has only 6 entries => it is a vector in R6  Dimension of columns space of this matrix cannot exceed 6. The invertible matrix theorem: According to the notion of a matrix being invertible, the matrix is invertible if and only if | A | ≠ 0.  𝑎𝑑𝑗(𝐴) If | A | ≠ 0, then the matrix is singular and not invertible since, A -1 = |𝐴| The invertible matrix theorem gives equivalent conditions for the inverse to exist. Let A be a square matrix of the order m x n. Then the following statements are equivalent. That is, for a given A, the statements are either all true or all false. 1. A is an invertible matrix. 2. A is row equivalent to the n x n identity matrix. 3. A has n pivot positions. 4. The equation Ax = 0 has only the trivial solution. 5. The columns of A form a linearly independent set. 6. The columns of A form a basis of Rn. 7. Col A = Rn 8. Dim Col A = n. 9. Rank A = n 10. Nul A = {0} 11. Dim Nul A = 0  Week 4 Reading Material Eigen Values and Eigen Vectors: Matrices as Linear Transformations: Consider the vector (x, y) rotated by an angle θ clockwise to (x’, y’) Here, x = r cos Φ; y = r sin Φ x’ = r cos (Φ + θ); y = r sin (Φ + θ)  x’ = r [cos(Φ).cos(θ) – sin(Φ). Sin(θ)] = r cos(Φ).cos(θ) - r sin(Φ). Sin(θ)  y’ = r [sin(Φ). cos(θ) – cos(Φ). Sin(θ)] = r sin(Φ). cos(θ) – cos(Φ). Sin(θ) Here, we can rewrite x’ and y’ as: x’ = x cos(θ) – y sin(θ) y’ = x sin (θ) + y cos (θ) If we try to rewrite these equations in the form of matrix notation, cos⁡(𝜃) −sin⁡(𝜃) 𝑥 𝑥′ [ ] [𝑦 ] = [ ] sin⁡(𝜃) cos⁡(𝜃) 𝑦′ Rotation matrix Eigenvector: - A transformation may move vectors in a variety of directions.  - There are special vectors on which the action of the matrix A is simply to scale the vector. - These vectors are of particular interest because of their use in many applications Example: Consider the matrix A and the vector u, where 1 −2 −1 A=[ ] and u = [ ] 0 3 1 If we computer the product Au, then it is 1 −2 −1 −1 − 2 −3 −1 Au = [ ][ ] =⁡[ ]=[ ]=3[ ]=3u 0 3 1 0+3 3 1 Eigenvector and Eigenvalue definitions: An eigenvector of an n x n matrix A is a nonzero vector x such that Ax = λx for some scalar λ. A scalar λ is called an eigenvalue of A if there is a nontrivial solution x of Ax = λx; such an x is called an eigenvector corresponding to eigenvalue λ. Example: Consider the matrix A and vectors u and v, where, 1 −2 1 3 A=[ ]; u = [ ] ; v = [ ]. Verify if u and v are eigenvectors of A. 0 1 0 4 Solution: Verifying using the definition of eigenvector. 1 −2 1 1 Au = [ ] [ ] = [ ] = 1.u 0 1 0 0 So, u is an eigenvector corresponding to the eigenvalue 1. 1 −2 3 −5 Av = [ ]⁡[ ] = [ ] ≠ λ.v 0 1 4 4 Here, v is not an eigenvector. Examples of Eigenvectors and Eigenvalues: 1 2 1. Show that 3 is an Eigenvalue of the matrix A = [ ]. Find the corresponding 0 3 eigenvector. Solution: The scalar 3 is an eigenvalue of A if and only if Ax = 3x has a nontrivial solution. Ax = 3x ⇒ Ax – 3x = 0 ⇒ (A – 3I)x = 0 This is a homogeneous equation. 1 2 1 0 𝑥1 ([ ] ⁡ − ⁡⁡3 [ ]) [ ] = 0 0 3 0 1 𝑥2 1⁡ − ⁡⁡3 2⁡ − ⁡⁡0 𝑥1 ⇒ ([ ⁡⁡]) [𝑥 ] = 0 0⁡ − ⁡⁡0 3⁡ − ⁡⁡3 2 −2 2 𝑥1 ⇒ ([ ]) [ ] = 0 0 0 𝑥2 ⇒ -2x1 + 2x2 = 0 ⇒ x1 = x2 x2 = free variable and x1 = basic variable 𝑥1 1 If x2 = 1, [𝑥 ] = ⁡[ ] , a non-trivial solution. 2 1 Eigenvector corresponding to the eigenvalue 3 for the given matrix. 𝑥1 2 Note that [𝑥 ] = ⁡[ ] is also a solution. 2 2 Eigenspace: In general, λ is an eigenvalue of A if and only if the equation (A – λI) x = 0 Has a nontrivial solution. The set of all solutions is just the null space of the matrix (A – λI), which is a subspace of Rn. This subspace is called eigensp