Lecture notes on probability statistics and linear algebra

how is linear algebra applied and how hard is linear algebra compared to calculus and how much linear algebra for machine learning,how to algebra linear equations
LexiWills Profile Pic
LexiWills,United Kingdom,Professional
Published Date:31-07-2017
Your Website URL(Optional)
Comment
LINEAR ALGEBRA W W L CHEN c W W L Chen, 1982, 2008. This chapter originates from material used by the author at Imperial College, University of London, between 1981 and 1990. It is available free to all individuals, on the understanding that it is not to be used for nancial gain, and may be downloaded and/or photocopied, with or without permission from the author. However, this document may not be kept on any information storage and retrieval system without permission from the author, unless such system is not accessible to any individuals other than its owners. Chapter 1 LINEAR EQUATIONS 1.1. Introduction Example 1.1.1. Try to draw the two lines 3x + 2y = 5; 6x + 4y = 5: It is easy to see that the two lines are parallel and do not intersect, so that this system of two linear equations has no solution. Example 1.1.2. Try to draw the two lines 3x + 2y = 5; x + y = 2: It is easy to see that the two lines are not parallel and intersect at the point (1; 1), so that this system of two linear equations has exactly one solution. Example 1.1.3. Try to draw the two lines 3x + 2y = 5; 6x + 4y = 10: It is easy to see that the two lines overlap completely, so that this system of two linear equations has in nitely many solutions. Chapter 1 : Linear Equations page 1 of 31c Linear Algebra W W L Chen, 1982, 2008 2 In these three examples, we have shown that a system of two linear equations on the plane R may have no solution, one solution or in nitely many solutions. A natural question to ask is whether there can be any other conclusion. Well, we can see geometrically that two lines cannot intersect at more than one point without overlapping completely. Hence there can be no other conclusion. In general, we shall study a system of m linear equations of the form a x + a x +::: + a x = b ; 11 1 12 2 1n n 1 a x + a x +::: + a x = b ; 21 1 22 2 2n n 2 (1) . . . a x +a x +::: +a x =b ; m1 1 m2 2 mn n m with n variables x ;x ;:::;x . Here we may not be so lucky as to be able to see geometrically what is 1 2 n going on. We therefore need to study the problem from a more algebraic viewpoint. In this chapter, we shall con ne ourselves to the simpler aspects of the problem. In Chapter 6, we shall study the problem again from the viewpoint of vector spaces. If we omit reference to the variables, then system (1) can be represented by the array 0 1 a a ::: a b 11 12 1n 1 Ba a ::: a b C 21 22 2n 2 B C (2) . . . . A . . . . . . . . a a ::: a b m1 m2 mn m of all the coecients. This is known as the augmented matrix of the system. Here the rst row of the array represents the rst linear equation, and so on. We also write Ax =b, where 0 1 0 1 a a ::: a b 11 12 1n 1 Ba a ::: a C Bb C 21 22 2n 2 B C B C A = and b = . . . . A A . . . . . . . . a a ::: a b m1 m2 mn m represent the coecients and 0 1 x 1 Bx C 2 B C x = . A . . x n represents the variables. Example 1.1.4. The array 0 1 1 3 1 5 1 5 A 0 1 1 2 1 4 (3) 2 4 0 7 1 3 represents the system of 3 linear equations x + 3x +x + 5x +x = 5; 1 2 3 4 5 x +x + 2x +x = 4; (4) 2 3 4 5 2x + 4x + 7x +x = 3; 1 2 4 5 Chapter 1 : Linear Equations page 2 of 31c Linear Algebra W W L Chen, 1982, 2008 with 5 variables x ;x ;x ;x ;x . We can also write 1 2 3 4 5 0 1 x 1 0 1 0 1 1 3 1 5 1 x 5 B C 2 B C A A 0 1 1 2 1 x = 4 : B C 3 A 2 4 0 7 1 x 3 4 x 5 1.2. Elementary Row Operations Let us continue with Example 1.1.4. Example 1.2.1. Consider the array (3). Let us interchange the rst and second rows to obtain 0 1 0 1 1 2 1 4 A 1 3 1 5 1 5 : 2 4 0 7 1 3 Then this represents the system of equations x +x + 2x +x = 4; 2 3 4 5 x + 3x +x + 5x +x = 5; (5) 1 2 3 4 5 2x + 4x + 7x +x = 3; 1 2 4 5 essentially the same as the system (4), the only di erence being that the rst and second equations have been interchanged. Any solution of the system (4) is a solution of the system (5), and vice versa. Example 1.2.2. Consider the array (3). Let us add 2 times the second row to the rst row to obtain 0 1 1 5 3 9 3 13 A 0 1 1 2 1 4 : 2 4 0 7 1 3 Then this represents the system of equations x + 5x + 3x + 9x + 3x = 13; 1 2 3 4 5 x + x + 2x + x = 4; (6) 2 3 4 5 2x + 4x + 7x + x = 3; 1 2 4 5 essentially the same as the system (4), the only di erence being that we have added 2 times the second equation to the rst equation. Any solution of the system (4) is a solution of the system (6), and vice versa. Example 1.2.3. Consider the array (3). Let us multiply the second row by 2 to obtain 0 1 1 3 1 5 1 5 A 0 2 2 4 2 8 : 2 4 0 7 1 3 Then this represents the system of equations x + 3x + x + 5x + x = 5; 1 2 3 4 5 2x + 2x + 4x + 2x = 8; (7) 2 3 4 5 2x + 4x + 7x + x = 3; 1 2 4 5 Chapter 1 : Linear Equations page 3 of 31c Linear Algebra W W L Chen, 1982, 2008 essentially the same as the system (4), the only di erence being that the second equation has been multiplied through by 2. Any solution of the system (4) is a solution of the system (7), and vice versa. In the general situation, it is not dicult to see the following. PROPOSITION 1A. (ELEMENTARY ROW OPERATIONS) Consider the array (2) corresponding to the system (1). (a) Interchanging the i-th and j-th rows of (2) corresponds to interchanging the i-th and j-th equations in (1). (b) Adding a multiple of the i-th row of (2) to the j-th row corresponds to adding the same multiple of the i-th equation in (1) to the j-th equation. (c) Multiplying the i-th row of (2) by a non-zero constant corresponds to multiplying the i-th equation in (1) by the same non-zero constant. In all three cases, the collection of solutions to the system (1) remains unchanged. Let us investigate how we may use elementary row operations to help us solve a system of linear equations. As a rst step, let us continue again with Example 1.1.4. Example 1.2.4. Consider again the system of linear equations x + 3x +x + 5x +x = 5; 1 2 3 4 5 x +x + 2x +x = 4; (8) 2 3 4 5 2x + 4x + 7x +x = 3; 1 2 4 5 represented by the array 0 1 1 3 1 5 1 5 A 0 1 1 2 1 4 : (9) 2 4 0 7 1 3 Let us now perform elementary row operations on the array (9). At this point, do not worry if you do not understand why we are taking the following steps. Adding2 times the rst row of (9) to the third row, we obtain 0 1 1 3 1 5 1 5 A 0 1 1 2 1 4 : 0 2 2 3 1 7 From here, we add 2 times the second row to the third row to obtain 0 1 1 3 1 5 1 5 A 0 1 1 2 1 4 : (10) 0 0 0 1 1 1 Next, we add3 times the second row to the rst row to obtain 0 1 1 0 2 1 2 7 A 0 1 1 2 1 4 : 0 0 0 1 1 1 Next, we add the third row to the rst row to obtain 0 1 1 0 2 0 1 6 A 0 1 1 2 1 4 : 0 0 0 1 1 1 Chapter 1 : Linear Equations page 4 of 31c Linear Algebra W W L Chen, 1982, 2008 Finally, we add2 times the third to row to the second row to obtain 0 1 1 0 2 0 1 6 A 0 1 1 0 1 2 : (11) 0 0 0 1 1 1 We remark here that the array (10) is said to be in row echelon form, while the array (11) is said to be in reduced row echelon form precise de nitions will follow in Sections 1.51.6. Let us see how we may solve the system (8) by using the arrays (10) or (11). First consider (10). Note that this represents the system x + 3x +x + 5x +x = 5; 1 2 3 4 5 x +x + 2x +x = 4; (12) 2 3 4 5 x +x = 1: 4 5 First of all, take the third equation x +x = 1: 4 5 If we let x =t, then x = 1t. Substituting these into the second equation, we obtain (you must do 5 4 the calculation here) x +x = 2 +t: 2 3 If we let x =s, then x = 2 +ts. Substituting all these into the rst equation, we obtain (you must 3 2 do the calculation here) x =6 +t + 2s: 1 Hence x = (x ;x ;x ;x ;x ) = (6 +t + 2s; 2 +ts;s; 1t;t) 1 2 3 4 5 is a solution of the system (12) for everys;t2R. In view of Proposition 1A, these are also precisely the solutions of the system (8). Alternatively, consider (11) instead. Note that this represents the system x 2x x =6; 1 3 5 x + x x = 2; (13) 2 3 5 x +x = 1: 4 5 First of all, take the third equation x +x = 1: 4 5 If we let x =t, then x = 1t. Substituting these into the second equation, we obtain (you must do 5 4 the calculation here) x +x = 2 +t: 2 3 If we let x =s, then x = 2 +ts. Substituting all these into the rst equation, we obtain (you must 3 2 do the calculation here) x =6 +t + 2s: 1 Hence x = (x ;x ;x ;x ;x ) = (6 +t + 2s; 2 +ts;s; 1t;t) 1 2 3 4 5 Chapter 1 : Linear Equations page 5 of 31c Linear Algebra W W L Chen, 1982, 2008 is a solution of the system (13) for every s;t2 R. In view of Proposition 1A, these are also precisely the solutions of the system (8). However, if you have done the calculations as suggested, you will notice that the calculation is easier for the system (13) than for the system (12). This is clearly a case of the array (11) in reduced row echelon form having more 0's than the array (10) in row echelon form, so that the system (13) has fewer non-zero coecients than the system (12). 1.3. Row Echelon Form Definition. A rectangular array of numbers is said to be in row echelon form if the following conditions are satis ed: (1) The left-most non-zero entry of any non-zero row has value 1. These are called the pivot entries. (2) All zero rows are grouped together at the bottom of the array. (3) The pivot entry of a non-zero row occurring lower in the array is to the right of the pivot entry of a non-zero row occurring higher in the array. Next, we investigate how we may reduce a given array to row echelon form. We shall illustrate the ideas by working on an example. Example 1.3.1. Consider the array 0 1 0 0 5 0 15 5 0 2 4 7 1 3 B C : A 0 1 2 3 0 1 0 1 2 4 1 2 Step 1: Locate the left-most non-zero column and cover all columns to the left of this column (in our illustration here, denotes an entry that has been covered). We now have 0 1  0 5 0 15 5  2 4 7 1 3 B C : A  1 2 3 0 1  1 2 4 1 2 Step 2: Consider the part of the array that remains uncovered. By interchanging rows if necessary, ensure that the top-left entry is non-zero. So let us interchange rows 1 and 4 to obtain 0 1  1 2 4 1 2  2 4 7 1 3 B C : A  1 2 3 0 1  0 5 0 15 5 Step 3: If the top entry on the left-most uncovered column isa, then we multiply the top uncovered row by 1=a to ensure that this entry becomes 1. So let us divide row 1 by 1 to obtain 0 1  1 2 4 1 2  2 4 7 1 3 B C A  1 2 3 0 1  0 5 0 15 5 Step 4: We now try to make all entries below the top entry on the left-most uncovered column zero. This can be achieved by adding suitable multiples of row 1 to the other rows. So let us add2 times row 1 to row 2 to obtain 0 1  1 2 4 1 2  0 0 1 1 1 B C : A  1 2 3 0 1  0 5 0 15 5 Chapter 1 : Linear Equations page 6 of 31c Linear Algebra W W L Chen, 1982, 2008 Then let us add1 times row 1 to row 3 to obtain 0 1  1 2 4 1 2  0 0 1 1 1 B C : A  0 0 1 1 1  0 5 0 15 5 Step 5: Now cover the top row. We then obtain 0 1        0 0 1 1 1 B C : A  0 0 1 1 1  0 5 0 15 5 Step 6: Repeat Steps 15 on the uncovered array, and as many times as necessary so that eventually the whole array gets covered. So let us continue. Following Step 1, we locate the left-most non-zero column and cover all columns to the left of this column. We now have 0 1         0 1 1 1 B C : A   0 1 1 1   5 0 15 5 Following Step 2, we interchanging rows if necessary to ensure that the top-left entry is non-zero. So let us interchange rows 1 and 3 (here we do not count any covered rows) to obtain 0 1         5 0 15 5 B C : A   0 1 1 1   0 1 1 1 Following Step 3, we multiply the top row by a suitable number to ensure that the top entry on the left-most uncovered column becomes 1. So let us multiply row 1 by 1=5 to obtain 0 1       B  1 0 3 1 C : A   0 1 1 1   0 1 1 1 Following Step 4, we do nothing Following Step 5, we cover the top row. We then obtain 0 1       B      C A:   0 1 1 1   0 1 1 1 Following Step 1, we locate the left-most non-zero column and cover all columns to the left of this column. We now have 0 1             B C : A    1 1 1    1 1 1 Following Step 2, we do nothing Following Step 3, we multiply the top row by a suitable number to ensure that the top entry on the left-most uncovered column becomes 1. So let us multiply row 1 by1 to obtain 0 1             B C : A    1 1 1    1 1 1 Chapter 1 : Linear Equations page 7 of 31c Linear Algebra W W L Chen, 1982, 2008 Following Step 4, we now try to make all entries below the top entry on the left-most uncovered column zero. So let us add row 1 to row 2 to obtain 0 1             B C : A    1 1 1    0 0 0 Following Step 5, we cover the top row. We then obtain 0 1       B     C : A          0 0 0 Following Step 1, we locate the left-most non-zero column and cover all columns to the left of this column. We now have 0 1       B     C A:             Step1. Uncover everything We then have 0 1 0 1 2 4 1 2 0 0 1 0 3 1 B C ; A 0 0 0 1 1 1 0 0 0 0 0 0 in row echelon form. In practice, we do not actually cover any entries of the array, so let us repeat here the same argument without covering anything the reader is advised to compare this with the earlier discussion. We start with the array 0 1 0 0 5 0 15 5 B 0 2 4 7 1 3C : A 0 1 2 3 0 1 0 1 2 4 1 2 Interchanging rows 1 and 4, we obtain 0 1 0 1 2 4 1 2 B 0 2 4 7 1 3C : A 0 1 2 3 0 1 0 0 5 0 15 5 Adding2 times row 1 to row 2, and adding1 times row 1 to row 3, we obtain 0 1 0 1 2 4 1 2 0 0 0 1 1 1 B C : A 0 0 0 1 1 1 0 0 5 0 15 5 Interchanging rows 2 and 4, we obtain 0 1 0 1 2 4 1 2 0 0 5 0 15 5 B C : A 0 0 0 1 1 1 0 0 0 1 1 1 Chapter 1 : Linear Equations page 8 of 31c Linear Algebra W W L Chen, 1982, 2008 Multiplying row 1 by 1=5, we obtain 0 1 0 1 2 4 1 2 B 0 0 1 0 3 1 C : A 0 0 0 1 1 1 0 0 0 1 1 1 Multiplying row 3 by1, we obtain 0 1 0 1 2 4 1 2 B 0 0 1 0 3 1 C : A 0 0 0 1 1 1 0 0 0 1 1 1 Adding row 3 to row 4, we obtain 0 1 0 1 2 4 1 2 B 0 0 1 0 3 1C ; A 0 0 0 1 1 1 0 0 0 0 0 0 in row echelon form. Remarks. (1) As already observed earlier, we do not actually physically cover rows or columns. In any practical situation, we simply copy these entries without changes. (2) The steps indicated the the rst part of the last example are for guidance only. In practice, we do not have to follow the steps above religiously, and what we do is to a great extent dictated by good common sense. For instance, suppose that we are faced with the array   2 3 2 1 : 3 2 0 2 If we follow the steps religiously, then we shall multiply row 1 by 1=2. However, note that this will introduce fractions to some entries of the array, and any subsequent calculation will become rather messy. Instead, let us multiply row 1 by 3 to obtain   6 9 6 3 : 3 2 0 2 Then let us multiply row 2 by 2 to obtain   6 9 6 3 : 6 4 0 4 Adding1 times row 1 to row 2, we obtain   6 9 6 3 : 0 5 6 1 In this way, we have avoided the introduction of fractions until later in the process. In general, if we start with an array with integer entries, then it is possible to delay the introduction of fractions by omitting Step 3 until the very end. Chapter 1 : Linear Equations page 9 of 31c Linear Algebra W W L Chen, 1982, 2008 Example 1.3.2. Consider the array 0 1 2 1 3 2 5 A 1 3 2 4 1 : 3 2 0 0 2 Try following the steps indicated in the rst part of the previous example religiously and try to see how complicated the calculations get. On the other hand, we can modify the steps with some common sense. First of all, we interchange rows 1 and 2 to obtain 0 1 1 3 2 4 1 A 2 1 3 2 5 : 3 2 0 0 2 The reason for taking this step is to put an entry 1 at the top left without introducing fractions anywhere. When we next add multiples of row 1 to the other rows to make 0's below this 1, we do not introduce fractions either. Now adding2 times row 1 to row 2, we obtain 0 1 1 3 2 4 1 A 0 5 1 6 3 : 3 2 0 0 2 Adding3 times row 1 to row 3, we obtain 0 1 1 3 2 4 1 A 0 5 1 6 3 : 0 7 6 12 1 Next, multiplying row 2 by7, we obtain 0 1 1 3 2 4 1 A 0 35 7 42 21 : 0 7 6 12 1 Multiplying row 3 by5, we obtain 0 1 1 3 2 4 1 A 0 35 7 42 21 : 0 35 30 60 5 Note that here we are essentially covering up row 1. Also, we have multiplied rows 2 and 3 by suitable multiples to that their leading non-zero entries are the same, in preparation for taking the next step without introducing fractions. Now adding1 times row 2 to row 3, we obtain 0 1 1 3 2 4 1 A 0 35 7 42 21 : 0 0 23 18 26 Here, the array is almost in row echelon form, except that the leading non-zero entries in rows 2 and 3 are not equal to 1. However, we can always multiply row 2 by 1=35 and row 3 by 1=23 if we want to obtain the row echelon form 0 1 1 3 2 4 1 A 0 1 1=5 6=5 3=5 : 0 0 1 18=23 26=23 If this di ers from the answer you got when you followed the steps indicated in the previous example religiously, do not worry. row echelon forms are not unique Chapter 1 : Linear Equations page 10 of 31c Linear Algebra W W L Chen, 1982, 2008 1.4. Reduced Row Echelon Form Definition. A rectangular array of numbers is said to be in reduced row echelon form if the following conditions are satis ed: (1) The left-most non-zero entry of any non-zero row has value 1. These are called the pivot entries. (2) All zero rows are grouped together at the bottom of the array. (3) The pivot entry of a non-zero row occurring lower in the array is to the right of the pivot entry of a non-zero row occurring higher in the array. (4) Each column containing a pivot entry has 0's everywhere else in the column. We now investigate how we may reduce a given array to reduced row echelon form. Here, we basically take an extra step to convert an array from row echelon form to reduced row echelon form. We shall illustrate the ideas by continuing on an earlier example. Example 1.4.1. Consider again the array 0 1 0 0 5 0 15 5 B 0 2 4 7 1 3C : A 0 1 2 3 0 1 0 1 2 4 1 2 We have already shown in Example 1.3.1 that this array can be reduced to row echelon form 0 1 0 1 2 4 1 2 0 0 1 0 3 1 B C : A 0 0 0 1 1 1 0 0 0 0 0 0 Step 1: Cover all zero rows at the bottom of the array. We now have 0 1 0 1 2 4 1 2 B 0 0 1 0 3 1C : A 0 0 0 1 1 1       Step 2: We now try to make all the entries above the pivot entry on the bottom row zero (here again we do not count any covered rows). This can be achieved by adding suitable multiples of the bottom row to the other rows. So let us add4 times row 3 to row 1 to obtain 0 1 0 1 2 0 3 2 B 0 0 1 0 3 1 C : A 0 0 0 1 1 1       Step 3: Now cover the bottom row. We then obtain 0 1 0 1 2 0 3 2 B 0 0 1 0 3 1 C A:             Step 4: Repeat Steps 23 on the uncovered array, and as many times as necessary so that eventually the whole array gets covered. So let us continue. Following Step 2, we add2 times row 2 to row 1 to obtain 0 1 0 1 0 0 9 4 0 0 1 0 3 1 B C : A             Chapter 1 : Linear Equations page 11 of 31c Linear Algebra W W L Chen, 1982, 2008 Following Step 3, we cover row 2 to obtain 0 1 0 1 0 0 9 4 B      C : A             Following Step 2, we do nothing Following Step 3, we cover row 1 to obtain 0 1             B C : A             Step1. Uncover everything We then have 0 1 0 1 0 0 9 4 0 0 1 0 3 1 B C ; A 0 0 0 1 1 1 0 0 0 0 0 0 in reduced row echelon form. Again, in practice, we do not actually cover any entries of the array, so let us repeat here the same argument without covering anything the reader is advised to compare this with the earlier discussion. We start with the row echelon form 0 1 0 1 2 4 1 2 B 0 0 1 0 3 1C : A 0 0 0 1 1 1 0 0 0 0 0 0 Adding4 times row 3 to row 1, we obtain 0 1 0 1 2 0 3 2 0 0 1 0 3 1 B C : A 0 0 0 1 1 1 0 0 0 0 0 0 Adding2 times row 2 to row 1, we obtain 0 1 0 1 0 0 9 4 B 0 0 1 0 3 1 C ; A 0 0 0 1 1 1 0 0 0 0 0 0 in reduced row echelon form. 1.5. Solving a System of Linear Equations Let us rst summarize what we have done so far. We study a system (1) of m linear equations in n variables x ;:::;x . If we omit reference to the variables, then the system (1) can be represented by 1 n the array (2), with m rows and n + 1 columns. We next reduce the array (2) to row echelon form or reduced row echelon form by elementary row operations. By Proposition 1A, the system of linear equations represented by the array in row echelon form or reduced row echelon form has the same solution set as the system (1). It follows that to solve the system Chapter 1 : Linear Equations page 12 of 31c Linear Algebra W W L Chen, 1982, 2008 (1), it remains to solve the system represented by the array in row echelon form or reduced row echelon form. We now describe a simple way to obtain all solutions of this system. Definition. Any column of an array (2) in row echelon form or reduced row echelon form containing a pivot entry is called a pivot column. First of all, let us eliminate the situation when the system has no solutions. Suppose that the array (2) has been reduced to row echelon form, and that this contains a row of the form 0 ::: 0 1 z n corresponding to the last column of the array being a pivot column. This row represents the equation 0x +::: + 0x = 1; 1 n clearly the system cannot have any solution. Definition. Suppose that the array (2) in row echelon form or reduced row echelon form satis es the condition that its last column is not a pivot column. Then any variable x corresponding to a pivot i column is called a pivot variable. All other variables are called free variables. Example 1.5.1. Consider the array 0 1 0 1 0 0 9 4 B 0 0 1 0 3 1 C ; A 0 0 0 1 1 1 0 0 0 0 0 0 representing the system x 9x =4; 2 5 x + 3x = 1; 3 5 x + x = 1: 4 5 Note that the zero row in the array represents an equation which is trivial Here the last column of the array is not a pivot column. Now columns 2; 3; 4 are the pivot columns, so that x ;x ;x are the pivot 2 3 4 variables and x ;x are the free variables. 1 5 To solve the system, we allow the free variables to take any values we choose, and then solve for the pivot variables in terms of the values of these free variables. Example 1.5.2. Consider the system of 4 linear equations 5x + 15x = 5; 3 5 2x + 4x + 7x + x = 3; 2 3 4 5 (14) x + 2x + 3x = 1; 2 3 4 x + 2x + 4x + x = 2; 2 3 4 5 in the 5 variables x ;x ;x ;x ;x . If we omit reference to the variables, then the system can be repre- 1 2 3 4 5 sented by the array 0 1 0 0 5 0 15 5 0 2 4 7 1 3 B C : (15) A 0 1 2 3 0 1 0 1 2 4 1 2 Chapter 1 : Linear Equations page 13 of 31c Linear Algebra W W L Chen, 1982, 2008 As in Example 1.3.1, we can reduce the array (15) to row echelon form 0 1 0 1 2 4 1 2 0 0 1 0 3 1 B C ; (16) A 0 0 0 1 1 1 0 0 0 0 0 0 representing the system x + 2x + 4x + x = 2; 2 3 4 5 x + 3x = 1; (17) 3 5 x + x = 1: 4 5 Alternatively, as in Example 1.4.1, we can reduce the array (15) to reduced row echelon form 0 1 0 1 0 0 9 4 0 0 1 0 3 1 B C ; (18) A 0 0 0 1 1 1 0 0 0 0 0 0 representing the system x 9x =4; 2 5 x + 3x = 1; (19) 3 5 x + x = 1: 4 5 By Proposition 1A, the three systems (14), (17) and (19) have exactly the same solution set. Now, we observe from (16) or (18) that columns 2; 3; 4 are the pivot columns, so that x ;x ;x are the pivot 2 3 4 variables and x ;x are the free variables. If we assign values x = s and x = t, then we have, from 1 5 1 5 (17) (harder) or (19) (easier), that (x ;x ;x ;x ;x ) = (s; 9t 4;3t + 1;t + 1;t): (20) 1 2 3 4 5 It follows that (20) is a solution of the system (14) for every s;t2R. Example1.5.3. Let us return to Example 1.2.4, and consider again the system (8) of 3 linear equations in the 5 variablesx ;x ;x ;x ;x . If we omit reference to the variables, then the system can be represented 1 2 3 4 5 by the array (9). We can reduce the array (9) to row echelon form (10), representing the system (12). Alternatively, we can reduce the array (9) to reduced row echelon form (11), representing the system (13). By Proposition 1A, the three systems (8), (12) and (13) have exactly the same solution set. Now, we observe from (10) or (11) that columns 1; 2; 4 are the pivot columns, so that x ;x ;x are the pivot 1 2 4 variables and x ;x are the free variables. If we assign values x = s and x = t, then we have, from 3 5 3 5 (12) (harder) or (13) (easier), that (x ;x ;x ;x ;x ) = (6 +t + 2s; 2 +ts;s; 1t;t): (21) 1 2 3 4 5 It follows that (21) is a solution of the system (8) for every s;t2R. Example 1.5.4. In this example, we do not bother even to reduce the matrix to row echelon form. Consider the system of 3 linear equations 2x + x + 3x + 2x = 5; 1 2 3 4 x + 3x + 2x + 4x = 1; (22) 1 2 3 4 3x + 2x = 2; 1 2 Chapter 1 : Linear Equations page 14 of 31c Linear Algebra W W L Chen, 1982, 2008 in the 4 variablesx ;x ;x ;x . If we omit reference to the variables, then the system can be represented 1 2 3 4 by the array 0 1 2 1 3 2 5 A 1 3 2 4 1 : (23) 3 2 0 0 2 As in Example 1.3.2, we can reduce the array (23) to the form 0 1 1 3 2 4 1 A 0 35 7 42 21 ; (24) 0 0 23 18 26 representing the system x + 3x + 2x + 4x = 1; 1 2 3 4 35x + 7x + 42x =21; (25) 2 3 4 23x + 18x = 26: 3 4 Note that the array (24) is almost in row echelon form, except that the pivot entries are not 1. By Proposition 1A, the two systems (22) and (25) have exactly the same solution set. Now, we observe from (24) that columns 1; 2; 3 are the pivot columns, so that x ;x ;x are the pivot variables and x is 1 2 3 4 the free variable. If we assign values x =s, then we have, from (25), that 4   16 28 24 19 18 26 (x ;x ;x ;x ) = s + ; s ; s + ;s : (26) 1 2 3 4 23 23 23 23 23 23 It follows that (26) is a solution of the system (22) for every s2R. 1.6. Homogeneous Systems Consider a homogeneous system of m linear equations of the form a x + a x +::: + a x = 0; 11 1 12 2 1n n a x + a x +::: + a x = 0; 21 1 22 2 2n n (27) . . . a x +a x +::: +a x = 0; m1 1 m2 2 mn n withn variablesx ;x ;:::;x . If we omit reference to the variables, then system (27) can be represented 1 2 n by the array 0 1 a a ::: a 0 11 12 1n a a ::: a B 0C 21 22 2n B C . (28) . . . .A . . . . . . . 0 a a ::: a m1 m2 mn of all the coecients. Note that the system (27) always has a solution, namely the trivial solution x =x =::: =x = 0: 1 2 n Indeed, if we reduce the array (28) to row echelon form or reduced row echelon form, then it is not dicult to see that the last column is a zero column and so cannot be a pivot column. Chapter 1 : Linear Equations page 15 of 31c Linear Algebra W W L Chen, 1982, 2008 On the other hand, if the system (27) has a non-trivial solution, then we can multiply this solution by any non-zero real number di erent from 1 to obtain another non-trivial solution. We have therefore proved the following simple result. PROPOSITION 1B. The homogeneous system (27) either has the trivial solution as its only solution or has in nitely many solutions. The purpose of this section is to discuss the following stronger result. PROPOSITION 1C. Suppose that the system (27) has more variables than equations; in other words, suppose that nm. Then there are in nitely many solutions. To see this, let us consider the array (28) representing the system (27). Note that (28) has m rows, corresponding to the number of equations. Also (28) has n + 1 columns, where n is the number of variables. However, the column of (28) on the extreme right is a zero column, corresponding to the fact that the system is homogeneous. Furthermore, this column remains a zero column if we perform elementary row operations on the array (28). If we now reduce (28) to row echelon form by elementary row operations, then there are at mostm pivot columns, since there are onlym equations in (27) andm rows in (28). It follows that if we exclude the zero column on the extreme right, then the remaining n columns cannot all be pivot columns. Hence at least one of the variables is a free variable. By assigning this free variable arbitrary real values, we end up with in nitely many solutions for the system (27). 1.7. Application to Network Flow Systems of linear equations arise when we investigate the ow of some quantity through a network. Such networks arise in science, engineering and economics. Two such examples are the pattern of trac ow through a city and distribution of products from manufacturers to consumers through a network of wholesalers and retailers. A network consists of a set of points, called the nodes, and directed lines connecting some or all of the nodes. The ow is indicated by a number or a variable. We observe the following basic assumptions: c Linear Algebra WWL Chen, 1982, 2006  The total ow into a node is equal to the total ow out of a node.  The total ow into the network is equal to the total ow out of the network. Example 1.7.1. The picture below represents a system of one way streets in a particular part of some Example 1.7.1. The picture below represents a system of one way streets in a particular part of some city and the trac ow along the streets between the junctions: city and the traffic flow along the streets between the junctions: x 200 1 200 Ax B 300 2 x x 3 4 300 Cx D 500 5 400 300 Chapter 1 : Linear Equations page 16 of 31 Chapter 1 : Linear Equations page 2 of 31c Linear Algebra W W L Chen, 1982, 2008 We rst equate the total ow into each node with the total ow out of the same node: node A: 200 +x =x +x , 3 1 2 node B: 200 +x = 300 +x , 2 4 node C: 400 +x = 300 +x , 5 3 node D: 500 +x = 300 +x . 4 5 We then equate the total ow into and out of the network: 400 + 200 + 200 + 500 = 300 + 300 +x + 300: 1 These give rise to a system of 5 linear equations x +x x = 200; 1 2 3 x x = 100; 2 4 x x = 100; 3 5 x x =200; 4 5 x = 400; 1 in the 5 variables x ;:::;x , with augmented matrix 1 5 0 1 1 1 1 0 0 200 B 0 1 0 1 0 100 C B C B 0 0 1 0 1 100 C: A 0 0 0 1 1 200 1 0 0 0 0 400 This has reduced row echelon form 0 1 1 0 0 0 0 400 B 0 1 0 1 0 100 C B C B 0 0 1 0 1 100 C: A 0 0 0 1 1 200 0 0 0 0 0 0 Linear Algebra c WWL Chen, 1982, 2006 We have general solution (x ;:::;x ) = (400;t 100;t + 100;t 200;t), where t is a parameter. Since 1 5 one way streets do not permit negative ow, all the coordinates have to be non-negative. It follows that t 200. Example 1.7.2. The picture below represents the quantities of a particular product that flow from Example 1.7.2. The picture below represents the quantities of a particular product that ow from manufacturersM,M,M , through wholesalersW,W,W and retailersR,R,R,R ,to consumers: 1 2 3 1 2 3 1 2 3 4 manufacturersM ;M ;M , through wholesalersW ;W ;W and retailersR ;R ;R ;R , to consumers: 1 2 3 1 2 3 1 2 3 4 M M M 1 2 3 x 1 300 x x 200 2 3 W W W 1 2 3 x x x 5 6 7 x 4 300 100 R R R R 1 2 3 4 x 8 400 200 500 Chapter 1 : Linear Equations page 17 of 31 Chapter 1 : Linear Equations page 3 of 31c Linear Algebra W W L Chen, 1982, 2008 We rst equate the total ow into each node with the total ow out of the same node: node W : 200 +x =x +x , 1 1 4 5 node W : 300 +x = 300 +x , 2 2 6 node W : x = 100 +x , 3 3 7 node R : x = 400, 1 4 node R : 300 +x =x , 2 5 8 node R : 100 +x = 200, 3 6 node R : x = 500. 4 7 We then equate the total ow into and out of the network: 200 +x +x + 300 +x = 400 +x + 200 + 500: 1 2 3 8 These give rise to a system of 8 linear equations x x x =200; 1 4 5 x x = 0; 2 6 x x = 100; 3 7 x = 400; 4 x x =300; 5 8 x = 100; 6 x = 500; 7 x +x +x x = 600; 1 2 3 8 in the 8 variables x ;:::;x , with augmented matrix 1 8 0 1 1 0 0 1 1 0 0 0 200 B 0 1 0 0 0 1 0 0 0 C B C B 0 0 1 0 0 0 1 0 100 C B C B 0 0 0 1 0 0 0 0 400 C B C: B 0 0 0 0 1 0 0 1 300C B C B 0 0 0 0 0 1 0 0 100 C A 0 0 0 0 0 0 1 0 500 1 1 1 0 0 0 0 1 600 This has row echelon form 0 1 1 0 0 1 1 0 0 0 200 B 0 1 0 0 0 1 0 0 0 C B C B 0 0 1 0 0 0 1 0 100 C B C B 0 0 0 1 0 0 0 0 400 C B C: B 0 0 0 0 1 0 0 1 300C B C B 0 0 0 0 0 1 0 0 100 C A 0 0 0 0 0 0 1 0 500 0 0 0 0 0 0 0 0 0 We have general solution (x ;:::;x ) = (t100; 100; 600; 400;t300; 100; 500;t), wheret is a parameter. 1 8 If no goods is returned, then all the coordinates have to be non-negative. It follows that t 300. 1.8. Application to Electrical Networks A simple electric circuit consists of two basic components, electrical sources where the electrical potential E is measured in volts (V ), and resistors where the resistence R is measured in ohms ( ). We are interested in determining the current I measured in amperes (A). Chapter 1 : Linear Equations page 18 of 31c Linear Algebra W W L Chen, 1982, 2008 The electrical potential between two points is sometimes called the voltage drop between these two points. Currents and voltage drops can be positive or negative. The current ow in an electrical circuit is governed by three basic rules:  Ohm's law: The voltage dropE across a resistor with resistenceR with a currentI passing through it is given by E =IR.  Current law: The sum of the currents owing into any point is the same as the sum of the currents owing out of the point.  Voltage law: The sum of the voltage drops around any closed loop is equal to zero. Around any loop, we select a positive direction clockwise or anticlockwise as we see t. We have the following convention:  The voltage drop across a resistor is taken to be positive if the current ows in the positive direction Linear Algebra c WWL Chen, 1982, 2006 of the loop, and negative if the current ows in the negative direction of the loop.  The voltage drop across an electrical source is taken to be positive if the positive direction of the loop is from + to, and negative if the positive direction of the loop is from to +. Example Example1.8.1. 1.8.1. Consider Consider the the electric electric circuit circuit sho sho wnwn inin the the diagr diagram am belo belo w:w: 8Ω A I I 1 3 + 20V I 4Ω 20Ω 2 − + − B 16V We wish to determine the currents I , I and I . Applying the Current law to the point A, we obtain 1 2 3 I =I +I . Applying the Current law to the point B, we obtain the same. Hence we have the linear 1 2 3 equation I I I = 0: 1 2 3 Next, let us consider the left hand loop, and let us take the positive direction to be clockwise. By Ohm's law, the voltage drop across the 8 resistor is 8I , while the voltage drop across the 4 resistor is 1 4I . On the other hand, the voltage drop across the 20V electrical source is negative, since the positive 2 direction of the loop is from to +. The Voltage law applied to this loop now gives 8I + 4I 20 = 0, 1 2 and we have the linear equation 8I + 4I = 20; or 2I +I = 5: 1 2 1 2 Next, let us consider the right hand loop, and let us take the positive direction to be clockwise. By Ohm's law, the voltage drop across the 20 resistor is 20I , while the voltage drop across the 4 resistor is 3 4I . On the other hand, the voltage drop across the 16V electrical source is negative, since the positive 2 direction of the loop is from to +. The Voltage law applied to this loop now gives 20I 4I 16 = 0, 3 2 and we have the linear equation 4I 20I =16; or I 5I =4: 2 3 2 3 Chapter 1 : Linear Equations page 19 of 31 Chapter 1 : Linear Equations page 4 of 31c Linear Algebra W W L Chen, 1982, 2008 We now have a system of three linear equations I I I = 0; 1 2 3 2I +I = 5; (29) 1 2 I 5I =4: 2 3 The augmented matrix is given by 0 1 0 1 1 1 1 0 1 0 0 2 A A 2 1 0 5 ; with reduced row echelon form 0 1 0 1 : 0 1 5 4 0 0 1 1 HenceI = 2 andI =I = 1. Note here that we have not considered the outer loop. Suppose again that 1 2 3 we take the positive direction to be clockwise. By Ohm's law, the voltage drop across the 8 resistor is Linear Algebra c WWL Chen, 1982, 2006 8I , while the voltage drop across the 20 resistor is 20I . On the other hand, the voltage drop across 1 3 the 20V and 16V electrical sources are both negative. The Voltage law applied to this loop then gives 8I + 20I 36 = 0. But this equation can be obtained by combining the last two equations in (29). 1 3 Example 1.8.2. Consider the electric circuit shown in the diagram below: Example 1.8.2. Consider the electric circuit shown in the diagram below: 8Ω A I I 1 3 + 20V I 6Ω 8Ω 2 − + − B 5Ω 30V We wish to determine the currents I , I and I . Applying the Current law to the point A, we obtain 1 2 3 I +I =I . Applying the Current law to the point B, we obtain the same. Hence we have the linear 1 2 3 equation I +I I = 0: 1 2 3 Next, let us consider the left hand loop, and let us take the positive direction to be clockwise. By Ohm's law, the voltage drop across the 8 resistor is 8I , the voltage drop across the 6 resistor is6I , while 1 2 the voltage drop across the 5 resistor is 5I . On the other hand, the voltage drop across the 20V 1 electrical source is negative, since the positive direction of the loop is from to +. The Voltage law applied to this loop now gives 8I 6I + 5I 20 = 0, and we have the linear equation 1 2 1 13I 6I = 20: 1 2 Next, let us consider the outer loop, and let us take the positive direction to be clockwise. By Ohm's law, the voltage drop across the 8 resistor on the top is 8I , the voltage drop across the 8 resistor 1 on the right is 8I , while the voltage drop across the 5 resistor is 5I . On the other hand, the voltage 3 1 drop across the 30V and 20V electrical sources are both negative, since the positive direction of the loop is from to + in each case. The Voltage law applied to this loop now gives 8I + 8I + 5I 50 = 0, 1 3 1 and we have the linear equation 13I + 8I = 50: 1 3 Chapter 1 : Linear Equations page 20 of 31 Chapter 1 : Linear Equations page 5 of 31

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.