# Discrete Structures Need done 3/26

All necessary info attached.

Some questions refer to textbook or notes photos of textbook page attached and so are notes..

1

Exam II (The exam is due March 27th at 8am) Discrete Structures I

Directions: Exam 1I is due Wednesday, March 27th , by 8am. Answer all questions
carefully. Do all steps with detailed explanations. I prefer that you send your solutions
electronically. They need not be typed. Follow this procedure:

2) Click on Exam II dropbox
3) Scroll down and next to “Add Attachments” click the “Browse My Computer” button to attach your
exam. Note, make sure you to attach your exam in Microsoft Word format or as a PDF file if scanned.)
4) Click Submit to send your exam to me.
Do not use the web board to submit exams. If you wish to FAX or mail your answers to me they

again, need not be typed but I must receive them by the due date and time. Make sure the
course number and name (92.321, Discrete Structures I) as well as your name and my name
appear on the top of each answer sheet. I must receive all exams by the due date. Use the
cover sheet for the FAX ((978) 934-4064). To mail exams to me send them to:

Prof. Alan W. Doerr
Mathematical Sciences Department
UMASS Lowell
I University Ave.
Lowell, Mass 01854

1. (15 pts.) Note the contrapositive of the definition of one-to-one function given on
page 141 of the text is: If a ≠ b then f(a) ≠ f(b). As we know, the contrapositive is
equivalent to (another way of saying) the definition of one-to-one.
(a) Consider the following function f: R → R defined by f(x) = x2 + 4 . Use
the contrapositive of the definition of one-to-one function to determine (no proof
necessary) whether f is a one-to-one function. Explain

(b) Compute f  f.

(c) Let g be the function g: R → R defined by g(x) = x3 + 3. Find g -1. Use the
definition of g -1 to explain why your solution, g -1 is really the inverse of g.

2. (5 points) Text page 169 number 34, part b.

3.(15 points) Let A =

1

1 1

2 1 1

1 1 2

− − 
 − 
 − − − 

, B =

1 1 1

2 2 1

2 1 3

− 
 − 
  

Photo attached Part B only.

2

and C =

2 2

1 0

1 1
− 
 − 
  

Compute:
(a) AC + BC (It is much faster if you use the distributive law for matrices first.)

(b) 2A – 3A

(c) Perform the given operation for the following zero-one matrices. See the
text, page 182, for the definition of the symbol .

1 1 1 1 1 1

1 0 0 0 1 1

0 1 1 0 0 1

   
   
   
      

4. (10 points) Let A =
2 2

3 4

 
 
 

.

(a) Use the formula for finding the inverse of a 2×2 matrix given in exercise 19
page 184 to find A-1 .
(b) Use the definition of the inverse of a matrix given in the text just prior to

examples). You must show all work. Here are a couple of online sites if you need
Elimination.

5. (15 points) Solve the following systems of equations using the method outlined in
week 7 (Part I) of the notes. Your procedure should be in matrix form as was done in
Example 3. (

x1 + x2 + x3 = 1
2×1 – x2 + x3 = 2
-1×2 + x3 = 1

6. (10 points) Week 7 (Part II, Systems Which Do Not Have a Unique Solution) of the
notes. Page 5 number 2.

7. (5 points) Look up the definition (not the formula) for the inverse of a matrix. Note,
the definition is given in your notes and in the text on page 184, prior to exercise 18.
Use the definition of the inverse of a matrix to do exercise 18 on page 184 of the text.

8. (10 points.) We know that matrix algebra behaves similar to
(but not exactly the same as) regular algebra. The statements in parts a and b illustrate a
couple of the differences between the two structures.

Photo attached Question 7

Photo attached showing example. Question 4

Notes attached.

3

Let A and B be arbitrary n x n matrices whose entries are real numbers.
(a) Use basic matrix laws only to expand (A + B )2. Explain all steps. Note the

basic matrix laws are given in your notes, week 6 pg.4. Hint: Use the
distributive laws.

(b) Is (A – B)(A + B) = A2 – B2 ? Explain as you did in part (a).

9. (15 pts) Read pages 311 to 318 and study examples 1, 2 and 3. Then do

Text, page 329, number 4.

Extra Points

i. Solve for B:
2 2 3 0

B =
3 4 1 2

   
   
   

. Hint, one way is to use problem 4 a.

ii. Text page 153 number 12 parts c and d. Explain, but no proof necessary.

iii. This can be used for extra credit for either Exam 2 or exam 3. Everyone
should try it. It’s a nice application.

Hand it in for exam 2 when exam 2 is due or for exam 3 (when exam 3 is due)
Project: Make up a meaningful network example. In the notes, week 7 part III,

on Network Analysis I have given you several different “flow models”. Your project
does not have to mimic one of these. Try to make it different than those presented in the
notes.
a) Your example must be well defined. Define the problem clearly.

b) Your example should involve solving a system of equations with an “infinite
number of solutions”. Actually, once you place restrictions on the variables (They may
be integers and see part f.) the number of solution may be large but not an infinite
number.

c) Solve your system of equations any way you wish, but describe your solutions
clearly.

d) Explain your results with two or three examples. That is, compute the flow
when the free variable are specific numbers.

e) Interpret your results. Do they make sense? Do negative values make sense?
f) Should there be a maximum capacity for each edge? If so, make up some
reasonable maximum capacity for each edge.

Photo attached. Question 9

1

Week7 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

2×2 + x3 = 2

or

x1 + 0 x2 + x3 = 1

x1 – x2 + 0x3 = 0 Why?

0x1 + 2×2 + 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

1×1 + 0 x2 + 0x3 = 1

0x1 +1 x2 + 0x3 = 1

0x1 + 0 x2 + 1

x3 = 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

2×2 + 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 + 2×2 + 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 + 2×2 + 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 + 2×2 + 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

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.

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

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.

4×1 + 2×2 + x3 = 1

2×1 + x2 + x3 = 4

2×1 + 2×2 + 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

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

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 1×1 + 2×2 = 1

2×1 + 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,

1×1 + 2×2 = 2

2×1 + x2 = 3

Note we can use the same steps that we used in solving the above system because the coefficient
matrix is the same

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

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.

1×1 + 2×2 = 1 1×1 + 2×2 = 0

2×1 + x2 = 0 and 2×1 + 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
 
 
 

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 3×3 coefficient matrix given in problem 6, and if B (of the definition of
inverse) is a 3×3 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

2×2 + 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

‐1×2 + x3 =  2            ‐1×2 + 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

1

Part2: 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 of part 1(except for exercise 1 parts d and e)
the systems of equations had a unique solution. That is, a single value for each of the variables.

In example 3 we found the solution to be  7 23 3,  . This means that the graphs of the two lines in
example 3 intersect at this unique point. 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/cases:

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. Discussed in part 1

.

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. Discussed
in part 2.

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. Discussed in part 2.

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 6. 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 its simplification follows. Recall,

we try to express the matrix

1 2

1

2 4

2

 

in the form 1
2

1 0

0 1

b

b
 
 
 

from which we can read off the

solution. However after one step we note that

1 2 1
2 4 2
 
 
 

1 22 R R 
1 2 1

0 0 0

 
 
 

. It should be clear to the reader that no matter what further

elementary row operations we perform on the matrix
1 2 1

0 0 0
 
 
 

we cannot change it to the form

we hoped for, namely, 1
2

1 0
0 1
b
b
 
 
 

. To understand what our result means simply write the system

of equations that the matrix
1 2 1

0 0 0
 
 
 

represents, that is,

x + 2y = 1

0x + 0y = 0.

The first equation tells us that x = 1 – 2y, or equivalently that y = 1 2 (1 – x), so that (1,0),

(-1,1), and (-5,3) 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 7. Determine the solutions of the system of equations whose matrix is row equivalent

to
1

0 0 1

0 1 1 0

0 0 0 0

 
  
  

. Give three examples of the solutions. If we use the variables x1, x2, and x3 the

system of equations which is represented by this matrix is:
1x

1
+ 0x

2
+ 0x

3

= 1 This equation simply says that x1 = 1.

0x
1
+ 1x

2
+ -1x

3
= 0 This equation simply tells us that x3 = x2.

0x
1
+ 0x

2
+ 0x

3
= 0 All this equation says is that 0 = 0.

So equation 1 indicates that there is a restriction on x1, namely it must be 1. Equation 2 gives us
restrictions on x2 and x3, namely, they must equal each other. Equation 3 does not place any
restrictions on any of the variables.

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

Example 8. Solve the system of equations whose matrix is

2 1 0 1

1 2 1 0

0 3 2 1

 
   
   

. Give three

examples of the solutions.

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

interchange rows 1 and 2
and then -1R

1 2 1 0
2 1 0 1
0 3 2 1

 
  
   

1 2 -2R R
1 2 1 0

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

2 3 R R
1 2 1 0

0 3 2 1
0 0 0 0

 
  
  

.

At this point we could row-reduce the last matrix further by but this is really not
necessary. If we call the variables x

1
, x

2
and x

3
the system of equations that this last matrix

represents is: x1 – 2×2 + x3 = 0

3x
2
– 2x

3
= 1.

From the latter equation we can say x
3
= ½ (3x

2
– 1). If we substitute this expression for

x
3 in the first equation we obtain x1 – 2×2 + ½ (3×2 – 1) = 0 or x1 = 2×2 – ½ (3×2 – 1) which can be

simplified to x
1
= ½(x

2
+ 1). If we replace x

2
by 0 then one solution is x

1
= 1/2, x

2
= 0 and

x
3
= -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 in solving systems of equations is that when the
number of unknowns is greater than the number of equations. For example:

x1 + x2 – 3×3 = -1

x2 – x3 = 0.

Here we have only two equations but three unknowns

But upon closer inspection this is simply another form of the above examples as we show
in example 9.

Example 9. Solve the system of equations

x1 + x2 – 3×3 = -1

x2 – x3 = 0.

This system is the same as the system

x1 + x2 – 3×3 = -1

0x1 + x2 – x3 = 0

0x1 + 0x2 + 0x3 = 0,

So we can represent the above system by the matrix
1 1 3 1

0 1 1 0

  
  

or the matrix
1 1 3 1

0 1 1 0
0 0 0 0

  
  
  

.

Clearly no matter what elementary row operations we perform on this matrix we cannot change

it to the form
1

2
3

1 0 0

0 1 0

0 0 1
b
b
b

 
 
 
  

. For this reason it is common practice to rewrite the matrix without

the rows which contain all zeros, so that the matrix of the given system is
1 1 3 1

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

and the

reader can show that this matrix can be reduced to
1 0 2 1

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

which gives us the system

x1 – 2×3 = -1

x2 – x3 = 0

The second equation tells us that x3 = x2

Substitute this value of x2 in first equation to obtain

x1 = 2×2 – 1

So all solutions of the given system are ordered triples of the form (2×2 – 1, x2, x2)

where x2 can be any real number. If we chose x2 = 0 then we find that (-1, 0, 0) is one example

of a solution to this system of equations and if we replace x3 by 2 we obtain (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 given in this example 9 can also be
described as any ordered triple of the form (x1, ½(x1+ 1), ½(x1+ 1) where x1 is any real

number. So if x1= 1 we obtain the triple (1, 1, 1) as a solution, which certainly satisfies the

original system of equations. To obtain my form of the solution set just take the equation x1 =

2×2 – 1 and solve for x2 and then for x3.

Exercises

1. Determine the solutions of the system of equations whose matrix is row equivalent to

. 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

. 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

. Give three examples of the solutions. Verify that your solutions satisfy
the original system of equations.

1 0 0 1

0 1 2 0

0 0 0 0

1 0 0 1

0 1 2 3

0 0 0 0

1 0 1 1
0 1 3 1

0 0 0 0

4. Determine the solutions of the system of equations whose matrix is row equivalent to

. 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

equivalent to . Give three examples of the solutions.

Verify that your solutions satisfy the original system of equations.

1 1 1 1
0 2 3 2
0 0 0 0

1 1 1 1
1 2 2 2
0 0 0 0