Discrete Structures Need done 3/26
Bearbear
week7__part1.pdf
1
Week 7 Solving Systems of Equations Using Matrices and Network Analysis
This week is quite lengthy and has several parts. For now, I ask you to concentrate on parts 1 and 2. If we have time we will cover part 3. A large number of applications can be modeled using systems of linear equations. Several such applications are discussed in part 3 of this week. Part 1 Solving systems of linear equations using matrices This is the key of all the material in the following pages.
Part 2. Solving systems of linear equations which do not have a unique solution. This is used in Part 3.
Part 3. Network Analysis. Fourteen examples, some from students, which depict some of the variety of applications of systems of equations.
Part 4 , The Row Reduction Method for Determining the Inverse of a Matrix Part 1. Solving Systems of Linear Equations Using Matrices
1) Consider the following system of equations: x1 + x3 = 1
x1 – x2 = 0
2x2 + x3 = 2
or
x1 + 0 x2 + x3 = 1
x1 - x2 + 0x3 = 0 Why?
0x1 + 2x2 + x3 = 2
We will solve this system using a procedure, which will lend itself to a procedure using matrices, which is called the Gauss-Jordan elimination method. But first, two systems of equations are called equivalent if they have the same (set of) solutions. We will see that the above system of equations is equivalent to, as the same solutions, as the system
2
1x1 + 0 x2 + 0x3 = 1
0x1 +1 x2 + 0x3 = 1
0x1 + 0 x2 + 1x3 = 0
Therefore we can “read off” the solutions directly from the above system, namely
x1 = 1
x2 = 1
x3 = 0
The reader should check by substitution into the original system that these are indeed the solutions.
The method of reducing any system of equations to a simpler system where we can more easily “read off” the solutions is based on three simple rules which apply to any system of equations. These rules we incorporate in to the following Theorem.
Theorem 1. (Elementary Operations on Equations) If any sequence of the following operations is performed on a system of equations, the resulting system is equivalent to (has the same solutions as) the original system:
a) Interchange any two equations in the system. b) Multiply both sides of any equation by a nonzero constant. c) Multiply both sides of any equation by a nonzero constant and add the result to a
second equation in the system, with the sum replacing the latter equation.
We will now apply the above Theorem to the original system given above. The original system is:
Example 1.
x1 + x3 = 1
x1 - x2 = 0
2x2 + x3 = 2
3
In order to get a clearer idea how the procedure works we will insert the “missing terms” and number the equations to obtain:
(1) x1 + 0 x2 + x3 = 1
(2) x1 - x2 + 0x3 = 0
(3) 0x1 + 2x2 + x3 = 2
Multiply both sides of equation (1) by –1 and add the result to equation (2) to obtain:
(1) x1 + 0 x2 + x3 = 1
(2) 0x1 - x2 - x3 = -1 Note: Equation (1) did not change.
(3) 0x1 + 2x2 + x3 = 2
Multiply both sides of equation (2) by –1 to obtain:
(1) x1 + 0 x2 + x3 = 1
(2) 0x1 + x2 + x3 = 1
(3) 0x1 + 2x2 + x3 = 2
Multiply both sides of equation (2) by –2 and add the result to equation (3) to obtain:
(1) x1 + 0 x2 + x3 = 1
(2) 0x1 + x2 + x3 = 1 Note: Equation (2) did not change.
(3) 0x1 + 0x2 - x3 = 0
Multiply both sides of equation (3) by –1 to obtain:
(1) x1 + 0 x2 + x3 = 1
(2) 0x1 + x2 + x3 = 1 (3) 0x1 + 0x2 + x3 = 0
Multiply both sides of equation (3) by –1 and add the result to equation (1) to obtain:
(1) x1 + 0 x2 + 0x3 = 1
(2) 0x1 + x2 + x3 = 1 Note: Equation (3) did not change.
(3) 0x1 + 0x2 + x3 = 0
4
Multiply both sides of equation (3) by –1 and add the result to equation (2) to obtain:
(1) x1 + 0 x2 + 0x3 = 1
(2) 0x1 + x2 + 0x3 = 1 Note: Equation (3) did not change.
(3) 0x1 + 0x2 + x3 = 0
Therefore the solution to the system is: x1 = 1, x2 = 1 and x3 = 0.
If you think about the step-by-step changes in the above equivalent systems the changes from system to system is in the numbers involved, that is, in the coefficients of the x’s, and the constants. The only purpose that the variables serve is to ensure that is that of keeping the coefficients (and the constants) in the appropriate location. We can effect this using matrices. We will write the original system in matrix notation as:
1 0 1 1
1 1 0 0
0 2 1 2
or 1 0 1 1
1 1 0 0
0 2 1 2
. The only purpose of the vertical line in the latter version of
this matrix is to separate the coefficients of the system from the constants for easier readability. Both ways of writing the matrix of the system are used. Since the first three columns of this matrix are the coefficients of the given system of equations the matrix consisting of the first three
columns is called the coefficient matrix. That is, the coefficient matrix is 1 0 1
1 1 0
0 2 1
.The
“complete matrix” above, 1 0 1 1
1 1 0 0
0 2 1 2
, is referred to as the augmented matrix. So one way
of using the tool of matrices to solve systems of equations is to take Theorem 1 above and to replace the word equation by row and the word system by matrix, that is, another version of Theorem 1 is:
Theorem 1. (Elementary Row Operations) If any sequence of the following operations is performed on a matrix, the resulting matrix is equivalent to the original.
a) Interchange any two rows in the matrix. b) Multiply any row of the matrix by a nonzero constant. c) Multiply both sides of any row by a nonzero constant and add the result to a second
row, with the sum replacing the latter row.
5
If we use the convention that Ri stands for row i of a matrix and the symbol to stand for
row equivalent then A i j cR R
B means that the matrix B is obtained from the matrix A by multiplying the ith row of A by c and adding it to the jth row of A. Remember for our purposes here if two matrices are row equivalent then they represent equivalent systems of equations. That is, systems which have the same solutions.
Remember: cRi + Rj means multiply row i by the number c and add it to row j. So the first step in
example 1 below indicates multiply row 1 by ‐1 and add it to row 2.
We now redo example 1 using matrices.
Example 1 revisited.
1 0 1 1
1 1 0 0
0 2 1 2
21)1( RR 1 0 1 1
0 1 1 1
0 2 1 2
Note: Row 1, 1R did not change. Step 1
2( 1) R 1 0 1 1
0 1 1 1
0 2 1 2
Multiply all of row 2 by (-1). Why? Step 2
32)2( RR 1 0 1 1
0 1 1 1
0 0 1 0
Note: Row 2, 2R did not change Step 3
3( 1) R 1 0 1 1
0 1 1 1
0 0 1 0
Step 4
13)1( RR 1 0 0 1
0 1 1 1
0 0 1 0
Note: Row 3 3R does not change. Step 5
3 2( 1) R R 1 0 0 1
0 1 0 1
0 0 1 0
Step 6
6
Note, one may prefer to use a different sequence of steps than I did in solving the above.
Study the above sequence of steps in example 1 revisited. The strategy in solving a system of equations using matrices should become clear after studying this and the other examples below.
Strategy
1. Get a 1 in the first row first column by interchanging rows or dividing all of row 1 by some nonzero number. In example 1 we already have a 1 in row I column 1..
2. Get 0’s for the other entries in column 1. See step 1 above. 3. Get a 1 in row 2, column 2. See step 2 above. 4. Use the 1 in row 2 column 2 as a “pivot” to get 0’s for the other entries in column 2. See
step 3 above. 5. Get a 1 in row 3 column 3. See step 4 above 6. Use the 1 in row 3 column 3 as a “pivot” to get 0’s for the other entries in column 3. See
steps 5 and 6 above.
Example 2. Solve the system. Recall that this means that we want to find all real numbers x1, x2, and x3 which will satisfy each equation in the system.
4x1 + 2x2 + x3 = 1
2x1 + x2 + x3 = 4
2x1 + 2x2 + x3 = 3
Follow the Strategy above to explain each step in the solution below.
The (augmented) matrix of the system is:
4 2 1 1
2 1 1 4
2 2 1 3
or if you prefer inserting the vertical line 4 2 1 1
2 1 1 4
2 2 1 3
.
4 2 1 1
2 1 1 4
2 2 1 3
1
4 R1
1 1
2
1
4
1
4 2 1 1 4
2 2 1 3
2 R 1 R
2
1 1
2
1
4
1
4
0 0 1
2 7 / 2
2 2 1 3
7
We now write in the variables and the equality symbols to obtain the system:
x1 + 0x2 + 0x3 = -1
0x1 + x2 + 0x3 = -1
0x1 + 0x2 + x3 = 7
and read off the solution to the original system as x1 = -1, x2 = -1 and x3 = 7.
2 R1 R3
1 1
2
1
4
1
4
0 0 1
2 7 / 2
0 1 1
2 5 / 2
Interchange
R 2
and R 3
1 1
2
1
4
1
4
0 1 1
2 5 / 2
0 0 1
2 7 / 2
1 2
R2 R1
1 0 0 1 0 1
1
2 5 / 2
0 0 1 2
7 / 2
2 R3 1 0 0 1 0 1
1 2
5 / 2
0 0 1 7
1
2 R3 R2
1 0 0 1 0 1 0 1 0 0 1 7
8
I encourage the reader to substitute these values in the system to verify that they are indeed
the solutions to the given system of equations.
Example 3. Solve the system 1x1 + 2x2 = 1
2x1 + x2 = 4
Recall that this means that we want to find all real numbers x1and x2 which will satisfy each equation in the system.
Using matrices we have
1 2(-2)R + R 1 2 1 1 2 1
2 1 4 0 3 2
Obtain a 0 in the 2nd row 1st column
1
23 (- ) R
2 3
1 2 1
0 1 -
Obtain a 1 in the 2nd row 2nd column
2 1 7 3(-2)R + R
2 3
1 0
0 1 -
Obtain a 0 in the 1st row 2nd column
So the solution is x1 = 7 3 and x2 =
2 3-
Now solve the system,
1x1 + 2x2 = 2
2x1 + x2 = 3
Note we can use the same steps that we used in solving the above system because the coefficient matrix is the same
9
1 2
1 23
2 1
(-2)R + R
(- ) R
1 3
4 (-2)R + R 3
1 3
1 2 2 1 2 2
2 1 3 0 3 1
1 2 2
0 1
1 0
0 1
So the solution is x1 = 4 3 and x2 =
1 3
For additional examples google “Using matrices to Solve Systems of Equations”.
Another much faster way of solving the two systems in example 3
If we knew ahead of time that we wanted to solve the above two systems of equations and we noticed that they had the same coefficient matrix we could save considerable time by augmenting the coefficient matrix by, not one column of constants as above but by both columns of constants. That is, we could solve both systems of equations simultaneously as below.
1 2
1 23
2 1
(-2)R + R
(- ) R
-2 1 3 3
7 4 (-2)R + R 3 3
-2 1 3 3
1 2 1 2 1 2 1 2
2 1 4 3 0 3 2 1
1 2 1 2
0 1
1 0
0 1
Note, this gives us the solutions of both systems of equations as described earlier.
Example 4. Solve the two systems of equations “simultaneously” as in the second half of example 3. Note, for simplicity I kept the same coefficient matrix as in example 3.
1x1 + 2x2 = 1 1x1 + 2x2 = 0
2x1 + x2 = 0 and 2x1 + x2 = 1
10
1 2
1 23
2 1
(-2)R + R
(- ) R
2 -1 3 3
-1 2 (-2)R + R 3 3
2 -1 3 3
1 2 1 0 1 2 1 0
2 1 0 1 0 3 2 1
1 2 1 0
0 1
1 0
0 1
So the solution of the first system are the values in the 3rd column, namely,
x1 = -1 3 and x2 =
2 3
The solution to the second systems are the numbers in the 4th column namely,
x1 = 2 3 and x2 =
-1 3
These four examples explain the row reduction method of solving systems of equations. At this point you may want to skip example 5 and try the exercises at the end of part 1. Example 5 is extra information “for the experts”. It is the underlying idea of part 4, and exercises 6 & 7.
Example 5. Consider the coefficient matrix A = 1 2
2 1
above. If we used the formula for
finding the inverse of A we would obtain A-1 = -1 2 3 3
2 -1 3 3
. Please verify this.
The definition of the inverse of any n x n matrix is: Given an n x n A if there exists an
n x n matrix B such that AB = BA = I then B is the inverse of the matrix A and it is denoted by
the symbol A-1 which is read A inverse. If we let A = 1 2
2 1
and take B or A-1 as w x
y z
.
The equation AB = I becomes 1 2
2 1
w x
y z
= 1 0
0 1
. Multiply the left side of this and
equate both sides of the result and you will obtain 2 systems of two equations 2 unknowns. In fact, you will obtain the 2 systems in example 4 (different variable names). These systems we solved by using the matrix
1 2 1 0
2 1 0 1
and row reducing it to -1 2 3 3 2 -1 3 3
1 0 0 1
. This gives us A-1 = -1 2 3 3
2 -1 3 3
.
11
This works for any n x n matrix whose inverse exists. WOW!
That is, if we want to find the inverse (if it exists) of any n x n matrix A. Take A, augment it by the matrix I then row reduce that to “I” augmented by “what it becomes” and “what it becomes” will be A-1. In symbols
-1row reduce row reduceA I . . . I A More example of find the inverse of a matrix this way are at the end of week 7, or just “google it”.
Remark Each system of equations will (usually) have its own set of solutions. The purpose of example 4 and exercises 3 & 4 of the notes is to show that since the coefficient matrix of exercise 3 and that of 4 are the same the same elementary row operations could be used to solve each system. So if we were given 2 systems with the same coefficient matrix instead of solving them separately we could save time by solving them together by augmenting the coefficient by not one but 2 columns. Then use the usual process to row reduce the matrix. If all goes well the numbers in the first (added) column become the solution of the first system and those in the second (added) column become the solutions of the second system. Exercise 5 is an example where you can do this. One intent of the discussion is to lead people to thinking about what exercise 6 means and eventually to why the method of finding the inverse of a matrix (see example 5) in the next set of notes works. So the matrix of problem six is really the matrix for solving 3 systems of 3 equations and 3 unknowns. A key part of the definition of the inverse of a matrix A is to find a matrix B such that
AB = I. If A is the 3x3 coefficient matrix given in problem 6, and if B (of the definition of inverse) is a 3x3 matrix of variables (since we are looking for B). Then AB = I becomes 3 systems of 3 equations and 3 unknowns, all with the same coefficient matrix. So we can solve all 3 systems simultaneously. The matrix of the 3 systems is that of problem 6. So if you solve problem 6 you are really finding the inverse (of the coefficient matrix).
12
Exercises
1. Write the systems of equations that the following matrices represent.
a)
1 1 0 0
1 1 1 1
0 1 1 2
b)
4 2 1 1
2 1 1 4
2 2 1 3
c) 2 1 4
1 1 1
d) 1 0 3 1
1 2 1 1
e) 1 0 3 1
1 2 1 0
2. Solve each of the systems of equations parts a through c in exercise 1 using the Gauss‐Jordan technique. Verify your solutions by substituting your solutions in the original equations. Note, you will be able to solve 1(d) and 1(e) after you study the next section, “Systems of Equations Which Do Not Have A Unique Solution” .
3. Solve the following system using the Gauss‐ Jordan technique. Verify your solution by substitution in the original system.
x1 + x3 = 1
x1 – x2 = ‐1
2x2 + x3 = 3
4. Could you have used the same steps in doing exercise 3 that we used in example 1? Why?
5. Can you solve the following two systems of equations simultaneously using the same matrix? (Hint: Augment the coefficient matrix by 2 columns.) x1 + x2 = 0 x1 + x2 = 1
‐x1 + x2 + x3 = 1 and ‐x1 + x2 + x3 = ‐1
‐1x2 + x3 = 2 ‐1x2 + x3 = 3
6. The matrix 1 0 1 1 0 0
1 1 0 0 1 0
0 2 1 0 0 1
can be viewed as a matrix which allows one to solve three
systems of three equations and three unknowns. Write out the three systems of equations and use the given matrix to solve the three systems simultaneously.
7. Look up the definition (not the formula) for the inverse of a matrix. What does exercise 6 give us?
13
