In this section, we discuss the algorithm for reducing any matrix, whether or not the matrix is viewed as an augmented matrix for linear system, to a simple form that could be used for further analysis and/or computation. This form is known as the reduced row echelon form, which is usually abbreviated as rref. This algorithm utilizes row operations to put the augmented matrix into a special form, which is usually called as Gauss--Jordan elimination; it consists of two stages, a forward phase (usually referred to as Gaussian elimination) in which matrix is transferred to a kind of upper triangular or "steplike" matrix (see the previous section), and a backward phase in which zeroes are introduced in each column containing a pivot using row operations. When a linear system of equations is solved numerically, it nearly always uses Gaussian elimination. The second stage is not so essential for solving linear systems of equations because the Gauss--Jordan method is inefficient for practical calculations. The main reason for this is that the Gaussian elimination uses backward substitution while the Gauss--Jordan algorithm suggests to implement backward elimination, which involves roughly 50% more operations than Gaussian elimination. The Gauss--Jordan elimination is an essential algorithm for solving other problems such as matrix equations, but for linear systems of equations it is pure theoretical.
The basic idea of the backward elimination was popularized by the German engineer Wilhelm Jordan in his book on geodesy (the science of measuring Earth shapes) entitled Handbuch der Vermessungskunde and published in 1888. However, the method was also appeared in an article by Clasen published in the same year. Jordan and Clasen probably discovered Gauss--Jordan elimination independently.
Johann Carl Friedrich Gauss (1777--1855) was a German mathematician and physicist who made significant contributions to many fields in mathematics and sciences.
Wilhelm Jordan (1842--1899) was a German geodesist who conducted surveys in Germany and Africa and founded the German geodesy journal.
Since the first stage of Gauss--Jordan algorithm was discussed in the previous section, it is assumed that the reader is familiar with it. For further exposition, we need some new definitions along with the previously discussed terminology. The aim of the Gaussian elimination is to reduce a full system of linear equations in n unknowns to triangular form using elementary row operations, thereby reducing a problem that we can’t solve to one that we can. Mathematica has a special command, RowReduce, for the Gauss--Jordan algorithm. The only unfortune aspect of using the command RowReduce is that it does not actually give the solution to the original system. You must still write out the solution yourself from rref matrix. On the other hand, the Solve command gives the actual solution to the system where you can specify which variables to solve for in the system. In this case, you should know in advance the dimension of the solution set.
Two matrices are row-equivalent if one can be obtained from the other by a sequence of row operations.
Theorem:
Suppose that two matrices are row-equivalent augmented matrices. Then the systems of linear equations that they represent are equivalent systems.
A matrix is in reduced row echelon form (rref) if it meets all of the following conditions:
If there is a row (called a zero row) where every entry is zero, then this row lies below any other row that contains a nonzero entry.
The first nonzero entry of a nonzero row is a 1. This is called a leading 1 and its location in the matrix is referred to as the pivot position. A column that contains a pivot position is called a pivot column.
The leftmost nonzero entry of a row is the only nonzero entry, the leading 1, in its column.
Any column in which a leading 1 appears has zeroes in every other entry.
Theorem:
Every matrix has a unique reduced row echelon form.
Suppose that A is an m×n matrix and that is row equivalent to two m×n matrices B and C in reduced row-echelon form. We need to show that B = C.
If B and C are both row-equivalent to A, then they are row-equivalent to each other. Repeated row operations on a matrix combine the rows with each other using operations that are linear, and are identical in each column. A key observation for this proof is that each individual row of B is linearly related to the rows of C. This relationship is different for each row of B, but once we fix a row, the relationship is the same across columns. More precisely, there are scalars δ_{ij}, i,j = 1,2, ... , m, such that
So an entry of row i of matrix B (in column j) is a
linear function of the entries of all the rows of matrix C that are
also in column j, and the scalars (δ_{ik}) depend on which row
of B we are considering (the i subscript on δ_{ik}), but
are the same for every column (no dependence on j in δ_{ik}).
We now repeatedly exploit the fact that B and C are in reduced
row-echelon form. Recall that a pivot column is all zeroes, except a single
one. More carefully, if R is a matrix in reduced row-echelon form, and
d_{ℓ} is the index of a pivot column, then
[R]_{kdℓ}=1 precisely when k=ℓ and is
otherwise zero. Notice also that any entry of R that is both below the
entry in row ℓ and to the left of column d_{ℓ} is also zero
(with below and left understood to include equality). In other words, look at
examples of matrices in reduced row-echelon form and choose a leading 1 (with
a box around it). The rest of the column is also zeros, and the lower left
“quadrant” of the matrix that begins here is totally zeros.
Assuming no relationship about the form of B and C, let B
have r nonzero rows and denote the pivot columns as D =
{ d_{1}, d_{2}, ... , d_{r} |. For C, let
p denote the number of nonzero rows and denote the pivot columns as
P = \{ e_{1}, e_{2}, ... , e_{p} }. There are
four steps in the proof, and the first three are about showing that B
and C have the same number of pivot columns, in the same places. In
other words, the “e” symbols are a necessary fiction.
The entries of C are all zero since they are left and below of the
leading 1 in row 1 and column e_{1} of C. This is a
contradiction, so we know that d_{1} ≥ e_{1}.
Together this means that d_{1} = e_{1}.
Second Step. Suppose that we have determined that
d_{1} = e_{1},
d_{2} = e_{2}, ... ,
d_{u} = e_{u}. Let us now show that
d_{u+1} = e_{u+1}. Working towards a
contradiction, suppose that
d_{u+1} < e_{u+1}. For 1 ≤ ℓ ≤ u.
This contradiction shows that d_{u+1} ≥
e_{u+1}. By an entirely similar argument, we could conclude that
d_{u+1} ≤ e_{u+1}, and therefore
d_{u+1} = e_{u+1}.
Third Step. Now we establish that r = p. Suppose that
p < r. By the arguments above, we know that
d_{1} = e_{1},
d_{2} = e_{2}, ... ,
d_{p} = e_{p}. For 1 ≤ ℓ ≤ u < r,
So row r is a totally zero row, contradicting that this should be the
bottom most nonzero row of B. Hence, u ≥ r. By an
entirely similar argument, reversing the roles of B and C, we
would conclude that u ≤ r, and therefore u = r.
Thus, combining the first three steps we can say that D = P.
In other words, B and C have the same pivot columns, in the
same locations.
Fourth Step. In this final step, we will not argue by contradiction. Our
intent is to determine the values of the δ_{ij}. Notice that we can
use the values of the d_{i} interchangeably for B and
C. Here we go,
So B and C have equal values in every entry, and so are the same
matrix.
■
input m, n and A
r := 0
for j := 1 to n
i := r+1
while i <= m and A[i,j] == 0
i := i+1
if i < m+1
r := r+1
swap rows i and r of A (row op 1)
scale A[r,j] to a leading 1 (row op 2)
for k := 1 to m, k <> r
make A[k,j] zero (row op 3, employing row r)
output r and A
Matlab code:
function sol=GaussJ(Ab)
[m,n]=size(Ab);
for i=1:m
Ab(i,:)=Ab(i,:)/Ab(i,i);
for j=1:m
if j==i; continue;
end
Ab(j,:)=Ab(j,:)-Ab(j,i)*Ab(i,:);
end; end; sol=Ab;
As we see, the given matrix A is reduced to the rref form that contains
three pivots in columns 1, 3, and 6. Therefore, the corresponding system of
linear equations has three leading variables x_{1},
x_{3}, and x_{6}, and three free variables
x_{2}, x_{4}, x_{5}.
Solving for the leading variables (marked in red), we obtain
It is clear that the rref matrix is independent of the order of the equations,
or equivalently, the rows in the augmented matrix associated with the linear
system. Now we solve the given system of linear equations using standard
Solve command:
Every homogeneous system of linear equations is consistent because all such systems have a trivial solution: x_{1} = x_{2} = ... = x_{n} = 0. If there are other solutions, they are called nontrivial solutions. So there are only two possibilities for homogeneous systems of equations:
The system has only the trivial solution.
The system has infinitely many solutions in addition to the trivial
solution.
Example:
Use Gauss-Jordan elimination to solve the homogeneous linear system:
The first elimination step is to eliminate the elements a_{21} =
2 and a_{31} = 3 in the original matrix A =
[a_{ij}] by subtracting the multiples m_{21} =
2 and m_{31} = 3 of row 1 from rows 2 and 3, respectively,
which gives
This completes the forward elimination stage required by the Gaussian
elimination.
To obtain the reduced row echelon form, we first need to divide the second row
and the third row by -5 and -10, respectively, in order to see leading 1's on
the main diagonal:
The first elimination step in the backward stage is to eliminate the
element a_{21} = 2 in the first row by subtracting 2 times the
second row from the first one:
The second elimination step in the backward stage is to eliminate the
elements a_{31} = 1 and a_{32} = -1. So we
add the last row to the second one and subtract it from the first row. This
yields
A = {{1, 2, -1}, {2, -1, 3}, {3, -3, -4}}
b = {6, -3, 1}
LinearSolve[A, b]
{1, 2, -1}
The same output is obtained with the reduced row echelon form:
GaussianElimination[A_?MatrixQ, b_?VectorQ] :=
Last /@ RowReduce[Flatten /@ Transpose[{A, b}]]
A = {{1, 2, -1}, {2, -1, 3}, {3, -3, -4}}
b = {6, -3, 1}
GaussianElimination[A, b]
This completes the Gauss-Jordan elimination procedure. Obviously, the original set of equations has been transformed to a diagonal form. Now expressing the set in algebraic form leads to
\[
x_1 =1, \quad x_2 =2 , \quad x_3 =-1 ,
\]
which is the required solution of the given system.
■
We first define B^{(1)} to be the original augmented matrix.
Then, we denote by B^{(2)} the result of
the first elementary row operation, which entails subtracting 3 times the
first row from the second in order to eliminate x_{1}
from the second equation:
Determine which matrices are in reduced echelon form and which others are only
in echelon form.
\[
(a)\ \begin{bmatrix} 1&0&0&0 \\ 0&1&0&3 \\0&0&1&6 \end{bmatrix}, \qquad
(b) \ \begin{bmatrix} 1&0&1&2&0&4 \\ 0&1&-2&2&0&3 \\ 0&0&0&0&1&5
\end{bmatrix}, \qquad (c) \ \begin{bmatrix} 1&0&1&0 \\ 0&1&1&0 \\ 0&0&0&1
\end{bmatrix},
\]
\[
(d)\ \begin{bmatrix} 1&0&0&0 \\ 0&1&1&0 \\ 0&0&0&0 \\ 0&0&0&1 \end{bmatrix},
\qquad (e) \ \begin{bmatrix} 1&2&0&1&4 \\ 0&2&0&3&3 \\ 0&0&0&2&2 \\
0&0&0&0&1 \end{bmatrix} , \qquad (f) \ \begin{bmatrix} 1&1&0&0 \\ 0&1&1&0 \\
0&0&1&1 \end{bmatrix} .
\]
Consider the two 3×4 matrices below
\[
{\bf B} = \begin{bmatrix} 1&3&-2&2 \\ -1&-2&-1&-1 \\ -1&-5&8&-3 \end{bmatrix},
\quad {\bf C} = \begin{bmatrix} 1&2&1&2 \\ 1&1&4&0 \\ -1&-1&-4&1 \end{bmatrix} .
\]
Row-reduce each matrix and determine that the reduced row-echelon forms of
B and C are identical. From this argue that B and C
are row-equivalent.
Perform Gauss--Jordan elimination on the following systems of equations, but
without partial pivoting (without swapping rows).
where x_{1}, x_{2}, and x_{3}
denote prices in dollars of goods 1, 2, and 3, respectively. Find the prices
that solve the system using the Gauss-Jordan elimination method.
If matrix A represents an augmented matrix system of equations of the
form \( ax_{1}+bx_{2}+cx_{3}=d, \) find the values of \( x_{1}, x_{2} , \) and x_{3}.