Faculty of
Engineering
Math 1 – Linear algebra
Lecture (2) – Elimination methods
Outline
Solving a system of linear equations (SLE)
- Solution nature
- Gauss elimination method
- Gauss-Jordan elimination method
- Reduced Row Echelon form.
2
SLE
Unique
Infinite number No solution
solution
of solutions
x+y=2 x+y=2 x+y=2
x–y=0 3x + 3y = 6 x + y =3
Consistent system Inconsistent system
y y y
x x x
3
Elimination method for solving a SLE
The basic strategy is to replace one system with an equivalent system (i.e., one with
the same solution set) that is easier to solve.
Solving a triangular system
x+y +z=6 x=1
– 3y – z = –9 y=2
z=3 z=3
Gauss elimination (Two-phase algorithm)
Forward elimination Backward substitution
• Bring the given system into a
• Solve the resultant triangular
triangular one
system
• Done by elementary row
• Done by Backward substitution
operations
4
x+y=2
x–y=0
s+t=2 2x +3y = 2
s–t=0 4x – 8y = 0
When you solve a system of linear algebraic equations,
what quantity affects your decision: the name of the
variable or the coefficient of the variable?
5
6
Gauss elimination by example
Solve
x − 2 y + z = 0, 2 y − 8z = 8, −4 x + 5 y + 9z = −9
1 −2 1 0
augA = 0 2 − 8 8 r3 + 4 r1 → r3
− 4 5 9 − 9
- The element used in
1 − 2 1 0 elimination is called
0 2 − 8 8 r2 / 2 → r2 “pivot element”.
augA
- It position is called
0 − 3 13 − 9 “pivot position”.
- Its column is called
1 − 2 1 0
“pivot column”.
0 1 − 4 4
augA r3 + 3 r2 → r3
0 − 3 13 − 9
7
Gauss elimination by example (cont’d)
1 − 2 1 0
0 1 − 4 4
augA
0 0 1 3
• Forward elimination is now completed.
• Start backward substitution:
z = 3,
y = 16,
x = 29.
Two linear systems are called equivalent if they have the same solution set.
Two matrices are called row equivalent if there is a sequence of elementary
row operations that transforms one matrix into the other.
8
If the augmented matrices of two linear systems are row equivalent, then the two
systems have the same solution set.
Elementary row operations
Gauss elimination method uses a combination of the
following “elementary row operation” to produce a
“triangular-like equivalent” system:
1. Add to one row a multiple of another row.
2. Multiply all the entries of a row by a non-zero constant.
3. Interchange two rows.
➢ This systematic (algorithmic) method can be applied to solve
any system of linear equations.
➢ It is the most efficient solution method in terms of the
computational time.
➢ The nice “triangular” form is not always reachable. Another
9
standard form will be the target.
No solution case
Example
Find the solution of
2 x − 3 y + 2 z = 1, y − 4 z = 8, 5x − 8 y + 7 z = 1
Forward backward
elimination substitution ?
• A row of the form [0 0 . . . 0 k] indicates contradiction in the
given system.
• The system has no solution.
• The equations (constraints) need to be revised.
10
Infinite number of solutions case
Example
Find the solution of
x − y + z = 3, 2 x − y + 4 z = 7, 3x − 5 y − z = 7
Forward backward
elimination substitution
• The non-zero rows represent the independent rows (equations).
• If the number of independent equations < number of variables, then
some variables can be freely chosen.
• So, the system has an infinite number of solutions.
• Basic variables are expressed in terms of the free variables.
• We choose,
– Pivot columns as the basic variables,
– Non-pivot columns as the free variables.
11
Changing rows is needed
Example
Find the solution of
x + 2 y − 3 z = 11,3 x + 6 y − 8 z = 32, − 2 x − y = −7
Forward
elimination
• Pivots can’t be zero.
• If the candidate pivot is zero, search down its column for a
non-zero pivot; then, change rows.
Q: What to do when a non-zero pivot can’t be found?
A: Continue with the next column. See next slide.
12
Continue with the next column
Example
Find the solution of
x − 2 y + 6 z − 5w = 29, − x + 2 y − 3 z + 2 w = −14, 2 x − 4 y + 9 z − 6 w = 44
Forward
elimination
• If a non-zero pivot can’t be found in a certain column,
– This column will be a non-pivot column.
– Continue elimination with the next column.
• For this example, the system has an infinite number of
solutions (why?).
• Basic variables are x, z and w. Free variable is y.
• Solution: x = 2 y – 2, z = 6, w = 1
13
Solving a homogeneous system A x = 0
Example
Find the solution of
x + y = 0, 2 x − 3 y − z = 0, x − y + 2 z = 0
Forward backward
elimination substitution
• Homogeneous system are always consistent.
• If each column is a pivot column,
– The solution is unique.
– It is the zero solution (trivial solution).
• If non-pivot column(s) exist,
– The system has an infinite number of solutions.
– Basic variables are given in terms of the free variables.
14