LeLing2: Echelon form and solutions.
C ¯ ontents:
• Row elimination and row-equivalent matrices.
• Echelon form and solved systems.
• Gauß-Jordan elimination and echelon form.
• The general solution.
• The theorem of Steinitz.
R ¯ ecommended exercises: GeoLing 1,2.
1 Row elimination and row-equivalent matrices.
Two matrices A, B are said row-equivalent when either is obtained from the other by successive EROs.
Theorem 1.1 Two homogeneous linear systems are equivalent if and only if (iff ) the associated matrices are row-equivalent.
Therefore, to decide whether two systems are equivalent we should check if their matrices are equivalent under row operations. For this we need the so-called echelon form.
1.1 Echelon form and solved systems.
The basic idea to keep in mind is that a matrix is in echelon form if it represents a system which is essentially already solved. In other words we needn’t proceed further because the solution is self-evident.
Definition 1.2 A matrix A is in echelon form (or is an echelon matrix) when:
(i) The zero rows (if present) are grouped together below the nonzero ones.
(ii) In each nonzero row the first element different from zero is 1, which is also the only nonzero element in its own column (i.e. above and below the 1 only 0s appear).
The number 1 and the column containing it are called special.
1.2 Gauß-Jordan elimination and echelon form.
Geometria Lingotto.(iii) The special element of a row lies at the left of any special element below it.
The matrices 1 0 0 1
,
1 0 0
17110 1 0 −
24110 0 1
114
,
1 0 −2 −4 0 1
524
0 0 0 0
0 0 0 0
are echelon.
On the other hand
1 0 0 0 0 1
is not an echelon matrix for (i) fails.
The matrix
1 0 0
17110 1 1 −
24110 0 1
114
is not echelon because (ii) does not hold.
Also the matrix
1 0 0
17110 0 1
1140 1 0 −
2411
is not echelon, in fact (iii) is not satisfied.
Here is an important example of an echelon matrix:
Example 1.3 The matrix
0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0
is echelon.
1.2 Gauß-Jordan elimination and echelon form.
The Gauß-Jordan elimination method is an algorithm that takes an arbitrary matrix A and uses EROs to produce and echelon matrix E equivalent to A.
In order to remember the procedure easily, we divide it into two steps, the Gauß step and the Jordan step:
Gauß step: it consists essentially in obtaining zeroes below the elements equal to 1. Starting from the first column of A we identify (moving from left to right) the first nonzero column.
1We find in the first nonzero column the first (from the top) nonzero
1
Usually it is the first column to be already nonzero, i.e. containing a nonzero element a
i 16= 0 ; if
not, the unknown x
1is not explicitly involved in the system to be solved.
element a
i0j06= 0. Then we use
0 0 · · · 0 ∗ ∗ · · · ∗ 0 0 · · · 0 ∗ ∗ · · · ∗ .. . .. . . .. .. . .. . .. . .. . .. . 0 0 · · · 0 ∗ ∗ · · · ∗ 0 0 · · · a
i0j0∗ ∗ · · · ∗ 0 0 · · · ∗ ∗ ∗ · · · ∗ .. . .. . .. . .. . .. . .. . .. . .. . 0 0 · · · ∗ ∗ ∗ · · · ∗
Ri0 ai0j0
=⇒
0 0 · · · 0 ∗ ∗ · · · ∗ 0 0 · · · 0 ∗ ∗ · · · ∗ .. . .. . . .. ... .. . .. . .. . .. . 0 0 · · · 0 ∗ ∗ · · · ∗ 0 0 · · · 1
a∗i0j0
∗
ai0j0
· · ·
a∗i0j0
0 0 · · · ∗ ∗ ∗ · · · ∗ .. . .. . .. . .. . .. . .. . .. . .. . 0 0 · · · ∗ ∗ ∗ · · · ∗
From the 1 on row i
0we obtain 0s below it using the ERO R
i+ cR
i0. This gives a matrix
0 0 · · · 0 ∗ ∗ · · · ∗ 0 0 · · · 0 ∗ ∗ · · · ∗ .. . .. . . .. ... .. . .. . .. . .. . 0 0 · · · 0 ∗ ∗ · · · ∗ 0 0 · · · 1
a∗i0j0
∗
ai0j0
· · ·
a∗i0j0
0 0 · · · 0 ∗ ∗ · · · ∗ .. . .. . .. . .. . .. . .. . .. . .. . 0 0 · · · 0 ∗ ∗ · · · ∗
.
Now we swapp the i
0row with the first row by using the ERO R
i0⇔1to get:
0 0 · · · 1
a∗i0j0
∗
ai0j0
· · ·
a∗i0j0
0 0 · · · 0 b
11b
12· · · ∗ .. . .. . . .. ... .. . .. . .. . .. . 0 0 · · · 0 ∗ ∗ · · · ∗ 0 0 · · · 0 ∗ ∗ · · · ∗ 0 0 · · · 0 ∗ ∗ · · · ∗ .. . .. . .. . .. . .. . .. . .. . .. . 0 0 · · · 0 ∗ ∗ · · · ∗
.
Repeating the procedure from the start on the (sub-)matrix:
1.2 Gauß-Jordan elimination and echelon form.
Geometria Lingotto.
b
11b
12· · · ∗ .. . .. . .. . .. .
∗ ∗ · · · ∗ .. . .. . .. . .. .
∗ ∗ · · · ∗
will lead eventually to a matrix where:
(i) The zero rows (if present) are all written below the nonzero ones. If not, Gauß’s method could be used from the position of the last column.
(ii) In each nonzero row the first element different from zero is 1; below it only 0s are present.
(iii) The first 1 of a row lies at the left of the 1’s below it.
This ends the Gauß step and is where Jordan begins:
Jordan step: This works like a backwards gear: starting from the 1 in the last nonzero row we obtain zeroes above it, this time, using the ERO R
i+ cR
j:
0 0 · · · ∗ ∗ ∗ · · · ∗ 0 0 · · · ∗ ∗ ∗ · · · ∗ .. . .. . . .. ... ... ... ... ...
0 0 · · · ∗ ∗ ∗ · · · ∗ 0 0 · · · ∗ ∗ ∗ · · · ∗ 0 0 · · · 1 ∗ ∗ · · · ∗ 0 0 · · · 0 0 1 · · · 0 .. . .. . .. . .. . .. . .. . .. . .. . 0 0 · · · 0 0 0 · · · 0
=⇒
0 0 · · · 0 ∗ 0 · · · ∗ 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
The last column is now done with, and the 1 has now become the only nonzero element in the whole column, precisely as required by condition (iii) in the definition of echelon matrix. Once the engine is started, we repeat over and over until we get to the 1 of the fist column, the one in position i
0, j
0.
This concludes the Jordan step and yields an echelon matrix.
1.3 The general solution.
When the matrix is echelon the system is practically already solved. In fact, the un- knowns corresponding to the special columns (those containing just a 1) are variables that depend upon the other unknonws, in turn called independent variables, or param- eters. Hence x
1, x
2, · · · , x
ncan be divided into two groups, one of which is written in terms of the other. For example:
Example 1.4 Let S be
S =
2x
1− 6x
2+ 4x
4= 0 x
2+ x
3= 0 3x
1+ 7x
2= 0 3x
1+ 8x
2+ x
3= 0
Its matrix reads:
2 −6 0 4
0 1 1 0
3 7 0 0
3 8 1 0
The Gauß-Jordan method produces the echelon matrix:
1 0 0
780 1 0
−380 0 1
380 0 0 0
,
so the system S is equivalent to:
x
1+
78x
4= 0 x
2+
−38x
4= 0 x
3+
38x
4= 0 It is then clear that x
1, x
2, x
3depend on x
4.
The solutions of S read:
x
4−78x
43 8x
4−38x
4
Note all solutions are multiples of the single column
−7 83
−38 8
1
Geometria Lingotto.
S =
x
1+ 4x
2− 2x
4= 0 2x
1+ 8x
2− 2x
3+ x
4= 0 with matrix: 1 4 0 −2
2 8 −2 1
Gauß-Jordan yields the echelon matrix: 1 4 0 −2 0 0 1
−52, so that S is equivalent to: x
1+ 4x
2− 2x
4= 0
x
3+
−52x
4= 0 Now x
1, x
3are functions of x
2, x
4.
The system’s solutions are :
−4x
2+ 2x
4x
25 2
x
4x
4
The solutions are linear combinations of two columns
−4x
2+ 2x
4x
25 2
x
4x
4
= x
2
−4 1 0 0
+ x
4
2 0
5 2
1
2 The theorem of Steinitz.
Recall that nontrivial solution of a system means nonzero. From the elimination of Gauß-Jordan follows this result of Steinitz
2.
Theorem 2.1 A homogeneous system of linear equations with more unknowns than equations admits always a non-trivial solution.
2
