A linear equation is an equation of the form
a1x1+a2x2+...+anxn=b (1)
where x1,...,xn are unknowns, a1,...,an,b
are coefficients.
Example:
3x-4y+5z=6 (2)
This equation has three unknowns and four coefficients (3, -4, 5, 6).
A solution of a linear equation
(1) is a sequence of numbers x1,...,xn which
make (1) a true equality.
Example:
x=2, y=0, z=0
is a solution of equation (2).
A linear equation can have infinitely many solutions, exactly one solution
or no solutions at all.
Equation (2) has infinitely many solutions. To find them all we can
set arbitrary values of x and y and then solve (2) for z.
We get:
x = s
y = t
z = (6-3s+4t)/5
These formulas give all solutions of our equation meaning that for every
choice of values of t and s we get a solution and every solution
is obtained this way. Thus this is a (the) general solution
of our equation.
There may be many formulas giving all solutions of a given equation.
For example Maple gives another formula:
> with(linalg);
This command starts the linear algebra package.
> A:=matrix(1,3,[3,-4,5]):b:=vector([6]):linsolve(A, b);
This command asks Maple to solve the system of equations.
The solution has two parameters t1 and t2;
x=4/3t1-5/3t2+2, y=t1, z=t2.
In order to get this solution "by hand" one can give y
and z arbitrary values (t1 and t2)
and solve for x.
A system of linear equations is any
sequence of linear equations. A solution
of a system of linear equations is any common solution of these
equations. A system is called consistent
if it has a solution. A general solution
of a system of linear equations is a formula which gives all solutions
for different values of parameters.
Examples. 1. Consider the system:
x + y = 7
2x + 4y = 18
This system has just one solution: x=5,
y=2. This is a general solution of the system.
2. Consider the system:
x + y + z = 7
2x + 4y + z = 18.
This system has infinitely many solutions given by this formula:
x = 5 - 3s/2
y = 2 + s/2
z = s
This is a general solution of our system.
In order to find a general solution of a system
of equations, one needs to simplify it as much as possible. The simplest
system of linear equations is
x = a
y = b
.....
where every equation has only one unknown and all these unknowns are
different. It is not possible to reduce every system of linear equations
to this form, but we can get very close. There
are three operations that one can apply to any system of linear equations:
The system obtained after each of these operations is equivalent
to the original system, meaning that they have the same solutions.
For example consider the system
x + y = 7
2x + 4y = 18
We can first replace the second equation by the second equation plus
the first equation multiplied by -2. We get
x + y = 7
2y = 4
Now we can use the third operation and multiply the second equation
by 1/2:
x + y = 7
y = 2
Finally we can replace the first equation by the sum of the first equation
and the second equation multiplied by -1:
x = 5
y = 2
Since this system is equivalent to the original system, we get that
x=5, y=2 is the general solution of the original system.
Consider an (x,y)-plane and the set of points satisfying ax+by=c.
This set of points is either a line (if a or b is not 0)
or the whole plane (if a=b=c=0), or empty (if a=b=0
but c is not 0).
The set of solutions of the system
ax + by = c
a'x + b'y = c'
is the intersection of the sets of solutions of the individual equations.
For example if these equations define lines on the plane, the intersection
may be a point -- if the lines are not parallel, a line -- if the lines
coincide, or empty -- if the lines are parallel.
A system of equations in 3 or more variables has similar geometric meaning.
Consider the following problem:
x + y + 2z = a
x + z = b (1)
2x + y + 3z = c,
show that it has a solution only if a+b=c.
In order to prove that, replace the first equation by the sum of the
first two equations:
2x + y + 3z = a + b
x + z = b
2x + y + 3z = c
This system is equivalent to the previous one, so it has a solution if and only if the initial system has a solution. But comparing the first and the third equations of this system we notice that it has a solution only if a+b=c. The problem is solved.
Now suppose that we have that a+b=c and we want to find the general
solution of this system.
Then we need to simplify the system by using three operations
(adding, swapping, multiplying). It is more convenient to work not
with the system but with its augmented matrix,
the array (table, matrix) consisting of the coefficients of the left sides
of the equations and the right sides. For example the system
(1) from the problem that we just solved has the following augmented matrix:
| [ 1 | 1 | 2 | a ] |
| [ 1 | 0 | 1 | b ] |
| [ 2 | 1 | 3 | c ] |
The number of equations in a system of linear equations is equal to
the number of rows in the augmented matrix, the number of unknowns is equal
to the number of columns minus 1, the last column consists of the right
sides of the equations.
When we execute the operations on
the systems of equations, the augmented matrix changes. If we add equation
i to equation j, then row i will be added to row j,
if we swap equations, the corresponding rows get swapped, if we multiply
an equation by a (non-zero) number, the corresponding row is multiplied
by this number.
Thus, in order to simplify a system of equations it is enough to simplify
its augmented matrix by using the following row
operations:
For example let us simplify the augmented matrix
of the system (1) from the problem that we just solved.
First we replace the first row by the sum of the first and the second
rows:
| [ 2 | 1 | 3 | a+b ] |
| [ 1 | 0 | 1 | b ] |
| [ 2 | 1 | 3 | c ] |
Then we subtract the first row from the third row (remember that a+b=c):
| [ 2 | 1 | 3 | a+b ] |
| [ 1 | 0 | 1 | b ] |
| [ 0 | 0 | 0 | 0 ] |
Then we subtract the second row multiplied by 2 from the first row. :
| [ 0 | 1 | 1 | a-b ] |
| [ 1 | 0 | 1 | b ] |
| [ 0 | 0 | 0 | 0 ] |
Then we swap the first two rows and obtain the following matrix
| [ 1 | 0 | 1 | b ] |
| [ 0 | 1 | 1 | a-b ] |
| [ 0 | 0 | 0 | 0 ] |
The last matrix has several important features:
A matrix which satisfies the first four conditions
is called a matrix in the row echelon form or a row
echelon matrix.
A matrix which satisfies all five conditions is
called a matrix in the reduced row echelon form or a reduced
row echelon matrix.
It is very easy to find the general solution
of a system of linear equations whose augmented matrix has the reduced
row echelon form.
Consider the system of equations corresponding to the last matrix
that we got:
x + z = b
y + z = a - b
The unknowns corresponding to the leading 1's
in the row echelon augmented matrix are called leading unknowns.
In our case the leading 1's are in the first and the second positions,
so the leading unknowns are x and y. Other
unknowns are called free.
In our case we have only one free unknown, z. If we move it to the right and denote it by t, we get the following formulas:
x = b - t
y = a - b - t
z = t
This system gives us the general solution
of the original system with parameter t. Indeed, giving t arbitrary values,
we can compute x, y and z and obtain all solutions of the
original system of equations.
Similarly, we can get a general solution of every system of equations
whose matrix is in the reduced row echelon form:
One just has to move all free variables to the right side of the equations
and consider them as parameters.
Example Consider the system of equations:
x1 + 2x2 + x4 = 6
x3 + 6x4 = 7
x5=1
Its augmented matrix is
| [ 1 | 2 | 0 | 1 | 0 | 6 ] |
| [ 0 | 0 | 1 | 6 | 0 | 7 ] |
| [ 0 | 0 | 0 | 0 | 1 | 1 ] |
The matrix has the reduced row echelon form. The leading unknowns are x1, x3 and x5; the free unknowns are x2 and x4. So the general solution is:
x1= 6-2t-s
x2= s
x3= 7-6t
x4= t
x5= 1
If the augmented matrix does not have the reduced
row echelon form but has the (ordinary) row echelon
form then the general solution also can be easily found.
The method of finding the solution is called the back-substitution.
First we solve each of the equations for the leading unknowns The last
non-zero equation gives us the expression for the last leading unknown
in terms of the free unknowns. Then we substitute this leading unknown
in all other equations by this expression. After that we are able to find
an expression for the next to the last leading unknown, replace this unknown
everywhere by this expression, etc. until we get expressions for all leading
unknowns. The expressions for leading unknowns that we find in this process
form the general solution of our system of equations.
Example. Consider the following system of equations.
x1-3x2+ x3-x4 = 2
x2+2x3-x4 = 3
x3+x4 = 1
Its augmented matrix
| [ 1 | -3 | 1 | -1 | 2 ] |
| [ 0 | 1 | 2 | -1 | 3 ] |
| [ 0 | 0 | 1 | 1 | 1 ] |
is in the row echelon form.
The leading unknowns are x1, x2, x3; the free unknown is x4.
Solving each equation for the leading unknown we get:
x1=2+3x2-x3+x4
x2=3-2x3+x4
x3=1-x4
The last equation gives us an expression for x3: x3=1-x4.
Substituting this into the first and the second equations gives:
x1=2+3x2-1+x4+x4=1+3x2+2x4
x2=3-2(1-x4)+x4=1+3x4
x3=1-x4
Now substituting x2=1+3x4 into the first equation,
we get
x1=1+3(1+3x4)+2x4=4+11 x4
x2=1+3x4
x3=1-x4
Now we can write the general solution:
x1=4+11 s
x2=1+ 3 s
x3=1- s
x4= s
Let us check if we made any arithmetic mistakes. Take x4=1
and compute x1=15, x2=4, x3=0,
x4=1. Substitute it into the original system of equations:
15 - 3 * 4 + 0 - 1 = 2
4 + 2 * 0 - 1 = 3
0 + 1 = 1
OK, it seems that our solution is correct.
The Gauss-Jordan elimination procedure
There exists a standard procedure to obtain a reduced row echelon matrix
from a given matrix by using the row operations.
This procedure consists of the following steps.
Theorem. A system of linear equations either has no
solutions or has exactly one solution or has infinitely many solutions.
A system of linear equations has infinitely many solutions if and only
if its reduced row echelon form has free unknowns and the last column of
the reduced row echelon form has no leading 1's. It has exactly one solution
if and only if the reduced row echelon form has no free unknowns and the
last column of the reduced row echelon form has no leading 1. It has no
solutions if and only if the last column of the reduced row echelon form
has a leading 1.
A system of linear equation is called homogeneous if the right sides are equal to 0.
Example:
2x + 3y - 4z = 0
x - y + z = 0
x - y = 0
A homogeneous system of equations always has a solution (0,0,...,0). Therefore the theorem about solutions of systems of linear equations implies the first part of the following result.
Theorem. Every homogeneous system has either exactly one solution or infinitely many solutions. If a homogeneous system has more unknowns than equations, then it has infinitely many solutions.