Row Reduced Echelon Form is a matrix with pivots that have a value of 1 and each of the pivots have 0s above and below them
Examples of reduction:
Example 1
( 0 1 2 3 4 5 6 7 0 9 10 11 ) \left(
\begin{array}{ccc|c}
0 & 1 & 2 & 3 \\
4 & 5 & 6 & 7 \\
0 & 9 & 10 & 11
\end{array}
\right) \\ ⎝ ⎛ 0 4 0 1 5 9 2 6 10 3 7 11 ⎠ ⎞ ( 4 5 6 7 0 1 2 3 0 9 10 11 ) \left(
\begin{array}{ccc|c}
4 & 5 & 6 & 7 \\
0 & 1 & 2 & 3 \\
0 & 9 & 10 & 11
\end{array}
\right) \\ ⎝ ⎛ 4 0 0 5 1 9 6 2 10 7 3 11 ⎠ ⎞ ( 4 5 6 7 0 1 2 3 0 0 − 8 − 16 ) \left(
\begin{array}{ccc|c}
4 & 5 & 6 & 7 \\
0 & 1 & 2 & 3 \\
0 & 0 & -8 & -16
\end{array}
\right) \\ ⎝ ⎛ 4 0 0 5 1 0 6 2 − 8 7 3 − 16 ⎠ ⎞ ( 4 5 6 7 0 1 2 3 0 0 1 2 ) \left(
\begin{array}{ccc|c}
4 & 5 & 6 & 7 \\
0 & 1 & 2 & 3 \\
0 & 0 & 1 & 2
\end{array}
\right) \\ ⎝ ⎛ 4 0 0 5 1 0 6 2 1 7 3 2 ⎠ ⎞ ( 4 5 6 7 0 1 0 − 1 0 0 1 2 ) \left(
\begin{array}{ccc|c}
4 & 5 & 6 & 7 \\
0 & 1 & 0 & -1 \\
0 & 0 & 1 & 2
\end{array}
\right) \\ ⎝ ⎛ 4 0 0 5 1 0 6 0 1 7 − 1 2 ⎠ ⎞ Row Reduced Echelon Form:
( 1 0 0 0 0 1 0 − 1 0 0 1 2 ) \left(
\begin{array}{ccc|c}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & -1 \\
0 & 0 & 1 & 2
\end{array}
\right) \\ ⎝ ⎛ 1 0 0 0 1 0 0 0 1 0 − 1 2 ⎠ ⎞ Example 2
( 1 2 1 0 1 − 1 3 − 2 3 0 1 4 ) \left(
\begin{array}{ccc|c}
1 & 2 & 1 & 0 \\
1 & -1 & 3 & -2 \\
3 & 0 & 1 & 4
\end{array}
\right) \\ ⎝ ⎛ 1 1 3 2 − 1 0 1 3 1 0 − 2 4 ⎠ ⎞ As shown in the last lecture, this equals:
( 1 2 1 0 0 − 3 2 − 2 0 0 − 8 8 ) \left(
\begin{array}{ccc|c}
1 & 2 & 1 & 0 \\
0 & -3 & 2 & -2 \\
0 & 0 & -8 & 8
\end{array}
\right) \\ ⎝ ⎛ 1 0 0 2 − 3 0 1 2 − 8 0 − 2 8 ⎠ ⎞ ( 1 2 1 0 0 − 3 2 − 2 0 0 1 − 1 ) \left(
\begin{array}{ccc|c}
1 & 2 & 1 & 0 \\
0 & -3 & 2 & -2 \\
0 & 0 & 1 & -1
\end{array}
\right) \\ ⎝ ⎛ 1 0 0 2 − 3 0 1 2 1 0 − 2 − 1 ⎠ ⎞ ( 1 2 1 0 0 − 3 0 0 0 0 1 − 1 ) → ( 1 2 1 0 0 1 0 0 0 0 1 − 1 ) \left(
\begin{array}{ccc|c}
1 & 2 & 1 & 0 \\
0 & -3 & 0 & 0 \\
0 & 0 & 1 & -1
\end{array}
\right) \rightarrow
\left(
\begin{array}{ccc|c}
1 & 2 & 1 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & -1
\end{array}
\right) ⎝ ⎛ 1 0 0 2 − 3 0 1 0 1 0 0 − 1 ⎠ ⎞ → ⎝ ⎛ 1 0 0 2 1 0 1 0 1 0 0 − 1 ⎠ ⎞ Row Reduced Echelon Form:
( 1 0 0 1 0 1 0 0 0 0 1 − 1 ) \left(
\begin{array}{ccc|c}
1 & 0 & 0 & 1 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & -1
\end{array}
\right) ⎝ ⎛ 1 0 0 0 1 0 0 0 1 1 0 − 1 ⎠ ⎞ Example 3 (Infinitely Many Solutions)
System = { x + 3 y + z + w = 1 − 4 x − 9 y + 2 z − w = − 1 − 3 y − 6 z − 3 w = − 3 y + 2 z + w = 1 \text{System} =
\begin{cases}
x + 3y + z + w = 1 \\
-4x - 9y + 2z - w = -1 \\
-3y - 6z - 3w = -3 \\
y + 2z + w = 1
\end{cases} System = ⎩ ⎨ ⎧ x + 3 y + z + w = 1 − 4 x − 9 y + 2 z − w = − 1 − 3 y − 6 z − 3 w = − 3 y + 2 z + w = 1 ( 1 3 1 1 1 − 4 − 9 2 − 1 − 1 0 − 3 − 6 − 3 − 3 0 1 2 1 1 ) \left(
\begin{array}{cccc|c}
1 & 3 & 1 & 1 & 1 \\
-4 & -9 & 2 & -1 & -1 \\
0 & -3 & -6 & -3 & -3 \\
0 & 1 & 2 & 1 & 1
\end{array}
\right) ⎝ ⎛ 1 − 4 0 0 3 − 9 − 3 1 1 2 − 6 2 1 − 1 − 3 1 1 − 1 − 3 1 ⎠ ⎞ ( 1 3 1 1 1 − 4 − 9 2 − 1 − 1 0 1 2 1 1 0 1 2 1 1 ) \left(
\begin{array}{cccc|c}
1 & 3 & 1 & 1 & 1 \\
-4 & -9 & 2 & -1 & -1 \\
0 & 1 & 2 & 1 & 1 \\
0 & 1 & 2 & 1 & 1
\end{array}
\right) ⎝ ⎛ 1 − 4 0 0 3 − 9 1 1 1 2 2 2 1 − 1 1 1 1 − 1 1 1 ⎠ ⎞ ( 1 3 1 1 1 − 4 − 9 2 − 1 − 1 0 1 2 1 1 0 0 0 0 0 ) \left(
\begin{array}{cccc|c}
1 & 3 & 1 & 1 & 1 \\
-4 & -9 & 2 & -1 & -1 \\
0 & 1 & 2 & 1 & 1 \\
0 & 0 & 0 & 0 & 0
\end{array}
\right) ⎝ ⎛ 1 − 4 0 0 3 − 9 1 0 1 2 2 0 1 − 1 1 0 1 − 1 1 0 ⎠ ⎞ ( 1 3 1 1 1 0 3 6 3 3 0 1 2 1 1 0 0 0 0 0 ) → ( 1 3 1 1 1 0 1 2 1 1 0 1 2 1 1 0 0 0 0 0 ) \left(
\begin{array}{cccc|c}
1 & 3 & 1 & 1 & 1 \\
0 & 3 & 6 & 3 & 3 \\
0 & 1 & 2 & 1 & 1 \\
0 & 0 & 0 & 0 & 0
\end{array}
\right) \rightarrow
\left(
\begin{array}{cccc|c}
1 & 3 & 1 & 1 & 1 \\
0 & 1 & 2 & 1 & 1 \\
0 & 1 & 2 & 1 & 1 \\
0 & 0 & 0 & 0 & 0
\end{array}
\right) ⎝ ⎛ 1 0 0 0 3 3 1 0 1 6 2 0 1 3 1 0 1 3 1 0 ⎠ ⎞ → ⎝ ⎛ 1 0 0 0 3 1 1 0 1 2 2 0 1 1 1 0 1 1 1 0 ⎠ ⎞ ( 1 3 1 1 1 0 1 2 1 1 0 0 0 0 0 0 0 0 0 0 ) \left(
\begin{array}{cccc|c}
1 & 3 & 1 & 1 & 1 \\
0 & 1 & 2 & 1 & 1 \\
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0
\end{array}
\right) ⎝ ⎛ 1 0 0 0 3 1 0 0 1 2 0 0 1 1 0 0 1 1 0 0 ⎠ ⎞ To get this into reduced row echelon form, we must get rid of some more of the coefficients.
( 1 0 − 5 − 2 − 2 0 1 2 1 1 0 0 0 0 0 0 0 0 0 0 ) \left(
\begin{array}{cccc|c}
1 & 0 & -5 & -2 & -2 \\
0 & 1 & 2 & 1 & 1 \\
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0
\end{array}
\right) ⎝ ⎛ 1 0 0 0 0 1 0 0 − 5 2 0 0 − 2 1 0 0 − 2 1 0 0 ⎠ ⎞ New System = { x + − 5 z − 2 w = − 2 y + 2 z + w = 1 0 = 0 0 = 0 \text{New System} =
\begin{cases}
x + - 5z - 2w = -2 \\
y + 2z + w = 1 \\
0 = 0 \\
0 = 0
\end{cases} New System = ⎩ ⎨ ⎧ x + − 5 z − 2 w = − 2 y + 2 z + w = 1 0 = 0 0 = 0 The last two equations show that z and w are free variables, and x and y can be expressed in terms of these free variables (so they are constrained variables).
x = 5 z + 2 w − 2 y = − 2 z − w + 1 x = 5z + 2w - 2 \\
y = -2z - w + 1 \\ x = 5 z + 2 w − 2 y = − 2 z − w + 1