Week-2

Karthik Thiagarajan

DISCLAIMER: THESE NOTES ARE TIED TO A PARTICULAR LIVE SESSION. THEY CANNOT
BE TREATED AS A STANDALONE RESOURCE. PLEASE CHECK THE COLUMN TITLED
REMARKS IN THE MASTER FOLDER. IF THERE ARE ANY CORRECTIONS IN THIS
DOCUMENT, THEY WILL BE MENTIONED IN THE REMARKS SECTION.

1. Gaussian elimination: Motivation 2

1.1. Example 2
1.2. Example 2
2. Row echelon Form 4
2.1. Example 4
2.2. Example 5
2.3. Example 5
3. Reduced row echelon form 6
3.1. Example 6
3.2. Example 6
4. Gaussian Elimination: dependent and independent variables 7
4.1. Example 7
4.2. Example 7
5. Gaussian elimination: Augmented Matrix 9
5.1. Example 9
5.2. Example 10
1. Gaussian elimination: Motivation

1.1. Example

x- y z
y- z -
2 3 + = 7

z
3 = 7

= 2

• Step-1: Read off the value of z from eq-(3)

• Step-2: Plug in the value of z in eq-(2), y -
• Step-3: Plug in the value of z - y - in eq-(1), x
= 2 = 1

= 2, = 1 = 1

Each step is in fact a simple linear equation with one unknown. This
process is termed backward substitution. In terms of matrix-vector
notation:

- x
- y - Ax b
2 3 1 7

z
0 1 3 = 7 ≡ =

0 0 1 2

Notice that A is an upper triangular matrix. The key idea is to get an

increasing number zeros starting from the first row. Zeros in a row is
advantageous as it eliminates variables.

1.2. Example
Here is another example:

x- y z -
x y- z
3 +4 = 3

-x y - z
2 + 3 = 7

+2 = 4

- x -
A - x y b
3 1 4 3

= , = , =

- - z
2 1 3 7

1 2 1 4

Let us now try to convert it into an upper-triangular-like matrix:

Step-1:

- - R R - -
- -
3 1 4 | 3 1 2 1 | 4

-
2

1
1

2 -
3

1
|

|
7

4
⏪⏪⏪⏫1↔ 3

3 -
1

1 4
3 |

| -
7

Step-2:

- - R R R - -
- -
1 2 1 | 4 1 2 1 | 4

- ⏪⏪⏪⏪⏪⏫
2 → 2 +2 1

- - -
2 1 3 | 7 0 5 5 | 15

3 1 4 | 3 3 1 4 | 3

Step-3:
 - - R R R - -
- -
1 2 1 | 4 1 2 1 | 4

- ⏪⏪⏪⏪⏪⏫
3 → 3 +3 1

-
0 5 5 | 15 0 5 5 | 15

3 1 4 | 3 0 5 1 | 9

Step-4:

- - R 1
R - -
- -
1 2 1 | 4 1 2 1 | 4

⏪⏪⏪⏪⏫
2 → 2
5
0 5 5 | 15 0 1 1 | 3

0 5 1 | 9 0 5 1 | 9

Step-5:

- - R R-R - -
- -
1 2 1 | 4 1 2 1 | 4

⏪⏪⏪⏪⏪⏫
3 → 3 5 2

-
0 1 1 | 3 0 1 1 | 3

0 5 1 | 9 0 0 6 | 6

Step-6:

- - R R 1
1- -
- 1 -
1 2 1 | 4 2 1 | 4

⏪⏪⏪⏪
R -R ⏫
3 → 3
6

- 1 -
0 1 1 | 3 0 1 | 3
1 → 1

0 0 6 | 6 0 0 | 1

In terms of equations, this looks like:

x- y z -
y-z
2 + = 4

z -
= 3

= 1

Answer: x = 1, y = 2, z - = 1

This process of solving a system of equations is called Gaussian

elimination. A rough outline of the algorithm:

Gaussian Elimination

• Forward elimination.
• Sequence of elementary row operations:
– swap rows
– scale rows
– add multiple of one row to another
• Upper triangular-like matrix
• Row echelon form of the matrix
• Backward substitution
2. Row echelon Form
A matrix is said to be in row echelon form if it satisfies all the
conditions given below:

• Zero-rows should come at the end.

• The first non-zero entry in every row is called the leading entry and
this should be 1.
• In every non-zero row, the leading entry is to the right of the
leading entry in the previous row.

A row is called a zero-row if all its entries are zero. Some resources
refer to the leading entry as the pivot. In some resources, the leading
entry need not be 1, it could be any non-zero number. In fact, the
Wikipedia entry for row echelon form does not require the pivot to be 1:

Figure 1: Source: Wikipedia

In our course, we will stick to the leading entry as 1.

2.1. Example

4 7 3

Compute a row echelon form of 1 2 1 .

1 1 1

Step-1

4 7 3
R R 1 2 1

1
2

1
1

1
⏪⏪⏪⏫1↔ 2

1
7

1
3

Step-2
1 R R-R 1
⏪⏪⏪⏪⏪⏫ -1 -
2 1 2 1
2 → 2 4 1

4 7 3 0 1

1 1 1 1 1 1

Step-3

1 R -R -R 1
-1 - ⏪⏪⏪⏪⏫ -1 -
2 1 2 1
3 3 1

-1
0 1 0 1

1 1 1 0 0

Step-4

1 R -R 1
-1 - ⏪⏪⏪⏪⏫ 1
2 1 2 1
2 → 2

-1 -1
0 1 0 1

0 0 0 0
Step-5
1 R R R 1
1 ⏪⏪⏪⏪⏪⏫ 1
2 1 2 1
3 → 3+ 2

-1 1
0 1 0 1

0 0 0 0

Step-6

1 R R -R 1
1 ⏪⏪⏪⏪⏪⏫ 1
2 1 2 1
2 → 2 3

1 1
0 1 0 0

0 0 0 0

1
A 1 A. Row-
4 7 3 2 1

For the matrix , is a row-echelon form of

1
= 1 2 1 0 1

1 1 1 0 0
echelon form of a matrix is not unique.

2.2. Example

1 2
Compute a row echelon form of
1 4

R R -R R R
⏪⏪⏪⏪⏪⏫ ⏪⏪⏪⏪⏫
1 2 2 → 2 1 1 2 2 → 2 /2 1 2

1 4 0 2 0 1

2.3. Example
Final example:

-
-
1 1 0 1

Compute a row echelon form of .

-
2 2 3 2

1 1 1 1

Step-1

- R R-R -
- ⏪⏪⏪⏪⏪⏫
1 1 0 1 1 1 0 1
2 → 2 2 1

- -
2 2 3 2 0 0 3 0

1 1 1 1 1 1 1 1

Step-2
1 1 0 - R R -R
1 1 1 0 - 1

- ⏪⏪⏪⏪⏪⏫
3 → 3 1

0 0 3 0 0 0 3 0

1 1 1 1 0 0 1 0

Step-4:

1 1 0 - 1
R R 1 1 0 - 1

⏪⏪⏪⏪⏫ 2 → 2 /3

0 0 3 0 0 0 1 0

0 0 1 0 0 0 1 0

Step-5:
- R R -R 1 -
1
1 1 0 1 1 0 1

⏪⏪⏪⏪⏪⏫ 3 → 3 2

0 0 1 0 0 0 0

0 0 1 0 0 0 0 0
3. Reduced row echelon form
A matrix is in reduced row echelon form if:
• It is in row echelon form
• If a column contains a leading entry, it should have only one non-
zero entry, namely, the leading entry itself.

3.1. Example

4 4 2

Compute the reduced row echelon form of 1 1 1 .

3 3 2

1
- 1
4 4 2 1 1 1 1 1 1 1 1 1 1 1

- -
1 1 1 → 4 4 2 → 0 0 2 → 0 0 1 → 0 0

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

The last matrix in this row is in row echelon form. Now we proceed to the
reduced row echelon form.

1 1
1 1
1 1 1 0

0 0 → 0 0

0 0 0 0 0 0

1
1
1 0 4 4 2

0 0 is the reduced row echelon form of 1 1 1 . The reduced row

0 0 0 3 3 2
echelon for a matrix is unique.

3.2. Example

- - - -
1 3 0 1

Compute the reduced row echelon form of 1 3 1 1 :

3 9 2 3

- - - - - - -
1 3 0 1 1 3 0 1 1 3 0 1 1 3 0 1

1 3 1 1 → 0 0 1 0 → 0 0 1 0 → 0 0 1 0

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

1
- 1
1 3 0 1 3 0 1

0 0 1 0 → 0 0 0

0 0 0 0 0 0 0 0
4. Gaussian Elimination: dependent and independent variables

4.1. Example

x- z
- x- y z
2 = 0

-x- y z
2 2 +4 = 0

2 +2 = 0

Step-1: Forward elimination (aim → row echelon form)

- - - -
- - - -
1 0 2 1 0 2 1 0 2 1 0 2

- - - - -
2 2 4 → 0 2 0 → 0 2 0 → 0 1 0

1 2 2 1 2 2 0 2 0 0 0 0

Step-2: Identify the leading entries

xy z
1 -
1
0 2

0 0

0 0 0

• Each column is associated with one variable. There are as many

variables as there are columns.
• The variables corresponding to the leading entries are called
dependent variables.
• The remaining variables are called independent variables (free).

1 - x
1 y
0 2 0

z
0 0 0

0 0 0 0

• x y → dependent variables
• z → independent variable
,

Backward substitution:

z t t R
•
• y
= , ∈

• x t
= 0

= 2

S t t t R
= {(2 , 0, ) | ∈ } is the set of all solutions to the above system.

4.2. Example
Another example:

x- y - w
x- y z- w
= 0

- x y-z w
2 2 + 2 = 0

5 +5 +5 = 0
Step-1: Forward elimination

- - 1- -
- - 1
1 1 0 1 1 0 1

- -
2 2 1 2 0 0 0

5 5 1 5 0 0 0 0

Step-2: Backward substitution

x y z w
1- -
1
1 0 1

0 0 0

0 0 0 0

• Dependent variables: xz
• Independent variables: y w
,

• y t w t
,

• z
= 1, = 2

• x t t
= 0

• S t t t t t t R
= 1 + 2

= {( 1 + 2, 1, 0, 2) | 1, 2 ∈ }
5. Gaussian elimination: Augmented Matrix

5.1. Example

x- y - z
x- y - z w
3 3 6 = 3

- x y z- w -
2 + = 0

2 +2 +4 = 1

Step-1: Augmented matrix A b: |

- -
- -
3 3 6 0 | 3

- - -
1 1 2 1 | 0

2 2 4 1 | 1

Step-2: Forward elimination

- - - -
- - - -
3 3 6 0 | 3 1 1 2 1 | 0

- - - - - -
1 1 2 1 | 0 → 3 3 6 0 | 3

2 2 4 1 | 1 2 2 4 1 | 1

- - - -
- - -
1 1 2 1 | 0 1 1 2 1 | 0

- - - - - -
3 3 6 0 | 3 → 0 0 0 3 | 3

2 2 4 1 | 1 2 2 4 1 | 1

- - - -
- -
1 1 2 1 | 0 1 1 2 1 | 0

- - - - - -
0 0 0 3 | 3 0 0 0 1 | 1

2 2 4 1 | 1 2 2 4 1 | 1

- - - -
- -
1 1 2 1 | 0 1 1 2 1 | 0

- - - -
0 0 0 1 | 1 → 0 0 0 1 | 1

2 2 4 1 | 1 0 0 0 1 | 1

- - - -
- -
1 1 2 1 | 0 1 1 2 1 | 0

-
0 0 0 1 | 1 → 0 0 0 1 | 1

0 0 0 1 | 1 0 0 0 0 | 0

Step-3: Backward substitution

x y z w b x y z w b
1- - 1- -
1 - 1 -
1 2 1 | 0 1 2 0 | 1
→
0 0 0 | 1 0 0 0 | 1

0 0 0 0 | 0 0 0 0 0 | 0

• Dependent variables: xw
• Independent variables: y z
,

– y t z t
,

• x t t w -
= 2, = 1

• S t t t t - t t R
= 2 +2 1 + 1, = 1

= {(2 1 + 2 + 1, 2, 1, 1) | 1, 2 ∈ }
5.2. Example

One final example:

x y-z
- x- y z -
+ = 3

x y- z
2 + = 4

3 +3 3 = 8

- -
- - - -
1 1 1 | 3 1 1 1 | 3

- -
2 1 1 | 4 → 0 0 1 | 2

3 3 3 | 8 3 3 3 | 8

- -
- -
1 1 1 | 3 1 1 1 | 3

- -
0 0 1 | 2 → 0 0 1 | 2

3 3 3 | 8 0 0 0 | 1

- -
- -
1 1 1 | 3 1 1 1 | 3

- -
0 0 1 | 2 → 0 0 1 | 2

0 0 0 | 1 0 0 0 | 1

Backward substitution

1 -
1 -
1 1 | 3

1
0 0 | 2

0 0 0 |

x y z - , no solution
0 +0 +0 = 1

Rule: If you have leading entry in the last column of the augmented
matrix,then the system is not solvable.