Row reduction of linear systems

Example. Consider the following SLE in standard form. \[\begin{align*} 2x_1\hphantom{+x_2}+x_3\hphantom{+x_4}-2x_5&=2\\ \hphantom{2x_1+}x_2\hphantom{+x_3}-x_4+2x_5&=-3\\ 3x_1\hphantom{+x_2+x_3}+x_4\hphantom{+2x_5}&=2 \end{align*}\]

Note that for a coefficient, which equation it is in depends on its row, and which variable it is the coefficient of depends of the column. In summary, equation and variable are determined by the position of the coefficient. Therefore, the SLE can be described by a table of numbers. It is called the augmented matrix of the SLE. In this case, it will be as follows. \[ \left( \begin{array}{rrrrr|l} 2 & 0 & 1 & 0 & -2 & 2\\ 0 & 1 & 0 & -1 & 2 & -3\\ 3 & 0 & 0 & 1 & 0 & 2 \end{array} \right) \] Definition. An \(m\times n\) matrix is a table of numbers with \(m\) rows and \(n\) columns. An augmented matrix is a matrix with the rightmost column separated from the rest by a vertical line. The plural of the word matrix is matrices. Notation. As in the above example, we will usually denote matrices with enclosing the table in parentheses. An alternative notation is to enclose the table with square brackets: \[ \left[ \begin{array}{rrrrrr} 2 & 0 & 1 & 0 & -2 & 2\\ 0 & 1 & 0 & -1 & 2 & -3\\ 3 & 0 & 0 & 1 & 0 & 2 \end{array} \right] \] Matrices are usually denoted by uppercase letters. By convention, if \(A\) is a matrix, then the coefficient in the \(i\)-th row and \(j\)-th column is denoted by both \(a_{ij}\) and \(A_{ij}\). The row vector that is the \(i\)-th row of the matrix is denoted by \(A_i\). The column vector that is the \(j\)-th column of the matrix \(A\) is denoted by \(A_j\). Definition. Since augmented matrices represent SLE's, correspondingly we have elementary row operations for matrices too. Let \(A\) be a matrix.

  1. Swap the \(i\)-th row and the \(j\)-th row (\(A_i\leftrightarrow A_j\))
  2. Multiply the \(i\)-th row by a nonzero scalar c (\(cA_i\))
  3. Let \(d\) be a scalar. Add to the \(i\)-th row scalar \(d\) times the \(j\)-th row (\(A_i+dA_j\))
  4. Let \(c\) be a nonzero scalar and \(d\) a scalar. Multiply the \(i\)-th row by \(c\), and add to it \(d\) times the \(j\)-th row (\(cA_i+dA_j\))

In these we have \(i\ne j\). Note that 4 is a combination of 2 and 3. I added it for ease of computation. It is also strictly speaking not an elementary row operation, so if you are asked to list the elementary row operations, only list 1-3.

As advertized in Section 2.2, now we will see how to detect that a matrix is in such a form solutions can be readily read off. We will also see a method to achieve this form.

Definition. A matrix \(A\) is in reduced row echelon form (RREF), if the following conditions are satisfied.

  1. In every nonzero row, from the left to the right, the first nonzero coefficient is a 1. This is called a leading 1.
  2. In a column containing a leading 1, all the other entries are 0.
  3. If a leading 1 is above another leading 1, then it is also to the left of the other.
  4. Any zero rows are below any nonzero rows.

3 and 4 are important conditions for making the RREF of a matrix unique, but we will see that it's actually not important for reading off solutions. Therefore, if you have to find solutions, you don't necessarily have to make 3 and 4 hold. But if you're asked to transform a matrix to RREF, make sure that 3 and 4 hold!

Theorem. Let \(A\) be a matrix. Then the following assertions are true.

  1. \(A\) can be transformed into RREF by a finite number of elementary row operations.
  2. The RREF of \(A\) is unique. That is, whichever elementary row operations you have used, you should end up with the same RREF.

Method (Gauss--Jordan elimination). Let \(A\) be a matrix. You can transform it into RREF by performing the following steps.

  1. Go column by column, from the left to the right. Suppose that we are at the \(j\)-th column \(A^j\).
  2. If \(A^j\) has no nonzero entries in nonzero rows that do not have a leading 1 yet, then move on to \(A^{j+1}\).
  3. Else, select a nonzero entry \(a_{ij}\) such that the row \(A_i\) does not have a leading 1 yet. You might want to take an integer with a minimal absolute value, or the smallest positive integer, or the fraction with the smallest denominator.
  4. Make \(a_{ij}\) into a leading 1 by the row operation \(\frac{1}{a_{ij}}A_i\). Make \(a_{ij}\) be unique in its column by performing \(A_k-a_{kj}A_i\) for all \(k\ne i\) (note that by this point \(a_{ij}=1\)).
  5. Keep going on until every nonzero row has a leading 1.
  6. If you actually want \(A\) in RREF, not just the solution set of the corresponding SLE, swap some rows to make that happen.

To describe the solution set, transform the matrix back into a SLE. First, check if there a row which is a contradiction. If not, make all variables which do not correspond to leading 1's (if any) into distinct parameters. Then the leading 1's will give functions of the parameters for the other variables.

Example. Let's check out our starting example. It can be row reduced into the matrix \[ \left( \begin{array}{rrrrr|l} 1 & 0 & 0 & \frac13 & -2 & \frac23 \\ 0 & 1 & 0 & -1 & 2 & -3 \\ 0 & 0 & 1 & -\frac23 & 2 & \frac23 \end{array} \right) \] Therefore, the solution set is the 2-parameter family \[\begin{align*} x_1&=-\frac13x_4+2x_5-\frac23 \\ x_2&=x_4-2x_5+3 \\ x_3&=\frac23x_4-2x_5-\frac23, \end{align*}\]

where \(x_4\) and \(x_5\) are parameters.

Example. Let's find the solution set of the SLE corresponding to the augmented matrix \[ \left( \begin{array}{rrr|l} 2 & 0 & -1 & 2 \\ -1 & 2 & 1 & 0 \\ 0 & 1 & 0 & 3 \end{array} \right) \] This can be reduced to \[ \left( \begin{array}{rrr|l} 0 & 0 & 1 & -\frac{10}{3} \\ 1 & 0 & 0 & \frac83 \\ 0 & 1 & 0 & 3 \end{array} \right) \] In this case, every variable corresponds to a leading 1, so there are no parameters. The solution is the unique point \[\begin{align*} x_1&=\frac83\\ x_2&=3\\ x_3&=-\frac{10}{3}. \end{align*}\]

Example. Let's find the solution set of the SLE corresponding to the augmented matrix \[ \left( \begin{array}{rrrr|l} 1 & 1 & 3 & 2 & 1 \\ 2 & 0 & -4 & 0 & 1 \\ -3 & 0 & 6 & 0 & 2 \\ \end{array} \right) \] By performing the row operation (\(2R_3+3R_2\)), the third row gets replaced by \((0\ 0\ 0\ 0\,|\,7)\). In equation form, this is \(0=7\), which is a contradiction. Therefore, there are no solutions.

Definition. If we only care about how many parameters we need to describe the solution set, it is enough to transform the matrix into Row Echelon Form (REF). A matrix \(A\) is in REF, if the following assertions hold.

  1. The first nonzero entry in a row is called a leading entry
  2. There are no nonzero coefficients below a leading entry.
  3. If a leading entry is above another leading entry, then it is also to the left of the other one.
  4. Nonzero rows are below nonzero rows.

Example. Let's transform the augmented matrix \[ \left( \begin{array}{rrrr|l} 2 & 1 & 0 & -1 & 2 \\ 0 & 2 & 1 & 0 & 3 \\ 1 & 0 & 2 & 1 & -1 \end{array} \right) \] to REF. REF's are not unique but for example we can get \[ \left( \begin{array}{rrrr|l} 1 & 0 & 2 & 1 & -1 \\ 0 & 1 & -4 & -3 & 4 \\ 0 & 0 & 1 & \frac23 & -\frac59 \end{array} \right) \] There are 4 variables and 3 leading 1's, so the solution will be a 1-parameter family.