..Equivalent
systems of linear equations
..The
Gauss method
Equivalent systems of
linear equations
Examples
/ x+2y+3z=5 | x-y+6z=1 | 3x-2y=4 \ y+4z=8 / x+y+3z-4t=12 \ 3x+y-2z-t=0 / 2x+3y+4z=5 | x-y+2z=6 \ 3x-5y-z=0Each of these systems can be expressed by the help of matrices.
[ 1 2 3] [x] [5]
[ 1 -1 6] . [y] = [1]
[ 3 -2 0] [z] [4]
[ 0 1 4] [8]
[x]
[ 1 1 3 -4] [y] [12]
[ 3 1 -2 -1] . [z] = [ 0]
[t]
[ 2 3 4] [x] [5]
[ 1 -1 2] . [y] = [6]
[ 3 -5 -1] [z] [0]
The first matrix of each representation of a linear system contains the
coefficients appearing in the system. This matrix is called the coefficient
matrix.The essential information of such system is this coefficient matrix A together with the column matrix B of the known terms.
We can denote such system shortly as AX=B. Then X is the column matrix of the unknowns. Therefore we can gather all essential data of the system in one matrix, by adding the column matrix of the known terms to the coefficient matrix.
For the first system we have then
[ 1 2 3 5] [ 1 -1 6 1] [ 3 -2 0 4] [ 0 1 4 8]This matrix is called the enlarged matrix of the system.
Conversely, when we have the enlarged matrix of a system, we know the system and we can start calculating the solutions.
equivalent systems
Two systems are equivalent if and only if they have the same set of solutions.Now we'll define some basic actions by witch a system is transformed in an equivalent system.
Action 1 :
Multiply one of the equations with a real number different from 0.
This is
equivalent with :
Multiply one of the rows, of the enlarged matrix of the
system, with a real number different from 0.
Action 2 :
Multiply one of the equations with a real number, and add the result to
another equation, leaving the original equation unchanged.
This is
equivalent with :
Multiply one of the rows, of the enlarged matrix of the
system, with a real number, and add the result to another row, leaving the
original row unchanged.
Action 3 :
Interchange two equations .
This is equivalent with :
Interchange two
rows of the enlarged matrix of the system.
Action 4 :
Delete an equation that is equivalent with 0 = 0
This is equivalent with
:
Delete a row, of the enlarged matrix of the system, that contains only
zero's.
Action 5 :
If an equation of a system is equivalent with 0=k, with k not zero, then the
system has no solutions.
This is equivalent with :
If a row, of the
enlarged matrix of the system, is composed of zero's, except for the last
number, then the system has no solutions.
Row-transformations
Each of the actions transforming a system to an equivalent system, is equivalent to a transformation of the rows of the enlarged matrix of the system. These are the so called 'row transformations'.
Now, it can be shown that, by a appropriate consequence of only these 5 actions, we can solve any system of linear equations. The method, to do this in a efficient way, is called the method of Gauss.
The Gauss method
We'll illustrate this method by means of 4 examples.Example 1
Take the system/ 2x-3y+2z=21 | x+4y-z=1 \ -x+2y+z=17or equivalently
[2 -3 2 21] [1 4 -1 1] [-1 2 1 17]First I'll show the row transformations, then I'll state the method in words.
R1 <-> R2
[1 4 -1 1]
[2 -3 2 21]
[-1 2 1 17]
R2 + 2.R3
[1 4 -1 1]
[0 1 4 55]
[-1 2 1 17]
R3 + R1
[1 4 -1 1]
[0 1 4 55]
[0 6 0 18]
(1/6).R3
[1 4 -1 1]
[0 1 4 55]
[0 1 0 3]
R3-R2
[1 4 -1 1]
[0 1 4 55]
[0 0 -4 -52]
(-1/4).R3
[1 4 -1 1]
[0 1 4 55]
[0 0 1 13]
Now we shall return to the system. / x+4y-z=1 | y+4z=55 \ z=13Working from z to x, we find easily z=13 ; y=3 ; x=2.
Now we state the method. Only use the row transformations described above and
work from top-row to bottom-row.
1. Make in each row, the first non-zero
element (called the main element) equal to 1
2. Transform, beneath this main
element, all the elements to 0
3. If there comes a row of all zero's,delete
this row
4. If there comes a row composed of zero's, except for the last
number, then the system has no solutions.
Remark: All these matrices are called row-equivalent.
The resulting matrix
is called an 'echelon' matrix.
It is also possible to transform, the matrix
such that each main element is the only non zero element on its column.
In
that case the resulting matrix is called row-canonical.
Example 2
Take the system/ 3x-4y+5z-4t=12 | x-y +z -2t = 0 | 2x+y+2z+3t=52 | 2x-2y+2z-4t=0 \ 2x-3y+2z-t=4or equivalently
[3 -4 5 -4 12]
[1 -1 1 -2 0]
[2 1 2 3 52]
[2 -2 2 -4 0]
[2 -3 2 -1 4]
R1-R4
[1 -2 3 0 12]
[1 -1 1 -2 0]
[2 1 2 3 52]
[2 -2 2 -4 0]
[2 -3 2 -1 4]
R2-R1;R3-2R1;R4-2R1;R5-2R1
[1 -2 3 0 12]
[0 1 -2 -2 -12]
[0 5 -4 3 28]
[0 2 -4 -4 -24]
[0 1 -4 -1 -20]
R3-5R2;R4-2R2;R5-R2;
[1 -2 3 0 12]
[0 1 -2 -2 -12]
[0 0 6 13 88]
[0 0 0 0 0]
[0 0 -2 1 -8]
delete R4;R3<->R4;
[1 -2 3 0 12]
[0 1 -2 -2 -12]
[0 0 -2 1 -8]
[0 0 6 13 88]
R4+3R3;(1/16)R4;R3/(-2);
[1 -2 3 0 12]
[0 1 -2 -2 -12]
[0 0 1 -1/2 4]
[0 0 0 1 4]
This is again an echelon matrix. Thus return to the system and calculate
the unknowns from bottom to top. / x-2y+3z =12 | y -2z -2t =-12 | z-0.5t=4 \ t=4 x=10 ; y=8 ; z=6 ; t=4
Example 3
Take the system
/ x+y-4z+10t=24
\ 3x-2y-2z+6t=15
[1 1 -4 10 24]
[3 -2 -2 6 15]
R2-3R1
[1 1 -4 10 24]
[0 -5 10 -24 -57]
r2/(-5)
[1 1 -4 10 24 ]
[0 1 -2 4.8 11.4]
Back to the system
/ x + y -4z +10t =24
\ y -2z +4.8t=11.4
The fundamental difference between proceeding examples is that, in this
case, it is impossible to calculate the unknowns. Therefore, we write the system
as follows. / x + y = 4z -10t + 24 \ y = 2z -4.8t+ 11.4 <=> / x = 2z - 5.2t + 12.6 \ y = 2z -4.8t+ 11.4For each chosen value of z and of t, we can calculate one solution of the system.
The system has an infinitely number of solutions.
The values of z and t are arbitrary.
The set S of all solutions can be written as follows.
S = {2z - 5.2t + 12.6 ,2z -4.8t + 11.4 , z, t} with z, t in R
Example 4
Take the system
/ x-3y=21
| 4x+2y=14
\ 3x+3y=7
[1 -3 21]
[4 2 14]
[3 3 7]
(1/2).R2 ; R3-3.R1
[1 -3 21]
[2 1 7]
[0 12 -56]
R2-2.R1
[1 -3 21]
[0 7 -35]
[0 12 -56]
(1/7)R2 ; (1/4)R3
[1 -3 21]
[0 1 -5]
[0 3 -14]
R3 -3.R2
[1 -3 21]
[0 1 -5]
[0 0 1]
Information Provided by Johan.Claeys@ping.be