2.1. Row Reduction

2.1 Row Reduction

Let’s start with an example. Suppose we want to solve the system of linear equations

\[2x+y+3z=1\\ x-y=1\\ 2x+z = 1\]

The first step is to write this in the form of a matrix.

\[\begin{bmatrix}2&1&3\\1&-1&0\\2&0&1\end{bmatrix}\begin{bmatrix}x\\y\\z\end{bmatrix} = \begin{bmatrix}1\\1\\1\end{bmatrix}\]

Let us write this as a single matrix:

\[\begin{bmatrix}2&1&3&1\\1&-1&0&1\\2&0&1&1\end{bmatrix}\]

We solve this using row operations.

\[\begin{bmatrix}2&1&3&1\\1&-1&0&1\\2&0&1&1\end{bmatrix} =\begin{bmatrix}1&0&0&1/3\\0&1&0&-2/3\\0&0&1&1/3\end{bmatrix}.\]

Definition 2.1.1 (Row operations). A row operation on a matrix is one of three operations:

  1. Multiplying a row by a nonzero number
  2. Adding a multiple of a row onto another row
  3. Exchanging two rows
Theorem 2.1.1. If the matrix $[A \vec b]$ representing a system of linear equations $A\vec x = \vec b$ can be turned into $[A’ \vec b’]$ by a sequence of row operations, then the set of solutions $A\vec x = \vec b$ and the set of solutions $A’ \vec x = \vec b’$ coincide.

Echelon form

A matrix is in echelon form if

  1. In every row, the first nonzero entry is 1, called a pivotal 1.
  2. The pivotal 1 of a lower row is always to the right of the pivotal 1 of a higher row
  3. In every column that contains a pivotal 1, all other entries are 0.
  4. Any rows consisting entirely of 0’s are at the bottom.

Theorem 2.1.7. Given any matrix $A$, there exists a matrix $\tilde A$ in echelon form that can be obtained from $A$ by row operations. 2. The matrix $\tilde A$ is unique.