MAT 1302A - Mathematical Methods II: Alistair Savage

MAT 1302A Mathematical Methods II
Alistair Savage
Mathematics and Statistics
University of Ottawa
Winter 2014 Lecture 2
Alistair Savage (uOttawa)
1 / 28
Overiew
Announcements
DGDS start next week.
Last Time
Overview of linear algebra
Linear equations
Systems of linear equations (linear systems)
Solution sets
Matrices (coefficient matrix and augmented matrix)
Todays goal
Develop a precise procedure for solving any system.
2 / 28
Matrix terminology
Matrix terminology
zero row or column: row or column with all entries equal to zero
nonzero row or column: row or column with at least one nonzero entry
leading entry of a row: leftmost nonzero entry
Examples
2
0
0
0
0
0 0 0
0 1 5 9
0
0 0 0
4
0 0 8
0 1 3 4
0 0 0 0
0 0 0 8
3 / 28
Terminology
(Row) Echelon form
A matrix is in (row) echelon form if it satisfies the following 3 conditions:
1
All nonzero rows are above all zero rows.
The leading entry of a nonzero row is to the right of the leading entry
of any row above it.
All entries in a column below a leading entry are zeros (this actually
follows from the second condition).
Reduced (row) echelon form

A matrix is in reduced (row) echelon form if it satisfies the above 3
properties and:
4
All leading entries are 1s.
Each leading 1 is in the only nonzero entry in its column.

4 / 28
Terminology
A matrix in echelon (respectively reduced echelon) form is called an

echelon matrix (respectively reduced echelon matrix).
Note: The word echelon means step-like formation (military, etc.).
5 / 28
Examples
Example 1
1 0 0 1
0 1 0
0
2
0 0 1
Reduced row echelon form (RREF)
Example 2
1 2 3
1
1
0
0 1
2
0
0
0
3
0
0
0
0
0
0
0
0
Row echelon form (EF)

6 / 28
Examples
Example 3
1 0 0 1
1 1 0
0
2
0 0 1
Not in echelon form
Example 4
0
0
0
0
1 2 3
1
1
0
0 2 1
0
0
0
3
0
0
0
0
Not in echelon form

7 / 28
Examples (cont.)
Example 5
0 0
6= 0
0 0
6= 0
0 0
6= 0
0
0
0 0
0 0
0
0
0
0
0
0
6= 0
0
0 0
0 0
0 0
0 0
EF
(=arbitrary entry)
Example 6
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
RREF
8 / 28
Reduced row echelon form

Theorem
Every matrix is row equivalent to exactly one reduced echelon matrix.
Important note: A matrix may be row equivalent to many echelon
matrices.
Example

1 0
,
0 1

2 0
,
0 3
and

1 1
0 1
are all row equivalent and are all in echelon form. However, only the
leftmost matrix is in reduced row echelon form.
9 / 28
Overview
Goal: Develop an algorithm for solving LSs.
Technique:
/ Solution set
O
Linear system

Augmented matrix
row reduction
/ EF or RREF
We first focus on the bottom arrow (row reduction). We will forget about
LSs for the time being.
Lets work through another example and try to keep track of why we are
performing each step.
10 / 28
Example
Reduce the following matrix to EF.
0
0 1 2
7
2
2
R1 R2 0
1
3
2
5

2
2
1
3
6
2
4 2 7 2 17
4
2 1 3 2 5
2
R1 +R3
R2 +R4 0
0
0
1
2
7
2R1 +R4

0 0 0 4 3 0
0
0 0 1 2 7
1
3
2
5
0 1 2
7
1
3
6
2
2 7 2 17
1 3 2 5
0 1 2 7
EF
0 0 4 3
0 0 0 0
11 / 28
Pivot positions and columns

Definition
A pivot position in a matrix A is a location that corresponds to a
leading 1 in the RREF of A (or a leading entry in an EF of A).
A pivot column is a column of A that contains a pivot position.
Previous example
0 1 2
7
0
1
3
2
5 row reduction
2

2
1
3
6
2
4 2 7 2 17
2
0
0
0
1
0
0
0
3
-1
0
0
2
2
4
0
7
EF
3
0
The boxed positions are the pivot positions and the first, third and fourth
columns are the pivot columns.
12 / 28
Pivots
Definition
A pivot is a nonzero number in a pivot position used to create zeros via
row operations.
Previous example
0
0
2
1
2
1
4 2
2
R1 +R3
0
2R1 +R4

0
0
1 2
7
2
3
2
5 R1 R2 0

3
6
2
2
7 2 17
4
1
3
2 5
2
0 1 2 7
R
+R
4
2
0
0
0
0
4 3
0 1 2 7
0
1
3
2
5
0 1 2
7
1
3
6
2
2 7 2 17
1 3 2 5
0 1 2 7
EF
0 0 4 3
0 0 0 0
The pivots are 2 and 1 (4 would also be a pivot if we continue to RREF).

13 / 28
Row reduction algorithm (Gauss-Jordan elimination)

Example: Reduce the following to EF and then RREF
0
0
2
4
2 0 10
0 1 2 3 1 0 3
0
6
6
6
9 0
6
0
3
1 5 1 0 20
Step 1: Begin with the leftmost nonzero column. This is a pivot column
and the pivot position is at the top.
Step 2: Select a nonzero entry in the pivot column as a pivot. If necessary,
interchange rows to move this entry into the pivot position.
0 -1 2 3 1 0 3
R1 R2
0 0
2
4
2 0 10

0 6
6
6
9 0
6
0 3 1 5 1 0 20
14 / 28

0
0
0
0
-1
0
6
3
2 3 1
2
4
2
6
6
9
1 5 1
0 3
0 10
0
6
0 20
Step 3: Use row replacement operations to create zeros in all positions

below the pivot (i.e. add appropriate multiples of row containing the pivot
to the rows below it).
0 1 2 3 1 0 3
6R1 +R3
0 0
2
4
2 0 10
3R1 +R4

0 0 6 12 3 0 12
0 0 7 14 4 0 29
Step 4: Ignore (cover) the row containing the pivot position and all rows
above it. Apply steps 1-3 to the remaining submatrix. Repeat this process
until there are no more nonzero rows to modify.
15 / 28

0 1 2 3 1 0 3
0 0
2
4
2 0 10
0 0 6 12 3 0 12
0 0 7 14 4 0 29
0 1 2 3 1 0
3R2 +R3
7
R
+R
2
4
0 0
2
4
2 0
2
0 0
0
0
9 0
0 0
0
0
3 0
0 1 2 3 1 0 3
0 0
2
4
2 0 10
0 0
0
0
9 0 18
0 0
0
0
3 0 6
0 1 2 3 1 0
13 R3 +R4 0
0
2
4
2 0

0 0
0
0
9 0
0 0
0
0
0 0
3
10
18
6
3
10
18
0
EF
16 / 28
Step 5: Beginning with the rightmost pivot and working up/left, use a
scaling operation to make each pivot a 1 and use replacement to create
zeros above each pivot.
0 1 2 3 1 0 3
0 0
2
4
2 0 10
0 0
0
0
9 0 18
0 0
0
0
0 0 0
0 1 2 3 1 0 3
1
R3 0
0
2
4
2 0 10
9
0 0
0
0
1 0 2
0 0
0
0
0 0 0
0 1 2 3 0 0 1
R3 +R1
2
4
0 0 6
2R +R2
0 0
3
0 0
0
0
1 0 2
0 0
0
0
0 0 0
17 / 28
0 1 2 3
0 0
4
2
0 0
0
0
0 0
0
0
0 1 2 3
1
R
2
0 0
1
2
2
0 0
0
0
0 0
0
0
0 -1 0 1 0
2R2 +R1
0 0 1 2 0

0 0 0 0 1
0 0 0 0 0
0 1 0 1 0
0 0 1 2 0
R1

0 0 0 0 1
0 0 0 0 0
0
0
1
0
0
0
1
0
0 1
0 6
0 2
0 0
0 1
0 3
0 2
0 0
5
3
0
0
0
0 0
0 5
0 3
0 2
0 0
RREF
18 / 28
Another example
4
4 3 13
2
2 4 4 0 7
4
8
4 0 20
2 4 4 3
R2 R3
0 0 -4 6
0 0 0 3
3R3 +R1
2 4 4
6R3 +R2
0 0 -4
0 0 0
2 4 0
4R +R1
0 0 1
2
0 0 0
R1 +R2
2 4 4
6
2R1 +R3
8 0 0 0
2
0 0 4
13 6
2 4 4
1
R3
6 10 3 0 0 4
6
2
0 0 0
0 7 8
2 4 4
1
R2
4
0 6 14
0 0 1
1 2 23
0 0 0
1 2 0
0 13 6
1
R
2 1
7
0 0 1
0 3
2
2
2
0 0 0
1 2
3
3 13 6
3
6
2
6 6 10
3 13 6
6 6 10
2
1
2
3
0 7 8
7
0 3
2
2
2
1 2
3
13
0 2
3
7
0 3
2
2
2
1 2
3
19 / 28
Different algorithms
Our algorithm allows you to reduce any augmented matrix to EF or RREF.

The algorithm is not unique there are other ones that work (e.g.
algorithm described in the proof of Theorem REMEF in the FCLA text).
Since the RREF of any matrix is unique, any valid algorithm will give you
the same RREF in the end (assuming you dont make any mistakes).
Reducing a matrix to EF or RREF is called row reduction.
Reducing a matrix to EF is called Gaussian elimination.
Reducing a matrix to RREF is called Gauss-Jordan elimination.
20 / 28
Solutions of linear systems

Recall
/ Solution set
O
Linear system
??
Augmented matrix
/ EF or RREF
row reduction
Suppose the augmented matrix of a LS has been row reduced to the

following RREFs. What is the solution set of the LS?
Example 1
1 0 0 3
0 1 0 2
0 0 1 5
x1
x2
x3
= 3
=
2
=
5
Only solution is
x1 = 3,
x2 = 2,
x3 = 5.
21 / 28
Solutions of linear systems (cont.)

Example 2
0
0
0
0
1
0
0
0
6 11 18 0
1 1 3 2
0 1
2 5
0 0
0 9
0 = 9 contradiction
The solution set is empty (i.e. no solution).
Example 3
1 0 2 0 0
0 1 1 0 2
0 0 0 1 8
x1
+ 2x3
x2 x3
x4
= 0
= 2
= 8
The variables corresponding to pivot columns (or leading 1s in RREF) are

called basic variables (x1 , x2 , x4 here) and the others are called free
variables (x3 here).
22 / 28

Example 3 (cont.)
We have the reduced system:
x1
+ 2x3
x2 x3
x4
= 0
= 2
= 8
We solve the reduced system of equations for the basic variables in terms
of the free variables.
x1 = 2x3
x2 = 2 + x3
x3 free
x4 = 8
23 / 28

Example 3 (cont.)
x1 = 2x3
x2 = 2 + x3
(1)
x3 free
x4 = 8
Each basic variable occurs in exactly one equation. The free variables (x3
here) can have any value and the above equations determine the values of
the basic variables.
Example: If x3 = 2, the corresponding solution is
(x1 , x2 , x3 , x4 ) = (4, 4, 2, 8).
(1) is called the general solution of the LS because it gives an explicit

description of all solutions.
24 / 28
Check your answer!
Checking your answer when there are free variables

Question: We should always check our answer. How do we do that when
there is more than one solution?
Can we check each one? NO! There are an infinite number of solutions!
Answer: We should replace each basic variable with its expression in terms
of the free variables. If we didnt make any mistakes, all of the terms with
free variables should cancel.
25 / 28
Check your answer!

Example 3 (cont.)
Our system
1
0
0
was
0 2 0 0
1 1 0 2
0 0 1 8
x1
+ 2x3
x2 x3
x4
= 0
= 2
= 8
and our solution was

x1 = 2x3
x2 = 2 + x3
x3 free
x4 = 8
Substituting gives
(2x3 )
+ 2x3
(2 + x3 ) x3
= 0
= 2
8 = 8
X
X
X
26 / 28
Weekend problem (for fun)
Quarter game rules:

Square table
You and your opponent take turns placing quarters on the table
Quarter must be placed in an empty space
Game ends when one player cant play that player loses
Problem: If you are allowed the first move, how can you play to guarantee
you will win?
27 / 28
Next time
To Do:
Read Section TSS of the text.
Do the recommended exercises.
Next Time:
More on general solutions
Geometric interpretation of linear systems
Existence of solutions (when is a system consistent?)
Uniqueness of solutions (is there just one solution or many?)
28 / 28

MAT 1302A - Mathematical Methods II: Alistair Savage

Uploaded by

Copyright:

Available Formats

MAT 1302A - Mathematical Methods II: Alistair Savage

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

MAT 1302A - Mathematical Methods II: Alistair Savage

Uploaded by

Copyright:

Available Formats

MAT 1302A Mathematical Methods II

Winter 2014 Lecture 2

Alistair Savage (uOttawa)