maths.free › Linear Algebra › 1. Systems of Linear Equations › Reduced Row-Echelon Form

Reduced Row-Echelon Form

After solving a few systems of equations, you will recognize that it does not matter so much what we call our variables, as opposed to what numbers act as their coefficients.

Reduced Row-Echelon Form

After solving a few systems of equations, you will recognize that it does not matter so much what we call our variables, as opposed to what numbers act as their coefficients. A system in the variables $x_1,\,x_2,\,x_3$ would behave the same if we changed the names of the variables to $a,\,b,\,c$ and kept all the constants the same and in the same places. In this section, we will isolate the key bits of information about a system of equations into something called a matrix, and then use this matrix to systematically solve the equations. Along the way we will obtain one of our most important and useful computational tools.

\begin{bmatrix} 1 & 5 & 0 & 6 & 8\\ 0 & 0 & 1 & 2 & 0\\ 0 & 0 & 0 & 0 & 1 \end{bmatrix}
\begin{bmatrix} 2 & 1 & 8\\ -1 & 1 & -1\\ -2 & 5 & 4 \end{bmatrix}
2x_1 + 3x_2 - x_3&= 0\\ x_1 + 2x_2 + x_3&= 3\\ x_1 + 3x_2 + 3x_3&= 7

For problems C10C19, find all solutions to the system of linear equations. Use your favorite computing device to row-reduce the augmented matrices for the systems, and write the solutions as a set, using correct set notation.

For problems C30C33, row-reduce the matrix without the aid of a calculator, indicating the row operations you are using at each step using the notation of .

Matrix and Vector Notation for Systems of Equations

Be careful with this notation for individual entries, since it is easy to think that $\matrixentry{A}{ij}$ refers to the whole matrix. It does not. It is just a number, but is a convenient way to talk about the individual entries simultaneously. This notation will get a heavy workout once we get to .

Example: A matrix

B=\begin{bmatrix} -1&2&5&3\\ 1&0&-6&1\\ -4&2&2&-2 \end{bmatrix} is a matrix with $m=3$ rows and $n=4$ columns. We can say that $\matrixentry{B}{2,3}=-6$ while $\matrixentry{B}{3,4}=-2$.

When we do equation operations on system of equations, the names of the variables really are not very important. Use $x_1$, $x_2$, $x_3$, or $a$, $b$, $c$, or $x$, $y$, $z$, it really does not matter. In this subsection we will describe some notation that will make it easier to describe linear systems, solve the systems and describe the solution sets. Here is a list of definitions, laden with notation.

Definition: Column Vector

A column vector of size $m$ is an ordered list of $m$ numbers, which is written in order vertically, starting at the top and proceeding to the bottom. At times, we will refer to a column vector as simply a vector. Column vectors will be written in bold, usually with lower case Latin letter from the end of the alphabet such as $\vect{u}$, $\vect{v}$, $\vect{w}$, $\vect{x}$, $\vect{y}$, $\vect{z}$. Some books like to write vectors with arrows, such as $\vec{u}$. Writing by hand, some like to put arrows on top of the symbol, or a tilde underneath the symbol, as in $\underset{\sim}{\textstyle u}$. To refer to the entry or component of vector $\vect{v}$ in location $i$ of the list, we write $\vectorentry{\vect{v}}{i}$.

Column Vector $\vect{v}$ Column Vector Entries $\vectorentry{\vect{v}}{i}$

Be careful with this notation. While the symbols $\vectorentry{\vect{v}}{i}$ might look somewhat substantial, as an object this represents just one entry of a vector, which is just a single complex number.

Condensed — the full section is in Beezer, A First Course in Linear Algebra.

Row Operations

An augmented matrix for a system of equations will save us the tedium of continually writing down the names of the variables as we solve the system. It will also release us from any dependence on the actual names of the variables. We have seen how certain operations we can perform on equations () will preserve their solutions (). The next two definitions and the following theorem carry over these ideas to augmented matrices.

Definition: Row Operations

The following three operations will transform an $m\times n$ matrix into a different matrix of the same size, and each is known as a row operation.

Swap the locations of two rows.
Multiply each entry of a single row by a nonzero quantity.
Multiply each entry of one row by some quantity, and add these values to the entries in the same columns of a second row. Leave the first row the same after this operation, but replace the second row by the new values.

We will use a symbolic shorthand to describe these row operations:

$\rowopswap{i}{j}$: Swap the location of rows $i$ and $j$.
$\rowopmult{\alpha}{i}$: Multiply row $i$ by the nonzero scalar $\alpha$.
$\rowopadd{\alpha}{i}{j}$: Multiply row $i$ by the scalar $\alpha$ and add to row $j$.

Row Operation, Swap $\rowopswap{i}{j}$ Row Operation, Multiply $\rowopmult{\alpha}{i}$ Row Operation, Add $\rowopadd{\alpha}{i}{j}$

Example: Two row-equivalent matrices

The matrices A=\begin{bmatrix} 2&-1&3&4\\ 5&2&-2&3\\ 1&1&0&6 \end{bmatrix} && B=\begin{bmatrix} 1&1&0&6\\ 3&0&-2&-9\\ 2&-1&3&4 \end{bmatrix} are row-equivalent as can be seen from \begin{bmatrix} 2&-1&3&4\\ 5&2&-2&3\\ 1&1&0&6 \end{bmatrix} \xrightarrow{\rowopswap{1}{3}} \begin{bmatrix} 1&1&0&6\\ 5&2&-2&3\\ 2&-1&3&4 \end{bmatrix} & \xrightarrow{\rowopadd{-2}{1}{2}} \begin{bmatrix} 1&1&0&6\\ 3&0&-2&-9\\ 2&-1&3&4 \end{bmatrix} We can also say that any pair of these three matrices are row-equivalent.

Notice that each of the three row operations is reversible (), so we do not have to be careful about the distinction between $A$ is row-equivalent to $B$ and $B$ is row-equivalent to $A$. ()

The preceding definitions are designed to make the following theorem possible. It says that row-equivalent matrices represent systems of linear equations that have identical solution sets.

Condensed — the full section is in Beezer, A First Course in Linear Algebra.

Reduced Row-Echelon Form

The preceding example amply illustrates the definitions and theorems we have seen so far. But it still leaves two questions unanswered. Exactly what is this simpler form for a matrix, and just how do we get it? Here is the answer to the first question, a definition of reduced row-echelon form.

Definition: Reduced Row-Echelon Form

A matrix is in reduced row-echelon form if it meets all of the following conditions:

If there is a row where every entry is zero, then this row lies below any other row that contains a nonzero entry.
The leftmost nonzero entry of a row is equal to 1.
The leftmost nonzero entry of a row is the only nonzero entry in its column.
Consider any two different leftmost nonzero entries, one located in row $i$, column $j$ and the other located in row $s$, column $t$. If $s>i$, then $t>j$.

A row of only zero entries is called a zero row and the leftmost nonzero entry of a nonzero row is a leading 1. A column containing a leading 1 will be called a pivot column. The number of nonzero rows will be denoted by $r$, which is also equal to the number of leading 1's and the number of pivot columns.

The set of column indices for the pivot columns will be denoted by $D=\set{d_1,\,d_2,\,d_3,\,\ldots,\,d_r}$ where $d_1\lt d_2\lt d_3\lt\cdots\lt d_r$, while the columns that are not pivot columns will be denoted as $F=\set{f_1,\,f_2,\,f_3,\,\ldots,\,f_{n-r}}$ where $f_1\lt f_2\lt f_3\lt\cdots\lt f_{n-r}$.

Reduced Row-Echelon Form Analysis $r$, $D$, $F$

The principal feature of reduced row-echelon form is the pattern of leading 1's guaranteed by conditions (2) and (4), reminiscent of a flight of geese, or steps in a staircase, or water cascading down a mountain stream.

There are a number of new terms and notation introduced in this definition, which should make you suspect that this is an important definition. Given all there is to digest here, we will mostly save the use of $D$ and $F$ until . However, one important point to make here is that all of these terms and notation apply to a matrix. Sometimes we will employ these terms and sets for an augmented matrix, and other times it might be a coefficient matrix. So always give some thought to exactly which type of matrix you are analyzing.

Example: A matrix in reduced row-echelon form

The matrix $C$ is in reduced row-echelon form. C&= \begin{bmatrix} 1&-3&0&6&0&0&-5&9\\ 0&0&0&0&1&0&3&-7\\ 0&0&0&0&0&1&7&3\\ 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0 \end{bmatrix} This matrix has two zero rows and three pivot columns. So $r=3$. Columns 1, 5, and 6 are the three pivot columns, so $D=\set{1,\,5,\,6}$ and then $F=\set{2,\,3,\,4,\,7,\,8}$.

Condensed — the full section is in Beezer, A First Course in Linear Algebra.

Symbols used here

A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}

matrix
A rectangular array of numbers; a linear map.

imaginary unit
i² = −1.

\mathbf{v},\ \vec{v}

vector
A quantity with magnitude and direction; a column of numbers.

\det A,\ |A|

determinant
Scaling factor of area/volume under A; zero means singular.

A^{-1},\ A^{T}

inverse, transpose
The matrix that undoes A; A with rows and columns swapped.

\lambda

lambda (eigenvalue)
The factor by which an eigenvector is stretched: Av = λv.

\mathbf{u} \cdot \mathbf{v},\ \|\mathbf{v}\|

dot product, norm
Σ u_i v_i; the length of v, √(v·v).

Questions people ask

What does a determinant mean geometrically?

It is the factor by which the matrix scales area (2×2) or volume (3×3), with a negative sign if orientation flips. Zero means the matrix flattens space and cannot be undone.

What is an eigenvector?

A direction the matrix does not turn — it only stretches it by the eigenvalue. Along eigenvectors a complicated matrix acts like multiplication by a number.

Why is matrix multiplication not commutative?

Because a matrix is a transformation and AB means "do B, then A". Rotating then reflecting is not the same as reflecting then rotating.

Prova själv

Parts of this page are adapted from Beezer, A First Course in Linear Algebra (GFDL 1.2). Condensed and re-explained here; errors are ours.

Mer information Linear Algebra

Determinants Matrix inverse Eigenvalues and eigenvectors Matrix multiplication Row reduction Vector spaces, span and linear independence Orthogonality, projections and least squares Diagonalisation and matrix powers Linear transformations and change of basis