---

Example

Solve the linear system

\[\begin{aligned*}
  x + 2y + z & = 1 \\
  3x + y + 4x & = 0 \\
  2x + 2y + 3z & = 2.
\end{aligned*}
\]

Phase 1. Towards the row echelon form.

1. Write an augmented matrix.

   \[\begin{equation*}
     M =
     \begin{pmatrix}
       1 & 2 & 1 & 1 \\
       3 & 1 & 4 & 0 \\
       2 & 2 & 3 & 2
     \end{pmatrix}.
   \end{equation*}
   \]

2. Move all zero rows.

   Nothing to do.

3. Enumerating rows, top to bottom:

   For \(M_1\):

   1. Scale the selected row.

      Nothing to do.

   2. Replace the rows below the selected row.

      \(M_2 \gets M_2 + kM_1\) with \(k = -3\), so

      \[\begin{align*}
        M
        & \gets
        \begin{pmatrix}
          1 & 2 & 1 & 1
          \\
          3 + (-3) \cdot 1
          & 1 + (-3) \cdot 2
          & 4 + (-3) \cdot 1
          & 0 + (-3) \cdot 1
          \\
          2 & 2 & 3 & 2
        \end{pmatrix}
        \\[2ex]
        & =
        \begin{pmatrix}
          1 & 2 & 1 & 1 \\
          0 & -5 & 1 & -3 \\
          2 & 2 & 3 & 2
        \end{pmatrix}.
      \end{align*}
      \]

      \(M_3 \gets M_3 + kM_1\) with \(k = -2\), so

      \[\begin{align*}
        M
        & \gets
        \begin{pmatrix}
          1 & 2 & 1 & 1 \\
          0 & -5 & 1 & -3
          \\
          2 + (-2) \cdot 1
          & 2 + (-2) \cdot 2
          & 3 + (-2) \cdot 1
          & 2 + (-2) \cdot 1
        \end{pmatrix}
        \\[2ex]
        & =
        \begin{pmatrix}
          1 & 2 & 1 & 1 \\
          0 & -5 & 1 & -3 \\
          0 & -2 & 1 & 0
        \end{pmatrix}.
      \end{align*}
      \]

   For \(M_2\):

   1. Scale the selected row.

      \(M_2 \gets kM_2\) with \(k = -\frac{1}{5}\), so

      \[\begin{align*}
        M
        & \gets
        \begin{pmatrix}
          1 & 2 & 1 & 1
          \\
          -\frac{1}{5} \cdot 0
          & -\frac{1}{5} \cdot (-5)
          & -\frac{1}{5} \cdot 1
          & -\frac{1}{5} \cdot (-3)
          \\
          0 & -2 & 1 & 0
        \end{pmatrix}
        \\[2ex]
        & =
        \begin{pmatrix}
          1 & 2 & 1 & 1 \\
          0 & 1 & -\frac{1}{5} & \frac{3}{5} \\
          0 & -2 & 1 & 0
        \end{pmatrix}.
      \end{align*}
      \]

   2. Replace the rows below the selected row.

      \(M_3 \gets M_3 + kM_2\) with \(k = 2\), so

      \[\begin{align*}
        M
        & \gets
        \begin{pmatrix}
          1 & 2 & 1 & 1 \\
          0 & 1 & -\frac{1}{5} & \frac{3}{5}
          \\
          0 + 2 \cdot 0
          & -2 + 2 \cdot 1
          & 1 + 2 \cdot (-\frac{1}{5})
          & 0 + 2 \cdot \frac{3}{5}
        \end{pmatrix}
        \\[2ex]
        & =
        \begin{pmatrix}
          1 & 2 & 1 & 1 \\
          0 & 1 & -\frac{1}{5} & \frac{3}{5} \\
          0 & 0 & \frac{3}{5} & \frac{6}{5}
        \end{pmatrix}.
      \end{align*}
      \]

   For \(M_3\):

   1. Scale the selected row.

      \(M_3 \gets kM_3\) with \(k = \frac{5}{3}\), so

      \[\begin{align*}
        M
        & \gets
        \begin{pmatrix}
          1 & 2 & 1 & 1 \\
          0 & 1 & -\frac{1}{5} & \frac{3}{5}
          \\
          \frac{5}{3} \cdot 0
          & \frac{5}{3} \cdot 0
          & \frac{5}{3} \cdot \frac{3}{5}
          & \frac{5}{3} \cdot \frac{6}{5}
        \end{pmatrix}
        \\[2ex]
        & =
        \begin{pmatrix}
          1 & 2 & 1 & 1 \\
          0 & 1 & -\frac{1}{5} & \frac{3}{5} \\
          0 & 0 & 1 & 2
        \end{pmatrix}.
      \end{align*}
      \]

   2. Replace the rows below the selected row.

      Nothing to do.

Phase 2.

4. Is the last column is a pivot column?

   The system is consistent.

5. Enumerating rows, bottom to top:

   For \(M_3\):

   1. Replace the rows above.

      \(M_2 \gets M_2 + kM_3\) using \(k = \frac{1}{5}\), so

      \[\begin{align*}
        M
        & \gets
        \begin{pmatrix}
          1 & 2 & 1 & 1
          \\
          0 + \frac{1}{5} \cdot 0
          & 1 + \frac{1}{5} \cdot 0
          & -\frac{1}{5} + \frac{1}{5} \cdot 1
          & \frac{3}{5} + \frac{1}{5} \cdot 2
          \\
          0 & 0 & 1 & 2
        \end{pmatrix}
        \\[2ex]
        & =
        \begin{pmatrix}
          1 & 2 & 1 & 1 \\
          0 & 1 & 0 & 1 \\
          0 & 0 & 1 & 2
        \end{pmatrix}.
      \end{align*}
      \]

      \(M_1 \gets M_1 + kM_3\) using \(k = -1\), so

      \[\begin{align*}
        M
        & \gets
        \begin{pmatrix}
          1 + (-1) \cdot 0
          & 2 + (-1) \cdot 0
          & 1 + (-1) \cdot 1
          & 1 + (-1) \cdot 2
          \\
          0 & 1 & 0 & 1 \\
          0 & 0 & 1 & 2
        \end{pmatrix}
        \\
        & =
        \begin{pmatrix}
          1 & 2 & 0 & -1 \\
          0 & 1 & 0 & 1 \\
          0 & 0 & 1 & 2
        \end{pmatrix}.
      \end{align*}
      \]

   For \(M_2\):

   1. Replace the rows above.

   \(M_1 \gets M_1 + kM_2\) using \(k = -2\), so

   \[\begin{align*}
     M
     & \gets
     \begin{pmatrix}
       1 + (-2) \cdot 0
       & 2 + (-2) \cdot 1
       & 0 + (-2) \cdot 0
       & -1 + (-2) \cdot 1
       \\
       0 & 1 & 0 & 1 \\
       0 & 0 & 1 & 2
     \end{pmatrix}
     \\
     & =
     \begin{pmatrix}
       1 & 0 & 0 & -3 \\
       0 & 1 & 0 & 1 \\
       0 & 0 & 1 & 2
     \end{pmatrix}.
   \end{align*}
   \]

   For \(M_1\):

   1. Replace the rows above.

      Nothing to do.

The solution is \((x, y, z) = (-3, 1, 2)\).