The algebraic method can be summarized as follows: Given a system of linear equations, use a series of elementary row operations to carry the augmented matrix to a nice matrix (meaning that the corresponding equations are easy to solve).
The following definitions identify the nice matrices
that arise in this process.
Definition
A matrix is said to be in row-echelon form (and will
be called a row-echelon matrix) if it satisfies the following conditions:
1)
All ZERO ROWS (consisting entirely of zeros) are at the bottom,
2)
The first nonzero entry from the left in each nonzero row is a 1.
called the leading 1 for that row.
3)
Each leading 1 is to the right of all leading 1’s in the rows
above it
|
The row-Echelon matrices have a so called staircase
form, as indicated by the following example.
$$\left[ \begin{matrix}
\underline{1} & 2 & 3 \\
0 & \underline{1} & 2 \\
0 & 0 & \underline{1} \\
\end{matrix} \right]$$
The leading 1’s proceed down and to the right through the matrix. Entries above and to the right of the leading 1’s are arbitrary, but all entries below and to the left of them are zero.
Definition
A row-echelon matrix is said to be in reduced
row-echelon form (and will be called a reduced row-echelon matrix) if it also
satisfies the following condition:
Each leading 1 is the only nonzero entry in its
column
|
Hence a matrix in row-echelon form is in reduced form
if, in addition, the entries directly above each leading 1 are zero. Note that
a matrix in row-echelon form can with a few more row operations, be carried to
reduced form.
Example 1
The following matrices are in row-echelon form (for
any choice of numbers in * position).
$$\left[ \begin{matrix}
1 & * & * \\
0 & 0 & 1 \\
\end{matrix} \right],\left[ \begin{matrix}
1 & * & * \\
0 & 1 & * \\
0 & 0 & 1 \\
\end{matrix} \right],\left[ \begin{matrix}
1 & * & * & * \\
0 & 1 & * & * \\
0 & 0 & 0 & 1 \\
\end{matrix} \right]$$
The following, on the other hand, are in reduced row-echelon form.
$$\left[ \begin{matrix}
1 & * & 0 \\
0 & 0 & 1 \\
\end{matrix} \right],\left[ \begin{matrix}
0 & 1 & 0 & * \\
0 & 0 & 1 & * \\
0 & 0 & 0 & 0 \\
\end{matrix} \right],\left[ \begin{matrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
\end{matrix} \right]$$
Clearly the choice of the positions for the lading 1’s determines the (reduced) row-echelon form (apart from the numbers in *-position).
Theorem 1 - Every matrix can be brought to (reduced)
row-echelon form by a series of elementary row operations.
|
Theorem 1 reduces the problem of finding solutions of
systems of linear equations to the case in which the augmented matrix is in
(reduced) row-echelon form. This case is easy as the next example shows.
Example 2
In each case assume that the
augmented matrix of a system of linear equations has been carried to the given
reduced row-echelon matrix by row operations. Then solve the system.
A )
$$\left[ \left. \begin{matrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
\end{matrix} \right|\begin{matrix}
-1 \\
0 \\
2 \\
\end{matrix} \right]$$
B ) $$\left[ \left. \begin{matrix} 1 & 3 & 0 & 1 & -3 \\ 0 & 0 & 1 & 2 & 5 \\ 0 & 0 & 0 & 0 & 0 \\ \end{matrix} \right|\begin{matrix} 0 \\ 0 \\ 1 \\ \end{matrix} \right]$$
C )$$\left[ \left. \begin{matrix} 1 & 5 & 0 & 0 & -2 \\ 0 & 0 & 1 & 0 & 4 \\ 0 & 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 & 0 \\ \end{matrix} \right|\begin{matrix} 3 \\ -5 \\ 6 \\ 0 \\ \end{matrix} \right]$$
Solution: In case A) the corresponding system of equations:
and the solution is apparent.
In case B) the last equation in
the corresponding system is:
There are certainly no values of x1,x2,x3,x4 and x5 that satisfy this equation, so the system has no solution in this case.
In case of C) the corresponding
system of equation is :
Use these equations to solve for the variables x1,x3, and x4 (corresponding to the leading 1’s) in terms of the other variables.
Now x2, and x5 can be assigned arbitrary values, say x2=s and x5=t, where s and t are parameter. This gives the solution
in parametric form.
In general, when the augmented
matrix of a system of linear equations has been carried to row-echelon form,
variables corresponding to columns containing a leading 1 are called leading
variables. The non-leading variables end up as parameters in the final
solution, and the lading variables are given in terms of these parameters.
There remains the task of giving a
systematic procedure by which the augmented matrix can be carried by row
operations to reduced row echelon form. Situations are described in the
following examples.
Example 3
Solve the following system of
equations.
$$\begin{align}
& x+2y-z=2 \\
& 2x+5y+2z=-1 \\
& 7x+17y+5z=-1 \\
\end{align}$$
Solution: The previous system can
be written in augmented matrix form:
Already has the
first leading 1 in place. Subtract 2 times row 1 from row 2, and subtract 7
times row 1 from row 3, to obtain
Now subtract 2
times row 2 from row 1, and subtract 3 times row 2 from row 3 to get reduced
row-echelon form.
The
corresponding system of equations is
If z=t where t
is an arbitrary parameter, we obtain the solution
$$\begin{align}
& x=9t+12 \\
& y=-4t-5 \\
& z=t \\
\end{align}$$
in parametric
form.
The row of 0’s
in the row-echelon form in previous example means that one of the equatios in
the original system is redundant in the sense that it provides no new
information about the solutions to the system. In fact, the third equation is
just the sum of the first equation plus three times the second, so any solution
to the first two equations is automatically a solution to the third. It is instructive
to see how one can discover the fact. We do this by keeping track of the row
operations performed in the solution to Example 3. Let R1, R2,R3 denote the
three rows of the original augmented matrix. Then the first manipulation in the
solution can be described as follows:
Now observe
that, in this last matrix, the last row is three times the second row. Hence
This can be
manipulated algebraically to give:
In other words,
the original third row, R3 equals the first row plus three times the second
row, as asserted. Note that we have been manipulation the symbols R1, R2 and R3
as though they were numbers or variables. This is a typical matrix calculation.
Example 4
Solve the
following system of equations
Solution: We
manipulate the augmented matrix keeping track of the manipulations for
reference. As before, we use R1,R2,R3 to denote the three rows. The augmented
matrix is:
$$\left[ \left. \begin{matrix}
1 & 0 & 10 \\
3 & 1 & -4 \\
4 & 1 & 6 \\
\end{matrix} \right|\begin{matrix}
5 \\
-1 \\
1 \\
\end{matrix} \right]\begin{matrix}
{{R}_{1}} \\
{{R}_{2}} \\
{{R}_{3}} \\
\end{matrix}$$
The indicated
row operations give:
But this means
that the following system of equations
is equivalent to
the original system. In other words, the two have the same solution. This last
system clearly has no solution. Hence the original system has no solutions.
Because we have
kept track of the operations performed in previous example it is possible to
give a clear explanation of why there is no solution. The offending equation 0=-3
corresponds to the row [0 0 0 -3] in the last matrix. In terms of the rows R1,
R2 and R3 of the original matrix, the last row is:
$$\left[ 0\text{ 0 0 -3} \right]=\left( {{R}_{3}}-4{{R}_{1}} \right)-\left( {{R}_{2}}-3{{R}_{1}} \right)={{R}_{3}}-({{R}_{1}}+{{R}_{2}})$$
The fact that
this is almost zero suggest that we compare R3 with R1+R2 or, what is the same
thing, that we compare the third equation with the first plus the second.
Third equation:
$$4x+y+6z=1$$
First equation
plus the second:
$$4x+y+6z=4$$
Since no numbers
x,y, and z can satisfy both these equations, the system has no solution.
The key to all
these examples is carrying the augmented matrix to reduced row-echelon form. Suppose
an arbitrary matrix is presented to you, even one that is not the augmented
matrix of a system of linear equations. Here is a step-by- step procedure by
which it can be brought to row-echelon form.
GUSSIAN ALGORITHM
Step 1: If the matrix consists entirely of zeros,
stop-it is already in row-echelon form.
Step 2: Otherwise, find the first column form the
left containing a nonzero entry (call it a) and move
the
row containing that entry to the top position.
Step 3: Now multiply that row by 1/a to create
leading 1.
Step 4: By subtracting multiples of that row from
rows below it, make each entry below the leading 1
zero.
This completes the first row, and all further row operations
are carried out on the other rows.
Step 5: Repeat steps 1-4 on the matrix consisting of
the remaining rows.
The process stops when either no rows remain at step
5 or the remaining rows consist of zeros.
|
Observe that the Gaussian algorithm is
recursive: When the first leading 1 has been obtained, the procedure is
repeated on the remaining rows of the matrix. This makes algorithm easy to use
on a computer.
No comments:
Post a Comment