/ 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.
[ 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.
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.
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.
Strategy:
Only use the row transformations described above and work from top-row to bottom-row.
1. In each row make 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 a row of zeros occurs, then delete this row
4. If a row of zeros occurs, except for the last number, then the system has no solutions.
/ 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.
We recall the strategy:
Only use the row transformations described above and work from top-row to bottom-row.
1. In each row make 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 a row of zeros occurs, then delete this row
4. If a row of zeros occurs, 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.
/ 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
/ 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.4The 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.
S = {2z - 5.2t + 12.6 ,2z -4.8t + 11.4 , z, t} with z, t in R
/ 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]Because of the last row, the system has no solutions.
Examples
3 x 2 matrix A =
[1 2] [0 0] [4 0]The rank is at most 2. If we delete the second row, we have the biggest regular square matrix. The rank of A is 2.
3 x 3 matrix A =
[4 5 7] [1 2 3] [2 4 6]The rank is at most 3, but A is not a regular matrix. So, we are looking for a regular 2x2 matrix. We delete row 3 and column 3. The remaining matrix is regular. The rank of A is 2.
3 x 3 matrix A =
[1 2 3] [1 2 3] [2 4 6]The rank is at most 3, but A is not a regular matrix. So, we are looking for a regular 2x2 matrix. But all 2x2 matrices are not regular. So, the rank of A is 1.
Application:
Take matrix A
[ a a-1 a-2 ] [3a-3 a+1 2a-4]Determine the rank for all values of a.
Solution:
The maximum rank is 2. We select a 2 x 2 matrix from A, for example
[ a a-1] [3a-3 a+1]The determinant of that matrix is -2a^{2} +7a -3. the zero's are 1/2 and 3. It follows that the rank of A is 2 if a is not in { 1/2 , 3}.
If we substitute 1/2 for a, we immediately see that the rank of A is 2.
If we substitute 3 for a, then we have for A
[3 2 1] [6 4 2]The rank of this matrix is 1.
Conclusion: If a is different from 3, the rank is 2. The rank is 1 if a = 3.
Choose in the matrix the element on the i-th row and the j-th column.
Delete this row en this column from the matrix.
Calculate the value D of the determinant of the remaining matrix.
The cofactor of the the element on the i-th row and the j-th column is (-1)^{i+j}.D
The elements of the deleted row and column do not affect the value of this cofactor!
Now we are ready to calculate the adjoint matrix of a square matrix A.
Replace each element of A with its own cofactor and transpose the result,
then you have calculated the adjoint matrix of A.
Examples
[ 1, 4 ] [ 5, 8 ] has the adjoint matrix [ 8, -4 ] [ -5, 1 ] --------------------- [ 1, 2, 4 ] [ 3, 2, 5 ] [ 1, 3, 4 ] has the adjoint matrix [ -7, 4, 2 ] [ -7, 0, 7 ] [ 7, -1, -4 ]
Proof:
We'll prove this property for 3x3 matrices but the method of the proof is universal.
So take P =
[a b c] [d e f] [g h i]Let A,B,C,D,E,F,G,H,I be the cofactors of a,b,c,d,e,f,g,h,i.
[d e f] [d e f] [g h i]Since the matrix has two equal rows,its determinant is 0. So det(Q) = 0.
We'll prove this property for 3x3 matrices but the method of the proof is universal.
We show that A. (adjoint of A) / det(A) = E or equivalently that
A.(adjoint of A) = det(A) . E
First we'll calculate
A.(adjoint of A) =
[a b c] [A D G] [d e f] . [B E H] = [g h i] [C F I] [aA+bB+cC aD+bE+cF aG+bH+cI] [dA+eB+fC dD+eE+fF dG+eH+fI] = [gA+hB+iC gD+hE+iF gG+hH+iI] Because of the cofactors property, [aA+bB+cC 0 0 ] [ 0 dD+eE+fF 0 ] = [ 0 0 gG+hH+iI] The diagonal elements of this matrix are det(A) [ det(A) 0 0 ] [ 0 det(A) 0 ] = [ 0 0 det(A)] [ 1 0 0] det(A). [ 0 1 0] = [ 0 0 1] det(A).IIn the same way, (adjoint of A).A =det(A).I
Remark : All regular matrices have an inverse matrix and now we can calculate this inverse matrix.
Example 1
[ 1, 4 ] [ 5, 8 ] determinant = -12 and has adjunct matrix [ 8, -4 ] [ -5, 1 ] The inverse matrix is : [ -2/3, 1/3 ] [ 5/12, -1/12 ]Example 2
[ 1, 2, 4 ] [ 3, 2, 5 ] [ 1, 3, 4 ] determinant = 7 and has adjunct matrix [ -7, 4, 2 ] [ -7, 0, 7 ] [ 7, -1, -4 ] The inverse matrix is [ -1, 4/7, 2/7 ] [ -1, 0, 1 ] [ 1, -1/7, -4/7 ] ]
There is a special method to solve such a system. This method is called Cramer's rule.
We'll prove the rule for a system of 3 equations in 3 unknowns, but the rule is universal.
Take,
/ ax + by + cz = d | a'x+ b'y + c'z = d' (1) \ a"x+ b"y + c"z = d" |a b c | with |N| = |a' b' c'| |a" b" c"| Then we have |xa b c | x.|N| = |xa' b' c'| |xa" b" c"| and using the properties of determinants |xa +by +cz b c | x.|N| = |xa'+b'y+c'z b' c'| |xa"+b"y+c"z b" c"| and appealing to (1) |d b c | x.|N| = |d' b' c'| |d" b" c"| Thus, |d b c | x = |d' b' c'| / |N| (2) |d" b" c"| Similarly, |a d c | y = |a' d' c'| / |N| (3) |a" d" c"| |a b d | z = |a' b' d'| / |N| (4) |a" b" d"|The formulas (2), (3), (4) constitute Cramer's rule. It can be proved that this solution is the only solution of (1).
Example:
Solve the system in x, y and z . This system has parameter p.
/ p x - y + z = 0 | 6 x + y - 2z = 2 \ px - 2y - z = 1 We find : |N| = -4p - 18 We assume that p is not -4.5. Men find : x.|N| = -5 y.|N| = -2p + 6 z.|N| = 3p + 6 So, x = 5/(4p+18) ; y = (p-3)/(2p+9) ; z = (3p+6)/(-4p-18)
Example
/ x + 2 y + 4z = 0
| 3x + 2y + 5z = 0
\ x + 3y + 4z = 0
This system has only the solution x = y = z = 0
Example:
/ x+2y+z+2u=1 | 4x+4y=-3 | 3x+6y=-4.5 \ 2x+4y+2z+4u=2 The matrix of coefficients is [1 2 1 2] [4 4 0 0] [3 6 0 0] [2 4 2 4] The rank of this matrix is 3. We choose a main matrix M from that matrix. [1 2 1] [4 4 0] [3 6 0]The equations corresponding with the rows of M are called the main equations, the other equations are the side equations.
In previous example we have:
The main equations are the first, the second and the third one.
The main unknowns are x, y and z.
The last equation is the only side equation and u is the side unknown.
The characteristic determinant is the determinant of the characteristic matrix.
So there are as much characteristic determinants as the number of side equations.
We continue with our example :
The characteristic determinant of the only side equation is
|1 2 1 1 | |4 4 0 -3 | |3 6 0 -4.5| |2 4 2 2 |With all these new concepts we can classify all the systems of linear equations.
Example: / 2x+3y+z=4 \ x+2y-z=3 Choose the main matrix [2 3] [1 2]z is the side unknown. With each choice of z, corresponds exactly one solution of the system.
/ 2x+y=1 | x+y=0 | 3x+2y=1 \ 4x+3y=1 I choose the main matrix [2 1] [1 1] The characteristic determinants are |2 1 1| |1 1 0| = 0 |3 2 1| and |2 1 1| |1 1 0| = 0 |4 3 1| The unique solution is the solution of the system / 2x+y=1 \ x+y=0 x=1, y=-1
Example 1
/ -4.5x - y + z = 0
| 6x + y - 2z = 2
\ -4.5 x - 2y - z = 1
The rang of the matrix of the system is 2.
We choose y and z as main unknowns and the third equation is a side equation.
The side unknown is x.
There is one characteristic matrix
[ -1 1 0 ]
[ 1 -2 2]
[-2 -1 1]
The value of de characteristic determinant is -5.
The system has no solutions.
Example 2
/ x + y - z + u = 2
| 2x - y + z + u = 3
| 3x + 2u = 5
\ 4x + y - z + 3u = 7
The rank of the matrix of coefficients is 2. We choose as main matrix M =
[ 1 1] [ 2 -1]The main unknowns are x and y and the main equations are the first one and the second one.
| 1 1 2 | | 2 -1 3 | = 0 | 3 0 5 | | 1 1 2 | | 2 -1 3 | = 0 | 4 1 7 |As the characteristic determinants are 0, the side equations may be omitted. We get a system of the second kind.
/ x + y = 2 + z - u
\ 2x - y = 3 - z - u
We can solve this remaining system as a system of the first kind.
There is exactly one solution for each value of z and u.
x = ( 5 - 2 u)/3
y = (1 + 3z - u)/3
What are the p-values such that the system has a solution different from (0,0,0) ?
/ p x - y + z = 0
| 6 x + y - 2z = 0
\ px - 2y - z = 0
The system is homogeneous. The condition is that the matrix formed by the coefficients is singular.
The determinant is -4p - 18. So, for p = -9/2 , there are solutions different from (0,0,0).
To find these solutions, we substitute -9/2 for p.
We omit a side equation. Then we have a system of the second kind with infinitely many solutions.
The three points are collinear <=> There is a line ux+vy+w=0 through A,B and C <=> There are values for u,v,w different from 0,0,0 such that u.a + v.a' + w = 0 u.b + v.b' + w = 0 u.c + v.c' + w = 0 <=> The homogeneous system a.u + a'.v + 1.w = 0 b.u + b'.v + 1.w = 0 c.u + c'.v + 1.w = 0 has a solution for u,v,w different from the obvious solution. <=> |a a' 1| |b b' 1| = 0 |c c' 1|
The points A(a,a'), B(b,b'), C(c,c') are collinear if and only if
|a a' 1| |b b' 1| = 0 |c c' 1| |
A third point P(x,y) is on the line AB <=> |x y 1| |a a' 1| = 0 |b b' 1| This is the equation of the line AB.
The equation of the line AB with A(a,a') and B(b,b') is
|x y 1| |a a' 1| = 0 |b b' 1| |
u x + v y + w = 0 u'x + v'y + w' = 0 u"x + v"y + w" = 0 The three lines are concurrent <=> The three lines have a common point P(x_{o},y_{o}) <=> There is an x_{o} and a y_{o} such that u x_{o} + v y_{o} + w = 0 u'x_{o} + v'y_{o} + w' = 0 u"x_{o} + v"y_{o} + w" = 0 <=> There is an x_{o} and a y_{o} such that u x_{o} + v y_{o} = -w u' x_{o} + v' y_{o} = -w' u" x_{o} + v" y_{o} = -w" <=> The system u x + v y = -w u' x + v' y = -w' u" x + v" y = -w" has a solution for x and y. The matrix of the coefficients of the system is [ u v ] [ u' v'] [ u" v"] Since the lines intersect each other, the rank is 2. We choose the first two equations as main equations The system has a solution for x and y <=> The characteristic determinant is zero <=> | u v w | | u' v' w'| = 0 | u" v" w"|
Three intersecting lines have equations : u x + v y + w = 0 u'x + v'y + w' = 0 u"x + v"y + w" = 0 The lines are concurrent if and only if | u v w | | u' v' w'| = 0 | u" v" w"| |
/mx + y + z = m+1
| x + my + z = 0
\ x + y + mz = 1
De determinant of the matrix formed by the coefficients is (m - 1)^{2} .(m+2)
First case: m is different from 1 and -2
With Cramer's Rule, we find for x, y and z the solutions :
m(m-1)(m+2) x = ------------------ = m/(m-1) (m - 1)^{2} (m+2) -(m-1)(m+2) y = ----------------- = 1/(1-m) (m - 1)^{2} (m+2) z = 0Second case: m = 1
Then, the system is:
/ x + y + z = 2
| x + y + z = 0
\ x + y + z = 1
We see immediately that the system has no solutions
Third case m = -2
We replace m by -2
/-2x + y + z = -1
| x - 2y + z = 0
\ x + y + -2z = 1
The rank of the matrix formed by the coefficients is 2.
We choose as the first and the third equation as main equations.
x and y are the main unknowns.
We calculate the characteristic determinant of the side equation.
| -2 1 -1 | | 1 1 1 | = 0 | 1 -2 0 |so, the side equation may be deleted and we bring the terms in z to the right side.
/ -2x + y = -1 -z \ x + y = 1 + 2zWith Cramer's Rule, we find
x = z + 2/3
y = z + 1/3
z is arbitrary. There are infinitely many solutions.
/(m-1)x + (2m+1)y + z = mThe matrix of the coefficients is
\ x + y + 2z = m+1
[ m-1 2m+1 1] [ 1 1 2]Choose the determinant
| m-1 1 | | 1 2 |The determinant = 2m-3
First case: m is different from 1.5
We choose the matrix
[ m-1 1 ] [ 1 2 ]as main matrix. The main unknowns are x and z. The side-unknown is y.
m-1 -4my -y x = --------------- 2m-3 m^{2} -m - 1 -3my + 2y z = ---------------------- 2m-3There are infinitely many solutions. y is arbitrary.
Second case: m = 1.5
/ 0.5 x + 4 y + z = 1.5 \ x + y + 2z = 2.5Choose y and z as main unknowns. We bring the terms with x to the right side. With Cramer's Rule, we find for each x just one solution.
/ 2x -my + z = 0 | x + y + 2z = 0 \ 3x - y + z = 0The system is homogeneous. It always has the solution (0,0,0).
First case: m is different from 2/5.
There is just one solution : (0,0,0).
Second case: m = 2/5
The rank of the matrix of the coefficients is now 2. We choose the main matrix as simple as possible.
[1 2] [-1 1]y and z are main unknowns. The first equation is de side equation. We delete this equation. We bring the terms in x to the right side. With Cramer's Rule, we find y = 5x/3 en z = -4x/3. We find for each x just one solution.
/ ax + y = 0 | 4x - y = 1 \ (a + 2) x + 3 y = 0This is a system with more equations than unknowns. The rank of the matrix of the coefficients. Its maximum is 2.
First case: a is different from -4.
Now the rank of the matrix of the coefficients is 2. We choose the first two equations as main equations. The characteristic determinant of the side equation is :
| a 1 0| | 4 -1 1| = -2 (a - 1) |a+2 3 0|If a = 1 then the characteristic determinant is 0. The side equations may be omitted. We have a Cramer system. We find x=1/5 and y = -1/5
If a is not 1, then the characteristic determinant is not 0. There are no solutions.
Second case: a = -4 We substitute -4 in the system. We immediately see that there are no solutions.
/ ax - y + az = 4 | -x + 3y + z = b \ 3x + y + 5z = 1The determinant of the matrix of the coefficients is 4(a-2).
Conclusion : There are infinitely many solutions for (a=2 and b=-7)
/ ax + by = 1 | ax + y = b \ x + by = aFirst we see that: If a = b= 1 the system is equivalent with the equation x + y = 1. There are infinitely many solutions. With each x corresponds exactly one y value. Suppose further that a and b are not both equal to 1.
The three 2 x 2 determinants that we can construct with the aid of the matrix of the coefficients
are equal to a-ab ; ab-1 and ab-b.
Case 1: a.b is not equal to 1.
The rank of the matrix of the coefficients is two. We consider the second and third equation as main equations.
The characteristic determinant of the side equation is :
| a 1 b| | 1 b a| = (b + a + 1) (1 - a) (b - 1) | a b 1|This determinant is 0 if and only if ( a = 1 of b = 1 of b = -a -1).
Case 2: a.b = 1 ( a not 1 )
The three 2 x 2 determinants that we can construct with the aid of the matrix of the coefficients are a-1 ; 0 ; 1-b.
As a is not equal to 1, b is different from 1. Then the rank of the matrix of the coefficients is two.
We consider the first and second equation as main equations. The characteristic determinant of the side equation is :
| a b 1| | a 1 b| = (b + a + 1) (1 - a) (b - 1) | 1 b a|The system has a solution if and only if b = - a -1. But :
b = - a -1 en a.b = 1 => a(- a -1) = 1 => a^{2} + a + 1 = 0There is no real value of a such that a^{2} + a + 1 = 0. So this second case can not occur.
Summary:
If (a = b= 1) there are an infinite number of solutions.
If (a.b not 1) the system has a solution on condition that ( a = 1 or b = 1 or b = -a -1).