System of Linear Equations
 
A system of m linear equations in n unknowns is given as :
  
a11 x1 + a12 x2 + . . . . . . a1n xn = b1  
a21 x1 + a22 x2 + . . . . . . a2n xn = b2
   :                                                                 :
   :                                                                 :
am1 x1 + am2 x2 + . . . . . . amn xn = bm
               
                line1.gif (1200 bytes)
               
The system can be conveniently written in matrix form as     A x = b
by putting   A = [ aij ] ,  x = [ x1 x2  . . . . . xn ] T  and   b = [ b1 b2 . . . . . bm ] T
The system  A x = b  is said to be consistent if it has a solution. (see Example 1  & Example 2)
It is said to be inconsistent if it has no solution. (see Example 3)
    
Example 1 :   The following equation  2x1- x2 = 3
is consistent because as  x1= 2 ,  x2 = 1
In fact, there are infinitely many sets of solutions :

For  x1 =   ,  x2 =    

  
Example 2 :   The following system of equations  
          2x1- x2 = 3   
            x1- x2 = 1
is consistent and has uniqtue soluion [ x1   x2 ] T  = [ 2   1 ] T.
  
Example 3 :   The following system of equations  
           2x1- x2 = 3   
       -x1+ 0.5x2 = 2
is inconsistent because no value of xi can satisfy the system.

I. Reduced Row Echelon Form
An m x n  matrix is said to be in reduced row echelon form ( see Example 4 ) when
(a)   all rows consisting entirely zeros, if any, are at the bottom of the matrix; and
(b)   the first nonzero entry in each row is equal to 1 (called the leading entry); and
(c)   if rows i and i +1 are two successive rows that do not consist entirely of zeros
  then the leading entry of row i +1 is to the right of the leading enrtry of row i;
  and
(d)   if a column contains a leading entry of some row, then all other entries in that
  column are zeros.
Note: A matrix satisfies only (a), (b) and (c) is said to be in row echelon form.
          (see Example 5)
Example 4 :  The following matrices are in reduced row echelon form   
  ,                
  
Example 5 :   The following matrices are in row echelon form
A = , B =               
  Question A 
  Matrix A is not a reduced row echelon form because :
sball.gif (573 bytes)QA1.gif (894 bytes) QA0r.gif (903 bytes)
sball.gif (573 bytes)QA2.gif (881 bytes) QA0r.gif (903 bytes)
sball.gif (573 bytes)QA3.gif (1045 bytes) QA0r.gif (903 bytes)
  Question B 
  Matrix B is not a reduced row echelon form because :
sball.gif (573 bytes)QB1.gif (242 bytes) QA0r.gif (903 bytes)
sball.gif (573 bytes)QB2.gif (238 bytes) QA0r.gif (903 bytes)
 
Example 6 :  
The following matrices is neither a reduced row echelon form nor   
a row echelon form
C = rrefex9.gif (1171 bytes) , D =               
  
Note :   A matrix can be transformed to reduced row echelon form
  by applying the elementary row operation.
 
  
II. Elementary Row Operation
The following row operations can eliminate a matrix to reduced row echelon form
(a) Interchange any two rows.
(b) Multiply any row by a nonzero scalar.
(c) Add a multiple of one row to another row.
Example 7 :   Matrix C in  Example 6   can be transformed to reduced row echelon form if we multiply row 2 by 0.5
C =   ,      0.5  x  R2   R2 
Exercise : Transform matrix D in  Example 6  to reduced row echelon form.
  
Theorem I :
Every  coefficient  matrix  A  of  a linear system  can be
reduced to row-echelon form or  reduced row-echelon form
by applying a sequence of elementary row operations to A.

 


III. Gaussian Elimination Method
Consider the linear system  A x = b   and its augmented matrix  [ A | b ] .
If, by a sequence of elementary row operations,  [ A | b ]   is reduced to 
[ A' | b' ]   such that A' is in row-echelon form, then the equivalent system
A' x = b'  can be solved by some simple steps. This method is called the
Gaussian Elimination.
Example 8 :
The linear system          -x1   +  x2    - 4x3   =  -10
3x1  + 2x2             =   1
2x1  + 3x2   - 2x3   =   3
has augmented matrix   Aug1.gif (429 bytes)
which can be reduced   Aug2.gif (488 bytes) 
by the elementary row
operations to
This is equivalent to       x1   - x2     + 4x3   =   10
        x2   - 2.4x3   =  - 5.8
                    x3   =    6
Thus we obtain    x = [  - 6.4    7.6    6   ] T   as the only solution.


IV. Gauss-Jordan Method
If the linear system  A x = b   and its augmented matrix  [ A | b ]  is reduced
to  [ R | C ] , such that R is in reduced row-echelon form, by elementary row
operations, then the solutionof the equivalent system  R x = C  can be
obtained easily.  This is called the Gauss - Jordan  Method.
Example 9 :  
Consider the linear system       x1 +   2x2 -  3x3  + 4x4 =  15
- 6x1          + 5x3          =  - 4
            8x2         + 7x4 =  22
has augmented matrix    Augmat.gif (471 bytes)
which can be reduced to reduced row Redmat.gif (724 bytes)
-echelon form by the elementary row
operations to
If we let  x1 = - 1  , then the solution    x =  [  - 1     1    - 2      2   ] T .
 
Theorem II :
Let  R  be a   m x n  matrix which is in reduced row-echelon
form. If R has r non-zero rows, then the system R x = C  is
consistent if and only if  cj = 0  when r < j m.