A.

Doerr

Solving Systems of Linear Equations

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 solution 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

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:

1
 A. Doerr

Example 1.

x1 + x3 = 1
x1 - x2 = 0
2x2 + x3 = 2

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

2
 A. Doerr

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 0 1 1 
1 1 0 0 or 1 1 0 0 . The only purpose of the vertical line in the latter
  
 0 2 2 
 1
0 2 1 2

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
1
 0 1   1 0 1 1 
coefficient matrix is 1 1 0 .The “complete matrix” above, 1 1 0 0 , is
   
0 2 1  0 2 2 
 1
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.

If we use the convention Ri to stand for row i of a matrix an the symbol  to stand for
row equivalent then cRi Rj B means that the matrix B is obtained from the matrix A
A
by multiplying the ith row of A by c and adding it to the jth row of A. Remember for

3
 A. Doerr

our purposes here if two matrices are row equivalent then they represent equivalent
systems of equations.

We now redo example 1 using matrices.

4
 A. Doerr

Example 1 revisited.

1 0 1 1  1 0 1 1 

1 1 
0 
( 1)
0 1 1

1  Note : Row 1  R1  did not change.
0
 
1  2 
R R

 0 2 2  0 2 2 
1  1

1 0 1 1
( 1 ) R2  
   0 1 1 1

0 2 1 2 

1 0 1 

2) R

1
1  Note: Row 2 R 2  did not change
 2
(
0 1


 3
R
1
 0 0 1 0 

1 0 1 1 
( 1 ) R3  1 1 1 
   0

0 0 1 0


1 0 0 1


( 1) R
3  1 
 R 
0 1 1 1

Note : Row 3  does not change

R03 0 1 0 


1 0 0 1 
( 1) R  R2  1 0 
   3  0 1
0 0 1 0 

Note, one may prefer to use a different sequence of steps in solving the 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
The (augmented) matrix of the system is:
4 2 1 1  4 2 1 1 


 1 1 4 or
2 
if you prefer inserting the vertical line 1 1 4  .

2
2 2 1 3  2 2 1 3
5
 A. Doerr

 1 1 1
4 1 1
2 1 1 2 4 4
2 1 1 4 R1 2 1 1 4
4
   2 
2 2 1 3 2 1 3


 
 
 1 1 1 
1 
2   2 4 4 
 R1 R2  
 1 7/ 2
0 0
2 
 
2 2 1 3
 
 

 1 1 1 
1 
 2 4 4 
2R1 R3 
 
 1 7/ 2
0 0
 
 2 
1
0 1 5 / 2
 2 

 1 1 1 
1 
Interchange  2 4 4 
  R 2
 1 
ndR3
a
0 1 5/ 2
  2 
1 7 / 2
0 0
 2 

 
1
 R R
1 0 0 1 
2 1
1
2   0 1 2 5 / 2
 1 
0 0 7 / 2
 2 

1 0 0 1 
2 R 1
  3  0 1 5/2
2
 0 1 7 
0

1
 1 0 0 1
R  R
3 2
0 1 0 1
    2

 0 1 7  
0

6
 A. Doerr

We now write in the variables and the equality symbols to obtain the system:

7
 A. Doerr

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.
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.

Remark
Each system of equations will (usually) have its own set of solutions. The purpose of
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 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).

Exercises (It is important that you do each of the following exercises.)

1. Write the systems of equations that the following matrices represent.

 1 1 0 0 4 2 1 1 
   
a)  1 1 1 1  b)  2 1 1 4 
 0 1 1 2 2 2 1 3 

2 1 4 1 0 3 1  1 0 3 01 
c) d)  e) 
     
1 1 1  1 2 1 1 1 2 1

8
 A. Doerr

2. Solve each of the systems of equations in exercise 1 using the Gauss-Jordan

technique. Verify your solutions by substituting your solutions in the original equations.
You may wish to read the section on the next page called “Systems of Equations
Which Do Not Have A Unique Solution” before you try 1(d) and 1(e).

3. Solve the following system using the Gauss- Jordan technique. Verify your solution
by substitution in the original system.

x1 + x 3 = 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

1 0 1 1 0 0 
 
6. The matrix 1 1 0 0 1 0  can be viewed as a matrix which allows one to solve
0 2 1 0 0 1 
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?

9
 A. Doerr

Systems of Equations Which Do Not Have A Unique Solution

On the previous pages we learned how to solve systems of equations using

Gaussian elimination. In each of the examples and exercises the systems of equations
had a unique solution. That is, a single value for each of the variables. In 2-space, the
xy-plane, we have the geometric bonus of being able to draw a picture of the solutions
to a system of two equations two unknowns. Clearly, if we were asked to draw the
graphs of two lines in the xy-plane we have 3 basic choices:

1. Draw the two lines so they intersect. This point of intersection can only
happen once for a given pair of lines. That is, the two lines intersect in a
unique point. There is a unique common solution to the system of equations.

2. Draw the two lines so that one is on "top of" the other. In this case there are
an infinite number of common points, an infinite number of solutions to the
given system.

3. Draw two parallel lines. In this case there are no points common to both lines.
There is no solution to the system of equations that describe the lines.

The 3 cases above apply to any system of equations.

Theorem 1. For any system of m equations with n unknowns (m < n) one of

the following cases applies:

1. There is a unique solution to the system.

2. There is an infinite number of solutions to the system.
3. There are no solutions to the system.

Again, in this section of the notes we will illustrate cases 2 and 3. To solve
systems of equations where these cases apply we use the matrix procedure developed
previously.

Example 3. Solve the

system x + 2y = 1
2x + 4y =
2

It is probably already clear to the reader that the second equation is really the first
in disguise. (Simply divide both sides of the second equation by 2 to obtain the first).
So if we were to draw the graph of both we would obtain the same line, hence have an
infinite number of points common to both lines, an infinite number of solutions.
However it would be helpful in solving other systems where the solutions may not be
so apparent to do the problem algebraically, using matrices. The matrix of the system
with

10
 A. Doerr

1 2 1
its simplification follows. Recall, we try to express the   in the form
matrix 2 4 2

1 0 b1
 from which we can read off the solution. However after one step we note that
0 1 

b2

1 2 1 2 1
 1 . It should be clear to the reader that no matter what further

 2 
2 4 0 0
R 1 R 2

   0
2 

elementary row operations we perform on the 1 2 1

 we cannot change it to the
matrix 0 0 0

form we hoped for, 1 0 b1 
 . To understand what our result means simply
namely, 0 1 b2 
1 2 1
write the system of equations that the  represents, that is,
0 0 0
matrix x + 2y = 1 
0x + 0y = 0.

The first equation tells us that x = 1 - 2y (or equivalently y = 1/2(1 - x)), so that
(1,0), (-1,1), (-5,3) etc. are three of the infinite number of possible solutions of the first
equation. The second equation places no restrictions on what values x and y can assume,
hence there are an infinite number of solutions to both equations, to the system. Any
pair of real numbers of the form (1 - 2y,y) where y can be any real number is a solution
to the given system of equations. The solutions of the system can also be expressed in
the form (x,1/2(1 - x) where x can be any real number.
Warning. When there are an infinite number of solutions to a system there are
frequently several “different-looking” ways to describe the solutions, as in the above
example.

Example 4. Determine the solutions of the system of equations whose matrix is row
1 0 0 1
 
equivalent to 0 1 1 0  . Give three examples of the solutions.
0 0 0 0
If we use the variables x1, x2, and x3 the system of equations which is
represented by this matrix is x1 = 1, and x2 - x3 = 0 (or x3 = x2)

There are an infinite number of solutions and any triple of the form (1, x2, x2)
where x2 can be any real number is a solution. (1,1,1), (1,3,3) and (1,-1,-1) are three
examples of solutions.

2 1 0 1
Example 5. Solve the system of equations whose matrix  
1 2 1 0 . Give three
is
e x amples of the solutions.

11
 A. Doerr

 0 3 2 1 

12
 A. Doerr

 2 1 0 1
 interchange rows 1 and 2 1 2 1 0
  
1 2 1 0       2 1 1
a nd then -1 R1
0


 0 3 1  0 3 2 1 
2 

1 2 1 0 1 2 1 0
-2R 1 
R2    
    0 3 2 1  R 2 R 3 03 2  1 .
0 3 1  0 0 0 
 0
2
At this point we could row-reduce the last matrix further by but this is really
not necessary. If we call the variables x1, x2 and x3 the system of equations that this
last matrix represents is:
x1 - 2x2 + x3 =
0 3x2 - 2x3 = 1.

From the latter equation we can say x3 = ½ (3x2 - 1). If we substitute this
expression for x3 in the first equation we obtain x1 - 2x2 + ½ (3x2 - 1) = 0 or
x1 = 2x2 - ½ (3x2 - 1) which can be simplified to x1 = ½(x2 + 1). If we replace x2 by 0
then one solution is x1 = 1/2, x2 = 0 and x3 = -1/2. Another solution is (3/2, 2, 5/2).
Why? We ask the reader to substitute these solutions into the original system to verify
that they are solutions, and to find two more solutions.

Another situation that one encounters is that when the number of unknowns is
greater than the number of equations. For example: x1 + x2 - 3x3 = -1
x2 - x3 = 0.

But upon closer inspection this is simply another form of the above examples .
We illustrate with an example

Example 6. Solve the system of equations

x1 + x2 - 3x3 = -1
x2 - x3 = 0. This system is the same as the system
x1 + x2 - 3x3 = -
1 0x1 + x2 - x3 =
0
1
0x1 + 0x2 + 0x3 = 0, 1 1 3 or the
So we can represent the above system by the
matrix
 
0 1 1 0 
1 1 3 1
 
matrix 0 1 1 0  . Clearly no matter what elementary row operations we perform on
13
 A. Doerr

0 0 0 0
 1 0 0 b1 
this matrix we cannot change it to the  
0 1 0 b2  . For this reason it is common
form 0 0 1 b3 

14
 A. Doerr

practice to rewrite the matrix without the rows which contain all zeros, so that the matrix
1 1 1
of the given system is  and the reader can show that this matrix can be
3 
0 1 0 

 1

reduced to 1 0 2 1
  which gives us the system
0 1 0

1
x1 - 2x3 = -
1 x2 - x3 =
0

From the second equation, x3 = x2

Substitute this value of x2 in first equation to

obtain x1 = 2x2 - 1

So all solutions of the given system are ordered triples of the form (2x2 – 1, x2,
x2) where x2 takes on all real numbers. Examples of solutions are:
x2 = 0 gives (-1, 0, 0) as an example of one solution and x3 = 2 gives (3, 2, 2) as
another solution.
Keep in mind that there are often many different ways to describe the solutions of the
same system. For example, I claim that the solutions of the system give in example 6
can also be described as any ordered triple of the form (x1, ½(x1+ 1), ½(x1+ 1)
where x1 is any real number.

Exercises
1. Determine the solutions of the system of equations whose matrix is row equivalent to
1 0 0 1
0 1 2 0
 
 0 0 0 0 
.Give three examples of the solutions. Verify that your
solutions satisfy the original system of equations.

2. Determine the solutions of the system of equations whose matrix is row equivalent to
10 01 02 13
 
 0 0 0 0 
.
Give three examples of the solutions. Verify that your solutions
satisfy the original system of equations.

3. Determine the solutions of the system of equations whose matrix is row equivalent to
1 0 1 1
15
 A. Doerr

0 1 3 1
 
 0 0 0 0 
. Give three examples of the solutions. Verify that your solutions

16
 A. Doerr

satisfy the original system of equations.

4. Determine the solutions of the system of equations whose matrix is row equivalent to
1 1 1 1 
0 2 3 2
 
 0 0 0 0  . Give three examples of the solutions. Verify that
your solutions satisfy the original system of equations.

5. Determine the solutions of the system of equations whose matrix is row

 1 1 1 1 
1 2 2 2
 
equivalent to  0 0 0 0  . Give three examples of the solutions.
Verify that your solutions satisfy the original system of equations.

17
 A. Doerr

Several Applications of Systems of Linear Equations

You should be prepared to make up a meaningful example like the

following. Network Analysis

Directed graphs can be used as models for a variety of situations in disciplines such as:
computer science, traffic analysis, electrical engineering and economics. A directed
graph is also referred to as a network and the analysis of the given problem as
network
analysis. Directed graphs are composed of nodes (also called vertices or junctions), and
directed edges. In the graph below, figure 1, the nodes are the “circles” labeled 1,2,3
and
4. “Dots”, with labels, are also used in place of circles. The edges are the “arrows”
in the graph.

We assume in the following flow examples that the sum of the flow into any
(intermediate) vertex is equal to the sum of the flow out of that vertex. Below are
several examples.

Example 1

The flow of traffic (in vehicles per hour) through a network of streets is shown in
the figure 1:
Solve this system xi , i = 1, 2, 3, 4.
for
Find the traffic flow when x3  0
Find the traffic flow x3  100
when
400

2 x2
x1
200
1 3 200

x3 4 x4

Sol 400
uti
on
18
 A. Doerr

FIGU RE 1
a) From figure 1, we have the following linear equations:

19
 A. Doerr

Junction
x1  200  x3
1:
x2  400  x1
Junction
2: x2  200  x4
Junction x4  400  x3
3:
Junction
4:

The augmented matrix for this system is:

 1 0 1 0  200
 
1 1 0 0  400

 0 1 0 1  200
 
 0 0 1 1  400

Gauss-Jordan elimination produces the matrix

1 0 0 1 200 
 
0 1 1 0  600
0 0 1 1 400 
 
 0 0 0 0 0 
This matrix gives us the following equations:
x1 – x4 = 200
x2 – x3 = -600
x3 – x4 = 400

Note you could have obtained these equations directly from the given system of
equations.

So
x1 = 200 – x4
x2 = -200 + x4 Why?
x3 = 400 + x4, where x4 can be any real number. Another way of describing the
solutions is to use a dummy variable, say s as used below.

Let x  s we have:
4

x1  200  x2  200  x3  400  s

s s
where s is any real number. Thus this system has an infinite number of solutions.
(More about this later.) Note the solutions could have been described without using s
(see the above).

b) If x3 = 0 then 0 = 400 + s so that x4 =s = -400. This tells us that x1 =-200, x2 = -

600. What this means is when the traffic flow along street x 3 is restricted to 0, that is,
20
 A. Doerr

when this street is closed the flow along the other streets is: x1 = -200, x2 = -600 and
x4 = -400. Which of course does not make any sense. Why?

21
 A. Doerr

If: x3 =100 then 100 = 400 + s so that Systems of Equations Which Do Not Have A Unique
Solution = s = -300. This tells us that x1 =-100, x2 = -500 and x4 = -300, which still
does not make any sense.

Can you determine the minimum value of s (or x4) which will make sense in this
problem? That is, what is the smallest value of x4 which will make the other variables
nonnegative?

In addition, for this problem to be realistic we should have a maximum capacity for
each edge. That is, each road or edge cannot handle an infinite number of cars per hour.
The number of vehicles that can travel along a road is determined by several factors, for
example: the width of the road, its surface (how smooth etc.), and how straight it is,
speed limit etc. So there are a maximum number of cars per hour that can travel along
each road. You should make up a realistic maximum capacity for each edge.

Example 2

The flow of traffic (in vehicles per hour) through a network of streets is shown in
the figure :
Solve this system xi , i = 1, 2,..,5.
for
Find the traffic flow x3  0 and x5  50
when
Find the traffic flow x3  x5  50
when

x1
200 300
1 2

x2 x4
x3
4 3
150 50
x5
FIGURE 3

Solution
a) From figure 3, we have the following linear equations:

Junction Junction 3:
1: Junction 4:
Junction
2:

22
 A. Doerr

x2  200 
x1
x1  x3 
300  x4
x4  x5  50
x2  x3  x5
 150

23
 A. Doerr

The augmented matrix for this system is:

1 1 0 0 0  200
 
 1 0 1 1 0 300 
 0 0 0 1 1 50 
 
 0 1 1 0 1 150 

Gauss-Jordan elimination produces the matrix

1 1 0 0 0  200
 
0 1 1 1 0 100 
0 0 0 1 1 50 
 
0 0 0 0 0 00 

If we x5  s an x3  t we have:
let d
x1  350  s  x2  150  s  x4  50  s
t t
where s and t are real numbers. Thus this system has an infinite number of solutions.

b) For an example if we let: t or x3  0 and let s or x5  50

we obtain for the other variables: x1 = 300, x2 = 100 and x4 = 0

300
200 300
1 2

1000
0
43
150 50

50

c) If we x3  x5  50
let:
 t  s  50
150
250
200

24
 1 2

50 0
50 A. Doerr

4 3

50 30
0

50

25
 A. Doerr

Follow the same rationale we did on example 2 so that the results of this problem
make sense in the “real world”.

Example 4. A student example (good if you know electric circuits).

A particular circuit has current sources connected across ports ab and cd. If
Iac=50 Amps and Icd=20 amps the flow of current in the circuit is demonstrated in the
figure.

x1 x2
AFE

x3 x4 x5
50 A

B C D
x6x7

20 A

With the sources fixed at their particular values. Find the flow between each node when
the path between F & E is an open circuit ( x2 = 0 ) and when the path is a short
circuit at 10 amps.

By Kirchoff's current law, the sum of the voltages entering a node is equal to that
leaving the node, so: (NOTE: Two of the following equations are wrong. Which two?
Check the flow equations for nodes C and D.)
50 = x1 + x3
50 = x3 + x6
x1 - x4 = x2
x2 = x5
x5 = x7 + 20
20 = x4 + x4

26
 A. Doerr

The augmented matrix for this system is:

1 0 1 0 0 0 0 50
0 0 1 0 0 1 0 50
1 -1 0 -1 0 0 0 0
0 1 0 0 -1 0 0 0
0 0 0 0 1 0 -1 20
0 0 0 -1 0 1 0 20

Gauss-Jordan elimination produces:

0 0 1 0 0 0 0 50
0 0 0 0 1 0 0 0
1 0 0 0 0 0 0 0
0 1 0 1 0 0 0 0
0 0 0 1 1 0 0 0
0 0 0 1 0 0 1 -20

In other words

x3 = 50
x6 = 0
x1 = 0
x2 + x4 = 0
x4 + x5 = 0
x3 + x3 = -20

This implies that the current from the 50A source follows the shortest path
possible and does not go over to the other side of circuit. For the open circuit case x2
= 0 This results in:
x4 = 0, x5 = 0, and x7 = -20 as all the current flows between C and D.

When the path x2 permits 10 Amps the results become:

x4 = -10, x5 = 10, and x7 = -10 this is an example of a current division as half
flows through one path and the remaining current flows through another.

27
 A. Doerr

Example 5.

The internet is a network of servers; servers receive requests of information from

client PCs (i.e. individual’s PCs), or send the requested information to the client PCs. A
person (the sender) sends a large file over the internet to second person (the receiver).
Before the file is sent, it is split into small packets. Then the packets are routed through
the network using routers to avoid congestion; routers are set up to regulate the flow of
data. In this problem, the network contains four routers named A, B, C, and D. The
bandwidth of the network is measured in megabytes per second (Data is represented in
binary inside a computer, 0 or 1, which is called a bit. A unit of byte contains of 8 bits.
A unit of kilobyte contains 1024 bytes. A unit of megabytes contains 1000 kilobytes).
Suppose the file contains 80 megabytes of data, which are sent to the routers A and C
as illustrated below. The complete network is illustrated below:

x1
A B
50
30
x2 x3

Sender Receiver

50 C D x5
x4

According to the above figure, the 80-megabytes file is split into 2 packets, 30-megabytes
and 50-megabytes. The two packets are then routed through the routers, and split into
more packets. At the routers B and D, these small packets are combined and sent to the
receiver. Note that the received file must contain exactly 80 megabytes of data such as
when it is sent by the sender.
Solve this system the data flow represented xi , i = 1, 2, ..5.
by
Find the network flow pattern x2  0
when Find the network flow x2  30
pattern when

Solution
a) From the figure , we have the following linear equations:

Junction A: x1  x2  30
Junction B: x1  x3  50
28
 A. Doerr

Junction C:
x3  x4  50
Junction D: x2  x4  x5
Junction x5  50  80
RECEIVER:

The augmented matrix for this system is:

1 1 0 0 0 30
1 0 1 0 0 50
 
0 0 1
 1 0 50
0 1 0 1 1 0 

0 0 0 0 1 30 


Gauss-Jordan elimination produces the matrix:

 1 0 0 0 30
1 
1 0 1 0 30
 
0 0 1 1 0 50
 
0 0 0 0 1 30 
 0 0 0 0 0

0


0

Let x  s we have:
4

x1  s x2  30  x3  50  x5  30
s s
where s is real numbers. Thus this system has an infinite number of solutions.

b) I x  0 , then we have the following graph:

f 2
30
A B
50
30
0 20

Sender Receiver

30
50 C 30 D

29
 A. Doerr

d) If x  30 , then we have the following graph:

2

30
 A. Doerr

0
A B
50
30
30 50

Sender Receiver

30
50 C D
0
Example 6.

Now, we understand the concept of how a file is sent through the network of internet.
We can consider the next problem. A student at MIT wants to download a 1-megabyte
graphic computer file located on a server at U. C. Berkley in Oakland, CA. If the file is
sent out as a sequential data stream, it will take too long. So the file is broken up into
ten 100-kilobytes “packets” and routed via multiple servers located in different cities
around the country, and reassembled at MIT into one file.

x6
SEATTLE CHICAGO

x5
(1megabyte) x7 4
10 packets 3

4 x8
U.C. DENVER MIT
BERKLEY
x1 x4
4
x2

LA ATLANTA
x3

Solution

a) From the figure, we have the following linear equations:

Junction BERKLEY: 3  4  x1  10
Junction SEATTLE: x5  x6  3
Junction CHICAGO: x6  x7  4

31
 A. Doerr

Junction LA:
x2  x3  x1
Junction x3  x4  4
ATLANTA:
x2  x5  4  x4  x7  2
Junction DENVER: 4  x8  4  10
Junction MIT:

The augmented matrix for this system is:

1 0 0 0 0 0 0 0 3
 
0 0 0 0 1 1 0 0 3
0 0 0 0 0 1 1 0 4
 
1 1 1 0 0 0 0 0 0 
0 0 1 1 0 0 0 0 4
 
 0 1 0 1 1 0 1 0  2
 0 0 0 0 0 0 0 1 2
 
Gauss-Jordan elimination produces the matrix:
 0 0 0 0 0 0 0 3
1 
 1 1 0 0 0 0 0 3
0 0 1 1 0 0 0 0 4 
 
0 0 0 0 1 0 1 0  1
 0 0 0 0 1 1 0 4
0 0 0 0 0 0 0 1 2 


0 0 0 0 0 0 0 0
0 


0


0

Let x  t an x  s , we have:
4 7
d
x1  3 x2  1  x3  4  x5  1  x6  4  x8  2
t t s s
where s and t are real numbers. Thus this system has an infinite number of solutions.

32
 A. Doerr

b) I
x  x7  0 , then we have the following graph:
f 4

SEATTLE CHICAGO

1
0 4
(1megabyte) 10 packets3
U.C. BERKLEY
4 2
DENVER MIT

3 0
1 4

LA ATLANTA
4

c) I x  4 x6  2 , then we have the following graph:

f 3
and

2
SEATTLE CHICAGO

1 2 4
3
(1megabyte) 10 packets
U.C. BERKLEY

2
4
DENVER MIT
0
3 4
1

ATLANTA
LA 4

33
 A. Doerr

Example 7.

A train carries 1000 people into Boston. Once there everybody must immediately
get to the Government Center to go to work. There are several different subways, which
go to the Government Center. The network of the subways in this problem is illustrated
below:

x1
A B
x7
500 x2
x5
E Government center

Station
x3
500
C D
x4 x6

Let the nodes A, B, C, D, and E represent the different subways, A, B, C, D, and E.

Solution
a) From the figure, we have the following linear equations:

Junction A: x1  x2  500
Junction B: x1  x7
Junction C: x3  x4  500
Junction D: x4  x6
Junction E: x2  x3  x5

The augmented matrix for this system is:

1 1 0 0 0 0 0 500

1 0 0 0 0 0 1 0 

0 0 1 1 0 0 0 500
 
0 0 0 1 0 1 0 0 
0 1 1 0 1 0 0 0 

34
 A. Doerr

Gauss-Jordan elimination produces the matrix:

1 0 0 0 0 0 1 0 

0 0 0 0 
0 1 1 500 
0 0 1 1 0 0
 0 500 

0 0 0 1 0 1 0 0 
0 0 0 0 1 1 1 1000 

Let x  s x7  t , we have:
6
and
x1  t x2  500  x3  500  x4  s x5  1000  s  t
t s
where s and t are real numbers. Thus this system has an infinite number of solutions.

b) I x  0 x7  0 , then we have the following graph:

f 6
and

0
A B
0
500 500
1000
E Government Center

Station 500
500
C D
0
0

35
 A. Doerr

If x6  200 an x  300 then we have the following graph:

7
d

300
A B
300
200
500
500
E Government Center

Station 300
500
C D 200
200

Example 8.
RAVMAK Corporation developed a DSP (digital signal processor) that can
translate voice over IP (Internet protocol) signals. The DSP processor can take a data
signal, a fax in, and a voice input from one port and can send it out over IP. The way
the processor works is it has internal currents that translate analog to digital signals, and
digital to analog signals. The processor takes these currents at different frequencies and
combines them and translates them out back to the port, and then sends it out over IP.
Within the processor there are 4 digital to analog converters. These converters handle the
entire analog to digital conversions. These converters are labeled 1, 2, 3, and 4 on the
flow chart. The current coming into the processor is 20 mA at converter 4, and the
current that leaves converters 1 and 3 is 10 mA. The currents combine at converters 1
and 3 to the total current that originally entered the circuit that was 20 mA. There is one
limitation to the circuit design, it has a limiting factor of circuit, and the circuit can only
handle a maximum of 25 mA per node, so the input and combination of currents at any
node can never exceed 25 mA. The complete network is illustrated below:

X1
1
1 2

X3

X2

X4

3 4
1020

36
 A. Doerr

Just as a second reminder the DSP circuit cannot exceed 25mA per a node and
the total input at converter 4 must equal to sum of the outputs of converters 1 and 3.
A.) Solve this system for current flow for Xi, i = 1, 2, 3, 4.
Solution:
From the figure, we have the following linear equations:
Converter 1: X2 + X3 – X1 = 10
Converter 2: X1 + X4 = 0
Converter 3: X2 + X4 = -
10 Converter 4: X3 = 20
The augmented matrix for this system is:

-1 1 1 0 10
1 0 0 1 0
0 –1 0 –1 10
0 0 1 0 20

Gauss-Jordan elimination produces the matrix:

0 0 0 0 0
1 0 0 1 0
0 –1 0 –1 10
0 0 1 0 20

Let X4 = s we have:
X1 = -s -X2 – 10 = s X3 = 20
where s is a real number. Thus this system has an infinite number of solutions.

Find the current flow pattern when X2 = 0

If X2 = 0, then we have the following
graph:

37
 A. Doerr

1010
1
1 2

20

-10

3 4
1020

C.) Find the current flow pattern when X2 =

10 If X2 = 10, then we have the following
graph:
20
10

1
1 2

20

10

3 4
1020

38
 A. Doerr

Example 9

The following figure shows flights per day from selected airports in various cities to
other cities’ airports. The routes shown can be interpreted as alternative ways to travel
from Los Angeles airport to Boston airport. In this problem, we will analyze the effects
of changing the number of flights to and from intermediate cities’ airports. The results
can be used as a means to decide which path(s) to take when flying from Los Angeles
to Boston. The more number of flights might lead to increased delay times which
might prevent a traveler from choosing that route (edge). On the other hand, the more
number of flights means more frequent flights per day, which might make impatient
travelers prefer this route.

70
Chicago Boston

X1 50

X2
Denver Washingto n D.C
X3
60
40
X4
X5
Los Angeles Atlanta
Houston

100 X6

Solving the system

From the figure, we have the following linear equations:

Junction Denver: 60 = x1 + x2 + x3

Junction Houston: 100 = x4 + x5 + x6

Junction Chicago: x1 + x4 = 70

Junction Atlanta: x3 + x6 = 40

Junction DC: x2 + x5 = 50

39
 A. Doerr

Re-organizing the equations, we have:

x1 + x2 + x3 = 60

x4 + x5 + x6 =

100 x1 + x4 = 70

x3 + x6 =

40 x2 + x5

= 50

The augmented matrix for this system is:

1 1 1 0 0 0 60
0 0 0 1 1 1 100
1 0 0 1 0 0 70
0 0 1 0 0 1 40
0 1 0 0 1 0 50

Gauss-Jordan elimination produces the matrix:

1 0 0 1 0 0 70
1 1 0 0 0 -1 20
0 0 1 0 0 1 40
0 1 0 0 1 0 50
0 0 0 0 0 0 0

This matrix gives us the following equations:

x1 + x4 = 70

x1 + x2 – x6 =

20 x3 + x6 = 40

x2 + x5 = 50

Further simplification of the equations leads to the following:

x6 = x1 + x2 – 20 = (70 – x4 ) + (50 – x5 ) – 20 = 100 – x4 – x5 => x4 = 100 – x5 –

x6 x1 = 70 – x4 = 70 – 100 + x5 + x6 = x5 + x6 – 30

40
 A. Doerr

Putting the variables in order, we have:

x1 = x5 + x6 -

30 x2 = 50 – x5

x3 = 40 – x6

x4 = 100 – x5 – x6

Letting x5 = s and x6 = t, we get:

x1 = s + t –30, x2 = 50 – s, x3 = 40 – t, x4 = 100 – s – t

where s and t are real numbers. Thus this system has an infinite number of solutions.

Using the equations that are just found, we are now ready to analyze the traffic under
different circumstances.

a) What is the traffic load when there is no flights from Houston to Atlanta and only
30 flights per day from Houston to Washington DC?

This problem states that s = 30, t =

0 x1 = 30 + 0 – 30 = 0

x2 = 50 – 30 = 20

x3 = 40 – 0 = 40

x4 = 100 – 30 – 0 = 70

b) What is the traffic load when there is no flights from Houston to Washington DC
and only 35 flights from Houston to Atlanta?

According to the problem, we have s = 0, t =

35 x1 = 0 + 35 – 30 = 5

x2 = 50 – 0 = 50

x3 = 40 – 35 = 5

x4 = 100 – 0 – 35 = 65

41
 A. Doerr

c) How is the traffic when there is no flights from Denver to Chicago, but no
other restrictions flights to other cities?

From the problem statement, we have x1 =

0 0 = x5 + x6 – 30 => x5 + x6 = 30

x2 = 50 – x5

x3 = 40 – x6

x4 = 100 – x5 – x6 = 100 – (x5 + x6 ) = 100 – (30) = 70

as a result of no flights from Denver to Chicago, we see that the number of flights
from Houston to Chicago must be 70 per day and the total number of flights from
Houston to Washington DC and Atlanta must be 30 per day.

d) What if there were no flights to Washington DC?

This states that x2 = x5 = 0,

x1 = 0 + x6 – 30

0 = 50 – 0 => 0 = 50

here, we see that there is no solution to this problem. This is because there are 50
flights per day going from Washington DC to Boston but if the incoming flights are
restricted, there is no way 50 flights can be going out.

e) How about the case when there is no flights from Houston to Atlanta and the
number of flights from Houston to Washington DC is restricted to 10?

From this statement, we have s = 10, t =

0 x1 = 10 – 30 = -20

x2 = 50 – 10 = 40

x3 = 40 – 0 = 40

x4 = 100 – 10 = 90

In this case we see that x1 is a negative number. This doesn’t make sense because it
is impossible to have a negative number of flights from a city to another one. It might
be possible to have a number of flights in the reverse direction however, that is not
what is being analyzed here, that is, we are analyzing flights going in one direction.

42
 A. Doerr

As for the capacity of the routes (edges), there is theoretically no limit since infinite
number of planes can be in the air simultaneously (assuming there is no limit to the sky)
however, this does not mean that the airports can handle all the traffic. So the
capacity limits are the result of airport limitations and not the routes themselves.

f) What are the ranges of s and t, assuming that negative numbers don’t make sense?

Since negative numbers don’t make sense, the minimum either variable can be is 0
(zero), that is, smin = tmin = 0.

Letting s = smin = 0, we get:

x1 = x6 – 30 x2 = 50 – 0 =

50 x3 = 40 – x6 x4 = 100 – x6

From the equations, we see that in order for x1 to make sense (not be negative), we need
x6 to be greater than or equal to 30. for x3 to make sense, we need x6 to be less than or
equal to 40. this gives us our range for x6

40 x6 30

Letting t = tmin = 0, we get:

x1 = x5 - 30 x2 = 50 – x5

x3 = 40 – 0 = 0 x4 = 100 –

x5

From the equations, we see that in order for x1 to make sense, we need x5 to be greater
than or equal to 30. in order for x2 to make sense, we need x5 to be less than or equal
to 50, giving us the range for x5

50 x6 30

43
 A. Doerr

The Row Reduction Method for Determining the Inverse of a

Matrix (This is extra material we will cover it only if time permits)

In week 5 in the notes we defined the inverse of an n x n matrix. We noted that not all
matrices have inverses, but when the inverse of a matrix exists, it is unique. This enables
us to define the inverse of an n x n matrix A as the unique matrix B such that
AB = BA = I, where I is the n x n identity matrix. In order to obtain some practical
experience, we developed a formula that allowed us to determine the inverse of invertible
2 x 2 matrices. We will now use the Gauss-Jordan procedure for solving systems of linear
equations to compute the inverses, when they exist, of n x n matrices, n 2. The
following procedure for a 3 x 3 matrix can be generalized for n x n matrices, n 2.

1 0 1 1 0 0 
 
From exercise 6, week 6 we know that the matrix1 1 0 0 1 0  can be interpreted
0 2 1 0 0 1 
as solving 3 systems of three equations three unknowns. By now you should have
written out the systems.
1 0 1
If A = 1 1 0 and if we use the above definition to find the inverse of A. Then we
 
0 2 1
 x11 x1 x13 
2 
want
 a 3 X 3 matrix B such that AB = I. Assume B = x22 x23 then the equation
x21
 
 x31 x32 x33 
AB =I becomes
1 0 1  x11 x1 x13 1 0 0
 
   2
x23  
1 1 0 x21 x22 = 0 1 0 . Write out the three systems of 3 equations 3
     
0 2 1  x32 x33 0 0 1 
 x31 
unknowns that this equation produces. These should be the same systems that you wrote
previously. You should know understand why the procedure given in the following
examples works.

44
 A. Doerr

1 0 1

1) Find the inverse A  1  1 0
 
of  0 2 1

1 0 1 1 0 0 1 0 1 1 0 0

 1 0 0 1  ( 1) R 1  R2 1 1 1 1 0
 1 0      

 0
0 2 1 0 0 1  Note:
0 2 Row
1 1 (R
0 1) does
0 not change

 0 1 0 0 1

   1
R 3 R2
1 0 1 1

0 1
1
 2 1 0 0
0
Note: Row 3 (R3) does not change.

 0 1 1 0 0
1 1 
2) R  0 1 1 1
  2  3  
( R

0 0 1 2  1
 2
0
Note: Row 2 (R2) does not change.

 0 0 1 2 1
1 1 
1) R  0 1 1 1
  3  1  
( R

0 0 1 2  1
 2
0
Note: Row 3 (R3) does not change.

1 2 1
 
So A = 1 1
-1
1
 2   1 
-1
Check that A A = 2
I.

45
 A. Doerr

 1 1 0
 
2) Find the inverse B  1 1 1
 
of  0 1 1

1 1 1 0 0 1 1 0 1 0 0
0 
1 1 1 0 1 0  ( 1) 0 1 1 1 0

 
1  2  0
R R

   
 1 0 0  1 1 0 0 1 
0 1 1  0 1 1 0 1 0 0

 i
   1
nterc han ge
 1 0 0 1
 0 1 1 1 0
   0
R2 and R3

 1 0 1 0 0
0 

1
0
 R  
  2  3
R
1 0 1 1
 
0 0 1 1 1 1
0

 0 0 2 1 1
1 
     1 0 1 1 1  . So B-1 = ? Check?
R 2 R1

 0 0 1 1 1 0 

0

 0 2
1 
3) Find the inverse of the
 1 0
matrix C 2 
  1 1 
 1
1 0 2 1 0 0 1  0  2  1 0 0
2 1 0 0 1 0 R1  2 1 0 0 1 0
   
 1 0 0  1 1 0 0 1
1 1 1   1
1 0  2 1 0 0
   0 1
  1  2 0 R1  4
2R R

1  
R3
1 1
0
1 0 2

46
 A. Doerr

1 4  10
2 1
1 3
0 0 1
1 0 0

2 1  0
1 0
1 0  2  1 0
 
R 2
   0
R3
1 0 0

0 0 4 2 1
1
7 3 1

47
 A. Doerr

 1
1 0 0 2 2
2 R3 R1 7 7 7
7   0 1 2 1 0
4 
 3 1 1
0 0 7 
 1 2 2
 7 7 7
 1 0 0 

4
R R
3 2 3 1
7   0 1 0  . C-1 = ? Check?
2 7 7
 7
 3 1 1
0 0 1
 7 7 7

Exercises:

Use the above procedure to determine the inverses of the following matrices if they
exist. Check your solutions.

1
 0 0 
1. 2 2 1
 
1 1 1 

1 1 0 
 
2. 2 1 3
1 1 1 

 
2 1 0
3. 4 1 3 

3
 3 1 2


1 0 0 
4. 2 2 1
 
1 1 1 

48
 A. Doerr

49