Linear Algebra

Reduced row echelon form

Row reduction can be steered many ways and works on a matrix of any shape. Does every route end at the same matrix, and what does that final matrix say about the columns we started with?

You need

Echelon forms and Gaussian eliminationPrecalculus

Unlocks

Finding an inverse by row reducing A next to ILinear Algebra RankLinear Algebra

Where you are 7 in Row reduction

Linear algebra6

Row reduction7

Augmented matrices and row operations Echelon forms and Gaussian elimination

Reduced row echelon form

Solving a system by row reduction: one, none or infinitely many solutions Homogeneous systems and solutions in parametric vector form ▾ Show all 7 (2 more)

Why this exists

Echelon forms solved square systems with one solution, and the reduced form appeared there as the shape the solution is read from. Two things were left open: most matrices in linear algebra are not square, and the claim that every route of row operations ends at the same reduced form was stated, not proved.

One fact settles both. Row operations change every column of a matrix but keep every linear combination that ties the columns together, and the reduced form writes those ties down in the plainest way, so it belongs to the matrix. Day 1 reduces matrices of any shape and proves the reduced form unique. Day 2 reads it: consistency, uniqueness, redundant vectors, and several systems at once.

Definition

Recall from Echelon forms and Gaussian elimination: a matrix is in reduced row echelon form when it is in echelon form, every leading entry is 1, and each leading 1 is the only nonzero entry in its column. Two matrices are row equivalent, A \sim B, when row operations turn one into the other; every row operation can be undone (Augmented matrices and row operations), so this runs both ways.

Gauss-Jordan elimination on an m \times n matrix. Keep a current row, starting at row 1, and visit the columns from left to right. If a column is 0 in the current row and every row below, it gets no pivot and the current row stays put. Otherwise swap a row with a nonzero entry there into the current row, scale that entry to 1, clear every other entry of the column, above and below, with replacements R_i + cR_j \to R_i, and move the current row down one. Stop when the rows or the columns run out. A finished column is never disturbed, since every row used later is 0 in all columns already visited, so the result is in reduced form.

The pivot positions of A are the positions of the leading 1s in its reduced form, and the pivot columns of A are the columns of A that contain them. The number of pivots is the rank. Write \mathbf{e}_k for the column with 1 in entry k and 0 elsewhere.

Intuition

Compare the matrix A of Example 1 with its reduced form R. Column 1 was (1, 2, -1) and is now \mathbf{e}_1, yet column 2 is twice column 1 in both, and column 4 is 2 times column 3 minus column 1 in both. Row operations change what the columns are, not how they are built from one another.

In the reduced form those recipes are in plain sight. The pivot columns are \mathbf{e}_1, \mathbf{e}_2, \dots in order, and every other column lists its own recipe: its entries are the coefficients on the pivot columns to its left.

Results

Column relations survive. If A \sim R, with columns \mathbf{a}_1, \dots, \mathbf{a}_n and \mathbf{r}_1, \dots, \mathbf{r}_n, then c_1\mathbf{a}_1 + \dots + c_n\mathbf{a}_n = \mathbf{0} exactly when c_1\mathbf{r}_1 + \dots + c_n\mathbf{r}_n = \mathbf{0}.

Pivot columns are the columns not built from earlier ones. Column j of A is a pivot column exactly when it is not a combination of columns 1 to j - 1, where a zero column counts as a combination of none. Otherwise, with pivot columns p_1 < \dots < p_k to its left,

\mathbf{a}_j = r_{1j}\,\mathbf{a}_{p_1} + \dots + r_{kj}\,\mathbf{a}_{p_k},

with the top entries of column j of the reduced form as coefficients. The pivot columns of A are linearly independent and span what all the columns span.

Uniqueness. Every matrix is row equivalent to exactly one matrix in reduced form. So A \sim B exactly when they have the same reduced form, and any echelon form of A has its leading entries at the pivot positions of A.

Reading \left[\begin{array}{c|c} A & \mathbf{b} \end{array}\right] (Day 2). The system is consistent exactly when the last column is not a pivot column, that is, when \mathbf{b} is a combination of the columns of A; otherwise the reduced form has a row \left[\begin{array}{ccc|c} 0 & \cdots & 0 & 1 \end{array}\right]. It has exactly one solution when, in addition, every column of A is a pivot column; with a non-pivot column it has infinitely many, the subject of Solving a system by row reduction: one, none or infinitely many solutions.

Several right-hand sides. The first n columns of the reduced form of \left[\begin{array}{c|ccc} A & \mathbf{b}_1 & \cdots & \mathbf{b}_k \end{array}\right] are the reduced form of A. So one reduction through the columns of A settles all k systems; the one for \mathbf{b}_i is consistent exactly when its column ends in 0 in every zero row of the reduced A.

Why it is true

Relations survive. c_1\mathbf{a}_1 + \dots + c_n\mathbf{a}_n = \mathbf{0} says that (c_1, \dots, c_n) solves the system with augmented matrix \left[\begin{array}{c|c} A & \mathbf{0} \end{array}\right]. Row operations take it to \left[\begin{array}{c|c} R & \mathbf{0} \end{array}\right], keep the zero column, and keep the solutions.

In a reduced form the relations are visible. Let R have pivot columns p_1 < \dots < p_r, so column p_k is \mathbf{e}_k. A row is 0 left of its leading entry, so in a non-pivot column j only the rows whose pivots lie left of j, rows 1 to k, can be nonzero: \mathbf{r}_j = r_{1j}\mathbf{e}_1 + \dots + r_{kj}\mathbf{e}_k. And \mathbf{e}_k is not a combination of earlier columns, which are all 0 in row k.

Back to A. “Column j is a combination of earlier columns” is a relation with coefficient -1 on column j and 0 on later ones, so it holds in A exactly when it holds in R, with the same coefficients. A relation among the pivot columns of A alone would carry to one among \mathbf{e}_1, \dots, \mathbf{e}_r, forcing every coefficient to be 0; so they are independent, and every other column is a combination of them.

Uniqueness. Let R and S both be reduced forms of A. Their pivot columns are the columns of A not built from earlier ones, so they sit in the same places and hold \mathbf{e}_1, \dots, \mathbf{e}_r in both. In a non-pivot column j, \mathbf{a}_j = \sum r_{ij}\mathbf{a}_{p_i} = \sum s_{ij}\mathbf{a}_{p_i}, so \sum (r_{ij} - s_{ij})\mathbf{a}_{p_i} = \mathbf{0}, and independence gives r_{ij} = s_{ij}. So R = S. If A \sim B, the reduced form of B is reached from A through B; if they share one, go from A to it and undo the steps from B. An echelon form is finished by scaling rows and clearing above pivots with rows that are 0 left of their pivots, which never moves a leading entry.

Augmented matrices. The last column is a pivot column exactly when \mathbf{b} is not a combination of the columns, that is, when the system has no solution. Two solutions \mathbf{x}, \mathbf{y} give \sum (x_i - y_i)\mathbf{a}_i = \mathbf{0}, so independent columns allow only one. With a non-pivot column j, raising x_j by t and lowering each x_{p_i} by t\,r_{ij} changes A\mathbf{x} by t(\mathbf{a}_j - \sum r_{ij}\mathbf{a}_{p_i}) = \mathbf{0}, so every t gives a solution. The first n columns of a reduced matrix are still reduced, so by uniqueness those of the reduced \left[\begin{array}{c|c} A & B \end{array}\right] are the reduced form of A.

Worked examples

Example 1

Day 1: Gauss-Jordan on a wide matrix

Find the reduced row echelon form of

A = \begin{bmatrix} 1 & 2 & 0 & -1 & 3 \\ 2 & 4 & 1 & 0 & 5 \\ -1 & -2 & 2 & 5 & -5 \end{bmatrix}

and name its pivot positions and pivot columns.

Solution

Column 1: the top entry is already 1, the first pivot. R_2 - 2R_1 \to R_2 and R_3 + R_1 \to R_3 clear below it:

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

Column 2, current row 2: rows 2 and 3 hold 0, and row 1 is finished, so column 2 gets no pivot and the current row stays at 2.

Column 3: the entry in row 2 is 1, the second pivot. Row 1 already has 0 above it, and R_3 - 2R_2 \to R_3 clears below it:

R = \begin{bmatrix} 1 & 2 & 0 & -1 & 3 \\ 0 & 0 & 1 & 2 & -1 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix}

R is reduced. The pivot positions are row 1, column 1 and row 2, column 3, so the pivot columns are columns 1 and 3. Row 3 became R_3 + 5R_1 - 2R_2 = \mathbf{0}: row 3 of A is 2(\text{row } 2) - 5(\text{row } 1).

Example 2

Day 1: A tall matrix with a zero column

Find the reduced row echelon form and the pivot columns of

B = \begin{bmatrix} 0 & 2 & -4 \\ 0 & 1 & 1 \\ 0 & 3 & -3 \\ 0 & -1 & 5 \end{bmatrix}

Solution

Column 1 is all zeros, which no row operation changes, so it never gets a pivot. Column 2: the 1 in row 2 avoids fractions, so R_1 \leftrightarrow R_2, then R_2 - 2R_1 \to R_2, R_3 - 3R_1 \to R_3 and R_4 + R_1 \to R_4:

\begin{bmatrix} 0 & 1 & 1 \\ 0 & 0 & -6 \\ 0 & 0 & -6 \\ 0 & 0 & 6 \end{bmatrix}

Column 3: \displaystyle -\frac{1}{6}R_2 \to R_2 makes the pivot 1; R_3 + 6R_2 \to R_3, R_4 - 6R_2 \to R_4 and R_1 - R_2 \to R_1 clear the rest:

\begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}

The pivot columns are 2 and 3. A 4 \times 3 matrix has at most three pivots, so its reduced form always has a zero row.

Example 3

Day 1: Reading the column relations

Use R from Example 1 to write each non-pivot column of A as a combination of pivot columns, and check against A.

Solution

The pivot columns of R are \mathbf{r}_1 = \mathbf{e}_1 and \mathbf{r}_3 = \mathbf{e}_2, and the other columns read as recipes:

\begin{aligned} \mathbf{r}_2 &= 2\mathbf{r}_1 \\ \mathbf{r}_4 &= -\mathbf{r}_1 + 2\mathbf{r}_3 \\ \mathbf{r}_5 &= 3\mathbf{r}_1 - \mathbf{r}_3 \end{aligned}

Relations survive row operations, so the same coefficients hold for the columns of A, written as columns:

2\mathbf{a}_1 = (2, 4, -2) = \mathbf{a}_2;
-\mathbf{a}_1 + 2\mathbf{a}_3 is (-1, -2, 1) + (0, 2, 4), and (-1, 0, 5) = \mathbf{a}_4;
3\mathbf{a}_1 - \mathbf{a}_3 is (3, 6, -3) - (0, 1, 2), and (3, 5, -5) = \mathbf{a}_5.

So \mathbf{a}_1 and \mathbf{a}_3 are independent and span what all five columns span.

Example 4

Day 1: Testing row equivalence

Which of B and C is row equivalent to A?

A = \begin{bmatrix} 1 & 3 & 2 \\ 2 & 7 & 1 \end{bmatrix} \qquad B = \begin{bmatrix} 3 & 10 & 3 \\ 1 & 4 & -1 \end{bmatrix}

C = \begin{bmatrix} 1 & 3 & 2 \\ 1 & 4 & 0 \end{bmatrix}

Solution

Row equivalent means same reduced form, so reduce all three. For A, R_2 - 2R_1 \to R_2 and R_1 - 3R_2 \to R_1. For B, R_1 \leftrightarrow R_2, R_2 - 3R_1 \to R_2, \displaystyle -\frac{1}{2}R_2 \to R_2 and R_1 - 4R_2 \to R_1. For C, R_2 - R_1 \to R_2 and R_1 - 3R_2 \to R_1.

A, B \sim \begin{bmatrix} 1 & 0 & 11 \\ 0 & 1 & -3 \end{bmatrix}

C \sim \begin{bmatrix} 1 & 0 & 8 \\ 0 & 1 & -2 \end{bmatrix}

B is row equivalent to A and C is not. Indeed the rows of B are R_1 + R_2 and R_2 - R_1 from A; no route reaches C.

Example 5

Day 2: One coefficient matrix, two right-hand sides

Let A be the first four columns of the matrix in Example 1. Is each of \mathbf{b}_1 = (1, 3, 1) and \mathbf{b}_2 = (2, 3, 0) a combination x_1\mathbf{a}_1 + \dots + x_4\mathbf{a}_4? If so, find one.

Solution

Both are systems with coefficient matrix A, so reduce them together:

\left[\begin{array}{cccc|cc} 1 & 2 & 0 & -1 & 1 & 2 \\ 2 & 4 & 1 & 0 & 3 & 3 \\ -1 & -2 & 2 & 5 & 1 & 0 \end{array}\right]

The operations are chosen by the columns of A, so they are those of Example 1: R_2 - 2R_1 \to R_2, R_3 + R_1 \to R_3, R_3 - 2R_2 \to R_3. The right-hand columns are carried along:

\left[\begin{array}{cccc|cc} 1 & 2 & 0 & -1 & 1 & 2 \\ 0 & 0 & 1 & 2 & 1 & -1 \\ 0 & 0 & 0 & 0 & 0 & 4 \end{array}\right]

For \mathbf{b}_1 the zero row ends in 0, so the system is consistent. Its column reads \mathbf{e}_1 + \mathbf{e}_2 = \mathbf{r}_1 + \mathbf{r}_3, which carries back to \mathbf{b}_1 = \mathbf{a}_1 + \mathbf{a}_3, so (x_1, x_2, x_3, x_4) = (1, 0, 1, 0). Check: (1, 2, -1) + (0, 1, 2) = (1, 3, 1). Columns 2 and 4 have no pivot, so this is not the only solution: \mathbf{a}_2 = 2\mathbf{a}_1, so (-1, 1, 1, 0) works too.

For \mathbf{b}_2 the zero row ends in 4, the equation 0 = 4. Scaled, it is \left[\begin{array}{cccc|c} 0 & 0 & 0 & 0 & 1 \end{array}\right], a pivot in the last column, so \mathbf{b}_2 is not a combination of the columns of A.

Example 6

Day 2: Gift boxes at the cannery

Aune packs gift boxes at the cannery. A small box holds 1 tin of herring and 1 of salmon; a medium box 2 herring, 3 salmon and 1 mackerel; a large box 2 herring, 3 salmon and 2 mackerel. Inkeri’s stock sheet says Monday used 110 herring, 145 salmon and 45 mackerel tins, and Tuesday 100, 135 and 50. How many boxes of each size were packed each day?

Solution

Let s, m, l count small, medium and large boxes. Each column of the coefficient matrix is one box’s contents, and both days share it:

\left[\begin{array}{ccc|cc} 1 & 2 & 2 & 110 & 100 \\ 1 & 3 & 3 & 145 & 135 \\ 0 & 1 & 2 & 45 & 50 \end{array}\right]

R_2 - R_1 \to R_2 gives (0, 1, 1 \mid 35, 35), the second pivot row. Then R_1 - 2R_2 \to R_1 gives (1, 0, 0 \mid 40, 30) and R_3 - R_2 \to R_3 gives (0, 0, 1 \mid 10, 15). Clearing above the third pivot, R_2 - R_3 \to R_2 gives (0, 1, 0 \mid 25, 20).

\left[\begin{array}{ccc|cc} 1 & 0 & 0 & 40 & 30 \\ 0 & 1 & 0 & 25 & 20 \\ 0 & 0 & 1 & 10 & 15 \end{array}\right]

Every column of the coefficient matrix is a pivot column, so each day has exactly one solution. Monday: 40 small, 25 medium and 10 large boxes. Tuesday: 30, 20 and 15. Check Monday: 40 + 50 + 20 = 110, 40 + 75 + 30 = 145, 25 + 20 = 45.

Example 7

Day 2: Which vectors in a list are needed

Which of these vectors in \mathbb{R}^4 are combinations of the ones before them? Give a linearly independent list with the same span.

\mathbf{v}_1 = \begin{bmatrix} 1 \\ -1 \\ 2 \\ 0 \end{bmatrix}, \; \mathbf{v}_2 = \begin{bmatrix} -2 \\ 2 \\ -4 \\ 0 \end{bmatrix}, \; \mathbf{v}_3 = \begin{bmatrix} 0 \\ 1 \\ 1 \\ 3 \end{bmatrix},

\mathbf{v}_4 = \begin{bmatrix} 3 \\ -1 \\ 8 \\ 6 \end{bmatrix}, \; \mathbf{v}_5 = \begin{bmatrix} 1 \\ 0 \\ 1 \\ 1 \end{bmatrix}

Solution

Make them the columns of a 4 \times 5 matrix. R_2 + R_1 \to R_2 and R_3 - 2R_1 \to R_3 clear column 1, and column 2 is then 0 from row 2 down: no pivot. In column 3, R_3 - R_2 \to R_3 and R_4 - 3R_2 \to R_4 leave rows 3 and 4 as (0, 0, 0, 0, -2), so column 4 has no pivot either. Column 5: \displaystyle -\frac{1}{2}R_3 \to R_3, then R_4 + 2R_3 \to R_4, R_2 - R_3 \to R_2 and R_1 - R_3 \to R_1:

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

The pivot columns are 1, 3 and 5, and the others read \mathbf{v}_2 = -2\mathbf{v}_1 and \mathbf{v}_4 = 3\mathbf{v}_1 + 2\mathbf{v}_3. Check: 3\mathbf{v}_1 + 2\mathbf{v}_3 is (3, -3, 6, 0) + (0, 2, 2, 6), which is \mathbf{v}_4. So \mathbf{v}_1, \mathbf{v}_3, \mathbf{v}_5 is linearly independent and spans what all five span.

Boundaries

Relations survive, vectors do not. Row operations can change the span of the columns: every column of R in Example 1 ends in 0. The pivot columns that span are columns of A.
Order matters. Reordering the columns can change which are pivot columns.
One zero row, several readings. A zero row of the reduced A is read in each right-hand column separately; a nonzero entry rules out only that column’s system.
Exact arithmetic. A tiny decimal where 0 belongs can pass for a pivot.

Where this goes next

Counting pivots gives the rank. Reducing A beside the identity is how an inverse is found. Columns without pivots become the free variables of Solving a system by row reduction: one, none or infinitely many solutions, and Example 7 is the standard test for Linear independence. Networks and chemical equations follow in Linear systems in use: networks, chemical equations, fitting curves.

Exercises

Day 1: Gauss-Jordan on any shape

Find the reduced row echelon form and the pivot columns.

\begin{bmatrix} 1 & 3 & -2 & 4 \\ 2 & 6 & -3 & 5 \end{bmatrix}
\begin{bmatrix} 2 & 0 & 4 \\ 1 & 0 & 3 \\ 3 & 0 & 5 \end{bmatrix}
\begin{bmatrix} 0 & 2 & 4 & -2 \\ 1 & 1 & 3 & 0 \\ 2 & 3 & 8 & -1 \end{bmatrix}

Day 1: Column relations

For the matrix in Exercise 3, write each non-pivot column as a combination of the pivot columns, and check against the original columns.
A 2 \times 4 matrix A has reduced form \begin{bmatrix} 1 & -2 & 0 & 3 \\ 0 & 0 & 1 & 4 \end{bmatrix}, first column (1, 2) and third column (-1, 1). Find A.
A matrix with columns \mathbf{a}_1, \dots, \mathbf{a}_4 has reduced form \begin{bmatrix} 1 & 0 & 2 & 0 \\ 0 & 1 & -3 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}. Which columns are combinations of earlier ones, and how? Is \mathbf{a}_1, \mathbf{a}_2, \mathbf{a}_4 linearly independent?

Day 1: Row equivalence

Are \begin{bmatrix} 1 & -1 & 2 \\ 3 & -2 & 1 \end{bmatrix} and \begin{bmatrix} 2 & -1 & -1 \\ 1 & 0 & -3 \end{bmatrix} row equivalent?
Are \begin{bmatrix} 1 & 2 & 3 \\ 2 & 4 & 7 \end{bmatrix} and \begin{bmatrix} 1 & 2 & 3 \\ 1 & 3 & 7 \end{bmatrix} row equivalent?

Day 2: Consistent, and how many solutions

Reduce and decide whether the system is consistent and its solution unique; give it when it is.

x + 2y = 4, 3x + 5y = 7, 2x - y = -17
x_1 - x_2 + 2x_3 + x_4 = 1, 2x_1 - 2x_2 + 5x_3 = 4, 3x_1 - 3x_2 + 7x_3 + x_4 = 6
Is (4, 3, 5) a combination of \mathbf{u}_1 = (1, 0, -1), \mathbf{u}_2 = (2, 1, 0) and \mathbf{u}_3 = (0, 1, 3)? In how many ways?

Day 2: Several right-hand sides

With one reduction, solve both systems with coefficient matrix \begin{bmatrix} 1 & 2 \\ 3 & 7 \end{bmatrix} and right-hand sides (5, 18) and (4, 13).
With coefficient matrix \begin{bmatrix} 1 & 1 & 2 \\ 2 & 3 & 5 \\ 1 & 2 & 3 \end{bmatrix}, reduce once for the right-hand sides (3, 7, 4) and (1, 1, 1). Which system is consistent? Give one solution and say whether it is the only one.
Tuulikki fills two kinds of crates at the cannery: a K crate holds 4 tins of herring and 2 of salmon, an R crate 3 of herring and 4 of salmon. Three stock levels are to be used up exactly: 72 herring and 56 salmon, 50 and 50, and 30 and 25. With one reduction, find the crates for each. Which levels can be packed in whole crates?
For \mathbf{w}_1 = (1, 2, 1), \mathbf{w}_2 = (3, 6, 3), \mathbf{w}_3 = (1, 0, 1), \mathbf{w}_4 = (2, 2, 2), find which are combinations of earlier ones, and an independent list with the same span.

Reasoning

Explain why the leading entries of any echelon form of A sit at the pivot positions of A.
Explain why at least two columns of any 3 \times 5 matrix are combinations of earlier columns.
List every 2 \times 2 matrix in reduced row echelon form, and explain why the list is complete.
Every column of an m \times n matrix A is a pivot column. Show that n \le m and that the reduced form of A is the n \times n identity above m - n rows of zeros.
Refute with an example: “If A has more columns than rows, every system with coefficient matrix A is consistent.”
Show that if every column of a square matrix A is a pivot column, the system with augmented matrix \left[\begin{array}{c|c} A & \mathbf{b} \end{array}\right] has exactly one solution for every \mathbf{b}.

Answers

\begin{bmatrix} 1 & 3 & 0 & -2 \\ 0 & 0 & 1 & -3 \end{bmatrix}, pivot columns 1 and 3. R_2 - 2R_1 \to R_2, then R_1 + 2R_2 \to R_1.
\begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{bmatrix}, pivot columns 1 and 3. After R_1 \leftrightarrow R_2 and clearing column 1, column 2 is zero; the pivot in column 3 sits in row 2.
\begin{bmatrix} 1 & 0 & 1 & 1 \\ 0 & 1 & 2 & -1 \\ 0 & 0 & 0 & 0 \end{bmatrix}, pivot columns 1 and 2. Start with R_1 \leftrightarrow R_2; row 3 becomes zero.
\mathbf{a}_3 = \mathbf{a}_1 + 2\mathbf{a}_2 and \mathbf{a}_4 = \mathbf{a}_1 - \mathbf{a}_2. Check: (0, 1, 2) + 2(2, 1, 3) = (4, 3, 8) and (0, 1, 2) - (2, 1, 3) = (-2, 0, -1).
A = \begin{bmatrix} 1 & -2 & -1 & -1 \\ 2 & -4 & 1 & 10 \end{bmatrix}. Columns 1 and 3 are the pivot columns, so \mathbf{a}_2 = -2\mathbf{a}_1 and \mathbf{a}_4 = 3\mathbf{a}_1 + 4\mathbf{a}_3 = (3, 6) + (-4, 4).
Only \mathbf{a}_3: \mathbf{a}_3 = 2\mathbf{a}_1 - 3\mathbf{a}_2. Columns 1, 2 and 4 are pivot columns, so \mathbf{a}_1, \mathbf{a}_2, \mathbf{a}_4 is linearly independent.
Yes. Both reduce to \begin{bmatrix} 1 & 0 & -3 \\ 0 & 1 & -5 \end{bmatrix}: the first by R_2 - 3R_1 \to R_2, R_1 + R_2 \to R_1; the second by R_1 \leftrightarrow R_2, R_2 - 2R_1 \to R_2, -R_2 \to R_2.
No. They reduce to \begin{bmatrix} 1 & 2 & 0 \\ 0 & 0 & 1 \end{bmatrix} and \begin{bmatrix} 1 & 0 & -5 \\ 0 & 1 & 4 \end{bmatrix}. Even the pivot columns differ: column 2 of the first is twice column 1.
Consistent, unique: (-6, 5). The reduced rows are (1, 0 \mid -6), (0, 1 \mid 5) and a zero row ending in 0.
Inconsistent. R_2 - 2R_1 \to R_2 and R_3 - 3R_1 \to R_3 give (0, 0, 1, -2 \mid 2) and (0, 0, 1, -2 \mid 3); R_3 - R_2 \to R_3 gives (0, 0, 0, 0 \mid 1).
Yes, in exactly one way: (4, 3, 5) = 4\mathbf{u}_1 + 0\mathbf{u}_2 + 3\mathbf{u}_3. The augmented matrix reduces to the identity beside (4, 0, 3), every column a pivot column.
(-1, 3) and (2, 1). R_2 - 3R_1 \to R_2 gives (0, 1 \mid 3, 1); R_1 - 2R_2 \to R_1 gives (1, 0 \mid -1, 2).
The first is consistent and the second is not. The reduced rows are (1, 0, 1 \mid 2, 2), (0, 1, 1 \mid 1, -1), (0, 0, 0 \mid 0, 1). One solution of the first is (2, 1, 0), not the only one, since column 3 has no pivot.
12 K and 8 R; 5 K and 10 R; \displaystyle \frac{9}{2} K and 4 R. The reduced rows are \displaystyle (1, 0 \mid 12, 5, \frac{9}{2}) and (0, 1 \mid 8, 10, 4). Only the first two levels fit whole crates.
\mathbf{w}_2 = 3\mathbf{w}_1 and \mathbf{w}_4 = \mathbf{w}_1 + \mathbf{w}_3; keep \mathbf{w}_1, \mathbf{w}_3. The reduced form is \begin{bmatrix} 1 & 3 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix}.
Finishing an echelon form scales rows, which leaves each leading entry in place, and clears above each pivot with its own row, which is 0 left of the pivot. No leading entry moves, and by uniqueness the result is the reduced form of A.
Each row holds at most one pivot, so at most 3 of the 5 columns are pivot columns. The other 2 or more are combinations of earlier columns.
\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}, \begin{bmatrix} 1 & c \\ 0 & 0 \end{bmatrix} for any c, \begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix}, and the zero matrix. Two pivots fill the diagonal. One pivot sits in row 1, row 2 zero: in column 1 the other entry is free, in column 2 the entry before it is 0.
There are n pivots, each in its own row, so n \le m. The k-th pivot column is column k and equals \mathbf{e}_k, so the top n rows form the identity, and the other m - n rows hold no pivot and are zero.
A = \begin{bmatrix} 1 & 2 & 3 \\ 2 & 4 & 6 \end{bmatrix} with right-hand side (1, 0): R_2 - 2R_1 \to R_2 gives the row (0, 0, 0 \mid -2), so there is no solution.
By Exercise 19 with m = n, the reduced form of A is I. The first n columns of the reduced form of \left[\begin{array}{c|c} A & \mathbf{b} \end{array}\right] are the reduced form of A, so it is \left[\begin{array}{c|c} I & \mathbf{x} \end{array}\right]: no zero row, and each row names one variable. The one solution is \mathbf{x}.