The leading entry of a row of a matrix is the left-most nonzero entry of the row.

Definition. An \(m\times n\) matrix \(A\) is in echelon form (or REF=row echelon form) if

1. all zero rows at the bottom,


2. all entries in a column of a leading entry below the leading entry are zeros, and


3. the leading entry of each row is to the right of all leading entries in the rows above it.

\(A\) is in reduced echelon form (or RREF=reduced row echelon form) if it satisfies two additional conditions:

4. the leading entry of each row is 1 and


5. each leading 1 is the only nonzero entry in its column.

Example.

1. The following matrices are in REF: \[\left[\begin{array}{rrrr}\boxed{1}&-2&1&0\\0&0&\boxed{4}&3\\0&0&0&0\end{array} \right],\;\; \left[\begin{array}{rrrr}\boxed{1}&-2&1&0\\0&0&\boxed{4}&3\\0&0&0&\boxed{5}\end{array} \right]\]


2. The following matrices are in RREF: \[\left[\begin{array}{rrrr}\boxed{1}&-2&0&0\\0&0&\boxed{1}&3\\0&0&0&0\end{array} \right],\;\; \left[\begin{array}{rrrr}\boxed{1}&-2&0&0\\0&0&\boxed{1}&0\\0&0&0&\boxed{1}\end{array} \right]\]

Definition. A pivot position in a matrix \(A\) is a position of a leading 1 in the RREF of \(A\) and corresponding column is a pivot column. A pivot is a nonzero number in a pivot position of \(A\) that is used to create zeros below it in Gaussian elimination.

Example. Pivot positions of the last matrix are \((1,1)\), \((2,3)\), and \((3,4)\).

The Gaussian elimination or row reduction algorithm to get the REF of a matrix is explained by the following example:
Example. \(A=\left[\begin{array}{rrrrr}0&3&-6&5&-5\\3&-7&8&-7&9\\3&-9&12&-9&15 \end{array}\right]\)

1. Start with the left-most nonzero column (first pivot column) and make its top entry nonzero by interchanging rows if needed. This top nonzero entry is the pivot of the pivot column. \[\left[\begin{array}{rrrrr}0&3&-6&5&-5\\3&-7&8&-7&9\\3&-9&12&-9&15 \end{array} \right] \xrightarrow{R_1\leftrightarrow R_3} \left[\begin{array}{rrrrr}3&-9&12&-9&15\\3&-7&8&-7&9\\0&3&-6&5&-5 \end{array} \right]\]


2. Create zeros below the pivot by row replacements. \[\left[\begin{array}{rrrrr}\boxed{3}&-9&12&-9&15\\3&-7&8&-7&9\\0&3&-6&5&-5 \end{array} \right] \xrightarrow{-R_1+R_2} \left[\begin{array}{rrrrr}\boxed{3}&-9&12&-9&15\\0&2&-4&2&-6\\0&3&-6&5&-5 \end{array} \right]\]


3. Ignore the column and row of the current pivot and repeat the preceding steps for the rest submatrix. \[\left[\begin{array}{rrrrr} {\color{gray}\boxed{3}}&{\color{gray}-9}&{\color{gray}12}&{\color{gray}-9}&{\color{gray}15}\\ {\color{gray}0}&\boxed{2}&-4&2&-6\\ {\color{gray}0}&3&-6&5&-5 \end{array} \right] \xrightarrow{-\frac{3}{2}R_2+R_3} \left[\begin{array}{rrrrr} {\color{gray}\boxed{3}}&{\color{gray}-9}&{\color{gray}12}&{\color{gray}-9}&{\color{gray}15}\\ {\color{gray}0}&\boxed{2}&-4&2&-6\\ {\color{gray}0}&0&0&\boxed{2}&4 \end{array} \right] (REF)\]

To get RREF start with the right-most pivot, make it 1 by scaling, and then create zeros above it by row replacements. Repeat it for the rest of the pivots. \[\left[\begin{array}{rrrrr} \boxed{3}&-9&12&-9&15\\ 0&\boxed{2}&-4&2&-6\\ 0&0&0&\boxed{2}&4 \end{array} \right] \xrightarrow{\frac{1}{2}R_3} \left[\begin{array}{rrrrr} \boxed{3}&-9&12&-9&15\\ 0&\boxed{2}&-4&2&-6\\ 0&0&0&\boxed{1}&2 \end{array} \right] %\xrightarrow[-2R_3+R_2]{9R_3+R_1} \xrightarrow{\substack{\;\;\;9R_3+R_1\\ -2R_3+R_2}} \left[\begin{array}{rrrrr} \boxed{3}&-9&12&0&33\\ 0&\boxed{2}&-4&0&-10\\ 0&0&0&\boxed{1}&2 \end{array} \right] \] \[\xrightarrow{\frac{1}{2}R_2} \left[\begin{array}{rrrrr} \boxed{3}&-9&12&0&33\\ 0&\boxed{1}&-2&0&-5\\ 0&0&0&\boxed{1}&2 \end{array} \right] \xrightarrow{9R_2+R_1} \left[\begin{array}{rrrrr} \boxed{3}&0&-6&0&-12\\ 0&\boxed{1}&-2&0&-5\\ 0&0&0&\boxed{1}&2 \end{array} \right] \xrightarrow{\frac{1}{3}R_1} \left[\begin{array}{rrrrr} \boxed{1}&0&-2&0&-4\\ 0&\boxed{1}&-2&0&-5\\ 0&0&0&\boxed{1}&2 \end{array} \right] (\text{RREF}) \]

Remark. The above algorithm to get RREF is called Gauss-Jordan elimination. The RREF of \(A\) is unique as it does not depend on the elementary row operations applied to \(A\).

Steps to solve a linear system \(A\overrightarrow{x}=\overrightarrow{b}\) (Gaussian elimination):

1. Find the RREF of the augmented matrix \([A\:\overrightarrow{b}]\).


2. Write the system of linear equations corresponding to the RREF.


3. If the new system is inconsistent, there is no solution of the original system. Otherwise write the basic variables (variables corresponding to pivot columns) in terms of constant and free variables (non-basic variables which corresponds to non-pivot columns).

Example. \[\begin{eqnarray*} \begin{array}{rcrcrcrcr} x_1&-&3x_2 &&&+&2x_4&=&1\\ 2x_1&-&6x_2 &+&x_3&+&10x_4&=&0\\ -x_1&+&3x_2 &+&x_3&+&4x_4&=&-3 \end{array} \end{eqnarray*}\] We find the RREF of the augmented matrix: \[\left[\begin{array}{rrrrr} \boxed{1}&-3&0&2&1\\ 2&-6&1&10&0\\ -1&3&1&4&-3 \end{array} \right] \xrightarrow[R_1+R_3]{-2R_1+R_2} \left[\begin{array}{crcrr} \boxed{1}&-3&0&2&1\\ 0&0&\boxed{1}&6&-2\\ 0&0&1&6&-2 \end{array} \right] \xrightarrow{-R_2+R_3} \left[\begin{array}{crcr|r} \boxed{1}&-3&0&2&1\\ 0&0&\boxed{1}&6&-2\\ 0&0&0&0&0 \end{array} \right] \] Corresponding system is \[\begin{eqnarray*} \begin{array}{rcrcrcrcr} x_1&-&3x_2 &&&+&2x_4&=&1\\ && &&x_3&+&6x_4&=&-2\\ && &&&&0&=&0 \end{array} \end{eqnarray*}\] where \(x_1\) and \(x_3\) are basic variables (for pivot columns) and \(x_2\) and \(x_4\) are free variables (for non-pivot columns). \[\begin{eqnarray*} \begin{array}{rcl} x_1&=&1+3x_2-2x_4\\ x_2&=&\text{free}\\ x_3&=&-2-6x_4\\ x_4&=&\text{free} \end{array} \end{eqnarray*}\] The solution set is \(\{(1+3s-2t,s,-2-6t,t)\; |\; s,t\in \mathbb R\}\). If we solve the corresponding matrix equation \(A\overrightarrow{x}=\overrightarrow{b}\), the solution set is \[\left\lbrace \left[\begin{array}{r}1+3s-2t\\ s\\ -2-6t\\ t \end{array} \right] \; |\; s,t\in \mathbb R \right\rbrace =\left\lbrace \left[\begin{array}{r}1\\ 0\\ -2\\ 0 \end{array} \right] +s \left[\begin{array}{r}3\\ 1\\ 0\\ 0 \end{array} \right] +t \left[\begin{array}{r}-2\\ 0\\ -6\\ 1 \end{array} \right] \; |\; s,t\in \mathbb R \right\rbrace.\]

Possibilities of solutions of \(A\overrightarrow{x}=\overrightarrow{b}\) from the RREF:

• System has no solution (inconsistent) iff the RREF of \([A\:\overrightarrow{b}]\) has a row of the form \[[0,\ldots, 0, c], c\neq 0.\]


• System has a solution (consistent) iff the RREF of \([A\:\overrightarrow{b}]\) has no row of the form \[[0,\ldots, 0, c], c\neq 0.\]
• Infinitely many solution if the RREF of \([A\:\overrightarrow{b}]\) has a non-pivot column that is not the last column (there is a free variable).


• Unique solution if all but the last column of the RREF of \([A\:\overrightarrow{b}]\) are pivot columns (there is no free variable).

Last edited