3.5 Elementary row-operation matrices

Encode a row operation once

Elementary row operations first appeared as procedural moves on a matrix. We swapped rows, scaled a row by a nonzero number, and added a multiple of one row to another. On an augmented matrix, these moves are legitimate for solving a system only when the operation is applied to the entire affected row, including the entry to the right of the augmentation bar. Under that condition the operation rewrites whole equations reversibly and therefore preserves the solution set.

There is a second, more structural way to read the same moves: each elementary row operation is the same as left-multiplication by a special square matrix. This matters because it converts a sequence of elementary row operations into an ordinary matrix equation. Later, this is exactly the bridge between row reduction, invertibility, rank, determinants, and basis arguments.

The structural viewpoint also answers a practical question. If the same row operation must be performed on many columns at once, how can one encode the operation once rather than repeat it entry by entry? The identity matrix gives the encoding: its rows record exactly which old rows are used to build each new row. Matrix multiplication then applies that recipe simultaneously to every column of a compatible matrix.

Build the elementary matrix from the identity

Suppose an elementary row operation $\rho$ is meant to act on matrices with $p$ rows. Start with the identity matrix $I_p$, apply the same elementary row operation to $I_p$, and call the result $E_\rho$. All scalars are taken from the underlying field of the matrices; in particular, every nonzero scaling factor $c$ has a reciprocal $1/c$ in that field.

Definition 3.5.1

(Elementary row-operation matrix)

The elementary row-operation matrix associated with an elementary row operation $\rho$ on $p$-row matrices is the $p \times p$ matrix obtained by applying $\rho$ to $I_p$.

This matrix is also called an elementary matrix. The longer name keeps its connection with the specified row operation visible.

Equivalently,

$$E_\rho = \rho(I_p).$$

The reason this definition is useful is the following theorem.

Theorem 3.5.2

(Elementary row operations are left multiplication)

Let $A$ be any matrix with $p$ rows. If $\rho$ is one elementary row operation and $\rho(A)$ denotes the result of applying it to $A$, then

$$\rho(A) = E_\rho A.$$

So applying that elementary row operation to $A$ is the same as multiplying $A$ on the left by the elementary row-operation matrix obtained from the same operation on $I_p$.

The multiplication must be on the left. Row operations change rows by mixing rows. Left multiplication forms new rows of $A$ as linear combinations of old rows of $A$. Right multiplication would instead mix columns.

The dimensions make the same point. If $A$ is $p \times n$, then $E_\rho$ is $p \times p$, so $E_\rho A$ is defined and remains $p \times n$. There is no assumption that $A$ is square. By contrast, a column-operation matrix acting on these same $n$ columns would have size $n \times n$ and multiply on the right.

Why left multiplication performs the operation

Proof

(Verify the three elementary cases row by row)

Write the rows of an arbitrary $p \times n$ matrix $A$ as $a_1,a_2,\ldots,a_p$, and let $e_k^{\mathsf T}$ denote row $k$ of $I_p$. The basic identity

$$e_k^{\mathsf T}A=a_k$$

says that a row of a left multiplier selects the corresponding row of $A$. Now check the three elementary operations.

1. For $R_i\leftrightarrow R_j$, the matrix $E_\rho$ has row $i$ equal to $e_j^{\mathsf T}$, row $j$ equal to $e_i^{\mathsf T}$, and every other row $k$ equal to $e_k^{\mathsf T}$. Thus the rows of $E_\rho A$ are the rows of $A$ with precisely rows $i$ and $j$ exchanged.

2. For $R_i\leftarrow cR_i$, where $c\ne0$, row $i$ of $E_\rho$ is $c e_i^{\mathsf T}$ and all other rows are unchanged. Hence row $i$ of the product is

   $$(c e_i^{\mathsf T})A=c a_i,$$

   while row $k$ remains $a_k$ for $k\ne i$.

3. For $R_j\leftarrow R_j+cR_i$, where $i\ne j$, row $j$ of $E_\rho$ is $e_j^{\mathsf T}+c e_i^{\mathsf T}$ and every other row is unchanged. Therefore the new row $j$ is

   $$(e_j^{\mathsf T}+c e_i^{\mathsf T})A=a_j+c a_i,$$

   exactly as prescribed.

These cases exhaust the elementary row operations, so they prove $E_\rho A=\rho(A)$ for every compatible $A$. The proof does not claim that an arbitrary manipulation of rows has such an elementary matrix; $\rho$ must be one of the three operations just checked.

Acting on an augmented matrix

Suppose $Ax=b$ is represented by the augmented matrix $[A\mid b]$. An elementary row operation must act on the full augmented matrix, not separately on whichever entries happen to be convenient. The multiplication identity is

$$E_\rho[A\mid b]=[E_\rho A\mid E_\rho b].$$

Thus the coefficients and the right-hand side undergo the same combination of rows. A vector $x$ satisfies $Ax=b$ if and only if it satisfies $E_\rho Ax=E_\rho b$: the forward implication follows by multiplying the equation by $E_\rho$, and the reverse implication follows by applying the reverse elementary operation. This is the precise reason the solution set is preserved.

Changing only $A$ while leaving $b$ fixed, or changing only $b$, generally produces a different system. The augmentation bar is therefore a visual separator, not a boundary at which a row operation may stop.

Encode replacement, scaling, and interchange

The three elementary row operations give three corresponding types of elementary row-operation matrices.

Worked example 3.5.3

(Row addition)

For matrices with three rows, consider

$$\rho:\quad R_2 \leftarrow R_2 + 3R_1.$$

Apply this operation to $I_3$:

$$I_3 = \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix} \quad\longmapsto\quad E_\rho = \begin{bmatrix} 1 & 0 & 0\\ 3 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix}.$$

Therefore, for every matrix $A$ with three rows,

$$E_\rho A$$

is the matrix obtained from $A$ by the operation $R_2\leftarrow R_2+3R_1$.

Worked example 3.5.4

(Row scaling)

For

$$\rho:\quad R_3 \leftarrow -2R_3,$$

the elementary row-operation matrix is

$$E_\rho = \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & -2 \end{bmatrix}.$$

The nonzero condition in row scaling is visible here: if the scaling factor were $0$, the resulting matrix would have a zero row and could not be reversed.

Worked example 3.5.5

(Row swap)

For

$$\rho:\quad R_1 \leftrightarrow R_3,$$

we get

$$E_\rho = \begin{bmatrix} 0 & 0 & 1\\ 0 & 1 & 0\\ 1 & 0 & 0 \end{bmatrix}.$$

Multiplying by this matrix on the left swaps the first and third rows of any compatible matrix.

Trace elementary left multiplication

Applying a row operation to the identity records its coefficients. Multiplying by that matrix on the left then applies the same operation to every column.

Compare a row operation with its matrix product

Use the stepper to revisit a row-operation sequence. At each step, read the displayed move as left multiplication by the matching elementary matrix.

A sequence of elementary row operations becomes one matrix product

The real payoff is not just representing one elementary row operation. A whole sequence of elementary row operations becomes one product of elementary row-operation matrices.

Theorem 3.5.6

(A sequence of elementary row operations as a product)

Suppose

$$A_1 \xrightarrow{\rho_1} A_2 \xrightarrow{\rho_2} A_3 \xrightarrow{\rho_3} \cdots \xrightarrow{\rho_k} A_{k+1}.$$

Then

$$A_{k+1} = E_{\rho_k}E_{\rho_{k-1}}\cdots E_{\rho_2}E_{\rho_1}A_1.$$

Here every $\rho_j$ is an elementary row operation on matrices with the same number of rows. The product represents the whole sequence, although the product itself need not be a single elementary row-operation matrix.

The order in this formula is important. The first row operation appears closest to $A_1$, because it is applied first:

$$A_2 = E_{\rho_1}A_1, \qquad A_3 = E_{\rho_2}A_2 = E_{\rho_2}E_{\rho_1}A_1.$$

Worked example 3.5.7

(Two row operations combined)

Let

$$A = \begin{bmatrix} 1 & 0 & 1\\ 0 & 2 & 1\\ 1 & 0 & 0 \end{bmatrix}.$$

Apply

$$\rho_1:\ R_2 \leftarrow R_2 + R_1, \qquad \rho_2:\ R_1 \leftarrow R_1 + 2R_2.$$

The corresponding row-operation matrices are

$$E_{\rho_1} = \begin{bmatrix} 1 & 0 & 0\\ 1 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix}, \qquad E_{\rho_2} = \begin{bmatrix} 1 & 2 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix}.$$

After both operations, the result is

$$E_{\rho_2}E_{\rho_1}A = \begin{bmatrix} 3&2&0\\ 1&1&0\\ 0&0&1 \end{bmatrix} \begin{bmatrix} 1&0&1\\ 0&2&1\\ 1&0&0 \end{bmatrix} = \begin{bmatrix} 3&4&5\\ 1&2&2\\ 1&0&0 \end{bmatrix}.$$

Instead of multiplying $E_{\rho_2}E_{\rho_1}$ directly, you can also obtain this combined matrix by applying the same two elementary row operations to $I_3$ in the same order. The final numerical matrix also confirms that the second operation uses the already-updated row $2$.

Reading a longer row-operation product

A chain of elementary row operations involves three distinct objects:

• the matrices $A_1,A_2,\ldots,A_{k+1}$ being transformed;
• the elementary row-operation matrices $H_1,H_2,\ldots,H_k$;
• the single combined left multiplier $J=H_k\cdots H_2H_1$.

Here is a typical four-row example. Suppose

$$\begin{aligned} \rho_1 &: R_2 \leftarrow -\frac12 R_2,\\ \rho_2 &: R_1 \leftrightarrow R_2,\\ \rho_3 &: R_3 \leftarrow R_3-2R_1,\\ \rho_4 &: R_4 \leftarrow R_4-2R_3,\\ \rho_5 &: R_1 \leftarrow R_1-R_3,\\ \rho_6 &: R_1 \leftarrow R_1-R_2. \end{aligned}$$

If

$$A_1 \xrightarrow{\rho_1} A_2 \xrightarrow{\rho_2} A_3 \xrightarrow{\rho_3} A_4 \xrightarrow{\rho_4} A_5 \xrightarrow{\rho_5} A_6 \xrightarrow{\rho_6} A_7,$$

then

$$A_7 = H_6H_5H_4H_3H_2H_1A_1.$$

The corresponding row-operation matrices are

$$\begin{aligned} H_1&= \begin{bmatrix} 1&0&0&0\\ 0&-\frac12&0&0\\ 0&0&1&0\\ 0&0&0&1 \end{bmatrix}, & H_2&= \begin{bmatrix} 0&1&0&0\\ 1&0&0&0\\ 0&0&1&0\\ 0&0&0&1 \end{bmatrix},\\[0.8em] H_3&= \begin{bmatrix} 1&0&0&0\\ 0&1&0&0\\ -2&0&1&0\\ 0&0&0&1 \end{bmatrix}, & H_4&= \begin{bmatrix} 1&0&0&0\\ 0&1&0&0\\ 0&0&1&0\\ 0&0&-2&1 \end{bmatrix},\\[0.8em] H_5&= \begin{bmatrix} 1&0&-1&0\\ 0&1&0&0\\ 0&0&1&0\\ 0&0&0&1 \end{bmatrix}, & H_6&= \begin{bmatrix} 1&-1&0&0\\ 0&1&0&0\\ 0&0&1&0\\ 0&0&0&1 \end{bmatrix}. \end{aligned}$$

Their product is

$$J=H_6H_5H_4H_3H_2H_1= \begin{bmatrix} -1&-\frac32&-1&0\\ 1&0&0&0\\ 0&1&1&0\\ 0&-2&-2&1 \end{bmatrix}.$$

The efficient way to obtain $J$ is to apply the six operations to $I_4$, not to expand all six factors by hand. The matrix $J$ records the total effect of the chain on rows:

$$A_7=JA_1.$$

This equation is also a good check on the order. If the first operation were placed on the far left, the product would describe a different chain.

Quick check

(In the six-step chain above, suppose $K$ is the row-operation matrix product for the reverse chain from $A_7$ back to $A_1$. What equation should $J$ and $K$ satisfy?)

Think of $K$ as undoing the total effect of $J$.

Solution · Answer

The matrices $J$ and $K$ encode transformations of every four-row matrix, not just the displayed matrix $A_1$. For any four-row matrix $X$, applying the forward chain and then its reverse gives

$$K(JX)=X.$$

Taking $X=I_4$ yields $KJ=I_4$. In the other order, the reverse chain followed by the forward chain restores every four-row matrix $Y$, so $J(KY)=Y$; taking $Y=I_4$ yields $JK=I_4$. Therefore

$$KJ=I_4 \qquad JK=I_4.$$

Equivalently, $K=J^{-1}$.

Reverse row operations and inverses

Every elementary row operation has a reverse operation:

• the reverse of $R_j \leftarrow R_j + cR_i$ is $R_j \leftarrow R_j - cR_i$;
• the reverse of $R_i \leftarrow cR_i$, with $c \ne 0$, is $R_i \leftarrow (1/c)R_i$;
• the reverse of a row swap is the same row swap.

This gives a precise matrix statement.

Theorem 3.5.8

(Elementary row-operation matrices are invertible)

Every elementary row-operation matrix is invertible. Its inverse is the elementary row-operation matrix corresponding to the reverse elementary row operation.

Proof

(Why the reverse matrix is a two-sided inverse)

Let $E_\rho$ represent an elementary row operation $\rho$, and let $E_{\rho^{-1}}$ represent the reverse elementary operation. For every matrix $X$ with $p$ rows, applying $\rho$ and then reversing it restores $X$. By the left-multiplication theorem,

$$E_{\rho^{-1}}E_\rho X=X.$$

This statement holds for every such $X$; in particular, put $X=I_p$ to obtain $E_{\rho^{-1}}E_\rho=I_p$. Reversing first and then applying $\rho$ similarly gives $E_\rho E_{\rho^{-1}}=I_p$. Hence

$$E_\rho^{-1}=E_{\rho^{-1}}.$$

Concretely, a swap is its own inverse, scaling by $c\ne0$ is undone by scaling by $1/c$, and adding $c$ times row $i$ to row $j$ is undone by adding $-c$ times row $i$ to row $j$.

For example, if

$$E = \begin{bmatrix} 1 & 0 & 0\\ 3 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix}$$

performs $R_2 \leftarrow R_2 + 3R_1$, then

$$E^{-1} = \begin{bmatrix} 1 & 0 & 0\\ -3 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix}$$

performs $R_2 \leftarrow R_2 - 3R_1$.

This is the algebraic reason elementary row operations are reversible, and it explains why row reduction is so closely connected to invertible matrices.

Proof

(Undo the last operation first)

Let $E_1,\ldots,E_k$ encode a chronological chain on matrices with $p$ rows, so its combined multiplier is $J=E_k\cdots E_1$. Each inverse $E_j^{-1}$ represents the reverse of the corresponding elementary operation. To recover the input, the first move must undo $E_k$, because that was the last change made to the rows. The remaining reverse moves undo $E_{k-1},\ldots,E_1$ in that order. Consequently the reverse multiplier is

$$K=E_1^{-1}E_2^{-1}\cdots E_k^{-1}.$$

There are two orders to distinguish: the time order of the reverse operations starts with $E_k^{-1}$, while the written product places that first action nearest the matrix being restored. For three steps, associativity gives

$$KJ=E_1^{-1}E_2^{-1}(E_3^{-1}E_3)E_2E_1 =E_1^{-1}(E_2^{-1}E_2)E_1=I_p.$$

The other product $JK$ cancels adjacent inverse pairs starting with $E_1E_1^{-1}$ and also equals $I_p$. The same successive cancellation works for any finite chain. No factors have been commuted, and the argument does not require the matrix being transformed to be square.

Apply this reading to the earlier two-operation example. Its combined multiplier is $E_{\rho_2}E_{\rho_1}$, so its inverse is $E_{\rho_1}^{-1}E_{\rho_2}^{-1}$. Starting from the final matrix, first subtract twice the current second row from the first, recovering $[1\ 0\ 1]$ as the first row. Then subtract that recovered first row from the second, recovering $[0\ 2\ 1]$. Reversing the chain means restoring the intermediate states, which explains the order without a memorized rule.

Why this viewpoint matters later

If $B$ is row-equivalent to $A$, then there is a finite sequence of elementary row operations taking $A$ to $B$. Therefore there is a product of elementary row-operation matrices $E$ such that

$$B = EA.$$

Because each elementary row-operation matrix is invertible, the product $E$ is invertible. So row equivalence can be discussed either procedurally, by listing elementary row operations, or algebraically, by writing an equation with an invertible matrix on the left. The converse statement also needs care: an arbitrary invertible left multiplier need not itself describe one elementary step.

This is useful in several later arguments:

• a square matrix row-equivalent to $I_n$ is a product of elementary row-operation matrices;
• elementary row operations preserve homogeneous solution information because they amount to multiplying by invertible matrices;
• determinant rules for elementary row operations can be expressed through elementary matrices;
• rank and basis arguments can use row reduction without pretending the original columns themselves have not changed.

Common mistakes

Common mistake

(Do not multiply on the wrong side)

Elementary row operations are represented by left multiplication. Right multiplication would combine columns, not rows.

Common mistake

(Do not reverse the product order)

If $\rho_1$ is applied before $\rho_2$, then the combined matrix is $E_{\rho_2}E_{\rho_1}$, not $E_{\rho_1}E_{\rho_2}$.

Common mistake

(Do not use a zero row scaling)

The scaling operation requires a nonzero scalar. Scaling a row by $0$ cannot be reversed and does not produce an invertible elementary row-operation matrix.

Common mistake

(One restored matrix is not enough to prove an inverse)

From $KJA=A$ for one particular matrix $A$, one cannot in general conclude $KJ=I$: the columns of $A$ may not detect every possible input. Prove that the composed row transformations restore every compatible matrix, or simply apply them to $I_p$. That is why the argument for $KJ=JK=I_p$ above uses arbitrary $p$-row matrices before substituting the identity.

Read products in the order they act

An elementary row operation on $p$-row matrices is encoded by applying that operation to $I_p$. The resulting elementary matrix $E_\rho$ acts on every compatible matrix by left multiplication, and the identity $E_\rho A=\rho(A)$ follows by checking the output rows in the swap, nonzero scaling, and row-addition cases. On an augmented matrix, the operation must act across the whole row, including the right-hand side, so that the corresponding system keeps exactly the same solutions.

A sequence $\rho_1,\ldots,\rho_k$ is represented in application order by $E_{\rho_k}\cdots E_{\rho_1}$. Each factor is invertible because the reverse elementary operation supplies a two-sided inverse. Consequently a finite row reduction can be treated as one invertible left transformation, while the individual factors still record the precise elementary steps.

Quick checks

Quick check

(For matrices with three rows, what row operation is represented by $E = \begin{bmatrix} 1&0&0\\0&1&0\\5&0&1 \end{bmatrix}$?)

Ask which row of $I_3$ changed.

Solution · Answer

Only row $3$ changed: five times row $1$ was added to it. Therefore

$$R_3 \leftarrow R_3 + 5R_1.$$

Quick check

(What is the inverse row operation for $R_2 \leftarrow R_2 - 4R_1$?)

Undo the added multiple.

Solution · Answer

The inverse operation is

$$R_2 \leftarrow R_2 + 4R_1.$$

Exercises

Quick check

(Write the row-operation matrix for $R_1 \leftrightarrow R_2$ on matrices with three rows.)

Apply the swap to $I_3$.

Solution · Guided solution

Swapping the first two rows of $I_3$ gives

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

This is the matrix that swaps rows $1$ and $2$ when multiplied on the left.

Quick check

(Suppose $B$ is obtained from $A$ by first doing $R_2 \leftarrow R_2 + R_1$, then $R_3 \leftarrow 2R_3$. Write $B$ as a product involving $A$.)

Name the two row-operation matrices in the order they act.

Solution · Guided solution

Let $E_1$ be the row-operation matrix for $R_2 \leftarrow R_2 + R_1$, and let $E_2$ be the row-operation matrix for $R_3 \leftarrow 2R_3$. Since $E_1$ acts first and $E_2$ acts second,

$$B = E_2E_1A.$$

Quick check

(Let $\beta_1,\beta_2\ne 0$. Suppose $B$ is obtained from a five-row matrix $A$ by the chain $R_3\leftarrow R_3+\alpha_1R_1$, then $R_2\leftarrow\beta_1R_2$, then $R_1\leftrightarrow R_4$, then $R_3\leftarrow R_3+\alpha_2R_2$, then $R_1\leftarrow\beta_2R_1$. Write the single matrix $G$ such that $B=GA$.)

Apply the same operations to $I_5$, remembering that later operations use the current rows, not the original rows.

Solution · Guided solution

Applying the operations to $I_5$ gives

$$G= \begin{bmatrix} 0&0&0&\beta_2&0\\ 0&\beta_1&0&0&0\\ \alpha_1&\alpha_2\beta_1&1&0&0\\ 1&0&0&0&0\\ 0&0&0&0&1 \end{bmatrix}.$$

The entry $\alpha_2\beta_1$ is the main point. The operation $R_3\leftarrow R_3+\alpha_2R_2$ occurs after row $2$ has already been scaled to $\beta_1R_2$, so the contribution from the original row $2$ is $\alpha_2\beta_1R_2$.

Quick check

(For the matrix $G$ in the previous exercise, suppose $D=GC$. Write the matrix $H$ such that $C=HD$.)

Reverse the row operations in reverse order.

Solution · Guided solution

The inverse chain is

$$G \xrightarrow{R_1\leftarrow\frac1{\beta_2}R_1} \xrightarrow{R_3\leftarrow R_3-\alpha_2R_2} \xrightarrow{R_1\leftrightarrow R_4} \xrightarrow{R_2\leftarrow\frac1{\beta_1}R_2} \xrightarrow{R_3\leftarrow R_3-\alpha_1R_1} I_5.$$

Therefore

$$H= \begin{bmatrix} 0&0&0&1&0\\ 0&\frac1{\beta_1}&0&0&0\\ 0&-\alpha_2&1&-\alpha_1&0\\ \frac1{\beta_2}&0&0&0&0\\ 0&0&0&0&1 \end{bmatrix}.$$

This is $G^{-1}$, so $D=GC$ implies $C=HD$.

Related notes

This page builds on 2.2 Augmented matrices and row operations and 3.2 Matrix multiplication, identity matrices, and linear systems. Continue to 3.6 Block matrices for the final Chapter 3 note. It prepares the algebraic row-reduction viewpoint used in 5.1 Invertible matrices and 7.2 Row operations, products, and invertibility.

Supplementary exercises with complete solutions

Question 1

For each of (a)–(d), the following ordered row operations send $A$ to $B$. Give a chain from $B$ back to $A$ and one square matrix $H$ satisfying $B=HA$. Sizes are (a),(b): $3\times4$, (c): $3\times6$, (d): $4\times5$.

(a)

$$\begin{gathered}\text{1. }R_2\leftarrow R_2+(-1)R_1\\\text{2. }R_3\leftarrow R_3+(-2)R_1\\\text{3. }R_3\leftarrow R_3+(-2)R_2\\\text{4. }R_3\leftarrow (-1)R_3\\\text{5. }R_1\leftarrow R_1+(-2)R_2\\\text{6. }R_2\leftarrow R_2+(-1)R_3\end{gathered}$$

(b)

$$\begin{gathered}\text{1. }R_1\leftrightarrow R_2\\\text{2. }R_1\leftarrow (-1)R_1\\\text{3. }R_3\leftarrow R_3+(-2)R_1\\\text{4. }R_3\leftarrow R_3+(-3)R_2\\\text{5. }R_1\leftarrow R_1+(-2)R_2\end{gathered}$$

(c)

$$\begin{gathered}\text{1. }R_1\leftrightarrow R_2\\\text{2. }R_3\leftarrow R_3+(2)R_1\\\text{3. }R_3\leftarrow R_3+(-3)R_2\\\text{4. }R_1\leftarrow R_1+(-2)R_2\\\text{5. }R_1\leftarrow R_1+(2)R_3\\\text{6. }R_2\leftarrow R_2+(-2)R_3\end{gathered}$$

(d)

$$\begin{gathered}\text{1. }R_2\leftarrow R_2+(-1)R_1\\\text{2. }R_3\leftarrow R_3+(-3)R_1\\\text{3. }R_4\leftarrow R_4+(-1)R_1\\\text{4. }R_2\leftarrow (-1)R_2\\\text{5. }R_3\leftarrow R_3+(4)R_2\\\text{6. }R_4\leftarrow R_4+(3)R_2\\\text{7. }R_3\leftrightarrow R_4\\\text{8. }R_4\leftarrow R_4+(4)R_3\\\text{9. }R_1\leftarrow R_1+(-2)R_2\\\text{10. }R_1\leftarrow R_1+(-1)R_3\end{gathered}$$

Complete solution

Work over the real numbers. Row replacement always uses distinct source and target rows; scaling factors are nonzero. An operation acts on the entire row, including every augmented block. In a finite chain the first operation acts first, so the combined left multiplier lists elementary matrices in reverse order.

Apply each forward operation to $I_r$. The matrices $H_j$ below record every intermediate multiplier, so induction on the steps gives the current matrix $H_jA$. The last multiplier is the requested $H$. Undo the operations in reverse order, replacing a row addition by subtraction, a scaling by reciprocal scaling, and a swap by the same swap. Each inverse undoes its predecessor on every compatible matrix, so the displayed reverse chain really ends at $A$.

(a)

$$H_{0}=\begin{bmatrix}1 & 0 & 0\\0 & 1 & 0\\0 & 0 & 1\end{bmatrix}$$ $$H_{1}=\begin{bmatrix}1 & 0 & 0\\-1 & 1 & 0\\0 & 0 & 1\end{bmatrix}$$ $$H_{2}=\begin{bmatrix}1 & 0 & 0\\-1 & 1 & 0\\-2 & 0 & 1\end{bmatrix}$$ $$H_{3}=\begin{bmatrix}1 & 0 & 0\\-1 & 1 & 0\\0 & -2 & 1\end{bmatrix}$$ $$H_{4}=\begin{bmatrix}1 & 0 & 0\\-1 & 1 & 0\\0 & 2 & -1\end{bmatrix}$$ $$H_{5}=\begin{bmatrix}3 & -2 & 0\\-1 & 1 & 0\\0 & 2 & -1\end{bmatrix}$$ $$H_{6}=\begin{bmatrix}3 & -2 & 0\\-1 & -1 & 1\\0 & 2 & -1\end{bmatrix}$$

Reverse chain, in this order:

$$\begin{gathered}\text{1. }R_2\leftarrow R_2+(1)R_3\\\text{2. }R_1\leftarrow R_1+(2)R_2\\\text{3. }R_3\leftarrow (-1)R_3\\\text{4. }R_3\leftarrow R_3+(2)R_2\\\text{5. }R_3\leftarrow R_3+(2)R_1\\\text{6. }R_2\leftarrow R_2+(1)R_1\end{gathered}$$

(b)

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

Reverse chain, in this order:

$$\begin{gathered}\text{1. }R_1\leftarrow R_1+(2)R_2\\\text{2. }R_3\leftarrow R_3+(3)R_2\\\text{3. }R_3\leftarrow R_3+(2)R_1\\\text{4. }R_1\leftarrow (-1)R_1\\\text{5. }R_1\leftrightarrow R_2\end{gathered}$$

(c)

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

Reverse chain, in this order:

$$\begin{gathered}\text{1. }R_2\leftarrow R_2+(2)R_3\\\text{2. }R_1\leftarrow R_1+(-2)R_3\\\text{3. }R_1\leftarrow R_1+(2)R_2\\\text{4. }R_3\leftarrow R_3+(3)R_2\\\text{5. }R_3\leftarrow R_3+(-2)R_1\\\text{6. }R_1\leftrightarrow R_2\end{gathered}$$

(d)

$$H_{0}=\begin{bmatrix}1 & 0 & 0 & 0\\0 & 1 & 0 & 0\\0 & 0 & 1 & 0\\0 & 0 & 0 & 1\end{bmatrix}$$ $$H_{1}=\begin{bmatrix}1 & 0 & 0 & 0\\-1 & 1 & 0 & 0\\0 & 0 & 1 & 0\\0 & 0 & 0 & 1\end{bmatrix}$$ $$H_{2}=\begin{bmatrix}1 & 0 & 0 & 0\\-1 & 1 & 0 & 0\\-3 & 0 & 1 & 0\\0 & 0 & 0 & 1\end{bmatrix}$$ $$H_{3}=\begin{bmatrix}1 & 0 & 0 & 0\\-1 & 1 & 0 & 0\\-3 & 0 & 1 & 0\\-1 & 0 & 0 & 1\end{bmatrix}$$ $$H_{4}=\begin{bmatrix}1 & 0 & 0 & 0\\1 & -1 & 0 & 0\\-3 & 0 & 1 & 0\\-1 & 0 & 0 & 1\end{bmatrix}$$ $$H_{5}=\begin{bmatrix}1 & 0 & 0 & 0\\1 & -1 & 0 & 0\\1 & -4 & 1 & 0\\-1 & 0 & 0 & 1\end{bmatrix}$$ $$H_{6}=\begin{bmatrix}1 & 0 & 0 & 0\\1 & -1 & 0 & 0\\1 & -4 & 1 & 0\\2 & -3 & 0 & 1\end{bmatrix}$$ $$H_{7}=\begin{bmatrix}1 & 0 & 0 & 0\\1 & -1 & 0 & 0\\2 & -3 & 0 & 1\\1 & -4 & 1 & 0\end{bmatrix}$$ $$H_{8}=\begin{bmatrix}1 & 0 & 0 & 0\\1 & -1 & 0 & 0\\2 & -3 & 0 & 1\\9 & -16 & 1 & 4\end{bmatrix}$$ $$H_{9}=\begin{bmatrix}-1 & 2 & 0 & 0\\1 & -1 & 0 & 0\\2 & -3 & 0 & 1\\9 & -16 & 1 & 4\end{bmatrix}$$ $$H_{10}=\begin{bmatrix}-3 & 5 & 0 & -1\\1 & -1 & 0 & 0\\2 & -3 & 0 & 1\\9 & -16 & 1 & 4\end{bmatrix}$$

Reverse chain, in this order:

$$\begin{gathered}\text{1. }R_1\leftarrow R_1+(1)R_3\\\text{2. }R_1\leftarrow R_1+(2)R_2\\\text{3. }R_4\leftarrow R_4+(-4)R_3\\\text{4. }R_3\leftrightarrow R_4\\\text{5. }R_4\leftarrow R_4+(-3)R_2\\\text{6. }R_3\leftarrow R_3+(-4)R_2\\\text{7. }R_2\leftarrow (-1)R_2\\\text{8. }R_4\leftarrow R_4+(1)R_1\\\text{9. }R_3\leftarrow R_3+(3)R_1\\\text{10. }R_2\leftarrow R_2+(1)R_1\end{gathered}$$

Question 3

Let $A,A^\prime$ be $m\times p$ and $B$ be $p\times q$. Suppose $A^\prime=\rho(A)$. (a) The source asks to prove that $AB=\rho(A^\prime B)$ for (i) $R_k\leftarrow R_k+\alpha R_i$, $i\ne k$, (ii) $R_k\leftarrow\beta R_k$, $\beta\ne0$, and (iii) $R_i\leftrightarrow R_k$, directly from the definitions. (b) Prove by induction that row-equivalent $A,A^\prime$ yield row-equivalent $AB,A^\prime B$, under the same finite operation sequence.

Complete solution

Work over the real numbers. Row replacement always uses distinct source and target rows; scaling factors are nonzero. An operation acts on the entire row, including every augmented block. In a finite chain the first operation acts first, so the combined left multiplier lists elementary matrices in reverse order.

(a): the direction in (i) and (ii) is false as printed

For (i), take $A=(1,0)^T$, $B=[1]$, and $R_2\leftarrow R_2+R_1$. Then $A^\prime B=(1,1)^T$, and applying the same operation again gives $(1,2)^T\ne AB$. For (ii), take $A=B=[1]$ and $\beta=2$. Then $A^\prime B=[2]$ and $\rho(A^\prime B)=[4]\ne[1]$. Thus no proof of the printed universal statements exists. The correct direction is $A^\prime B=\rho(AB)$; equivalently $AB=\rho^{-1}(A^\prime B)$. For a swap, $\rho^{-1}=\rho$, so (iii) is true as printed.

To prove the forward identity entrywise, in the replacement case only output row $k$ changes:

$$(A^\prime B)_{kj}=\sum_{r=1}^{p}(a_{kr}+\alpha a_{ir})b_{rj}=(AB)_{kj}+\alpha(AB)_{ij}.$$

Every other output row agrees. Scaling gives $(A^\prime B)_{kj}=\beta(AB)_{kj}$ and leaves other rows fixed. Swapping rows $i,k$ of $A$ interchanges exactly rows $i,k$ of $AB$. This proves all three forward transport identities directly, and applying the inverse operation proves the reverse identities.

(b): induction on the length of the row-operation sequence

For length zero the matrices are identical and so are their products. Suppose the assertion holds for a sequence of length $n$. For a sequence of length $n+1$, let $A_n$ be the matrix after the first $n$ operations. The induction hypothesis sends $AB$ to $A_nB$ by those same operations. The forward identity proved entrywise in (a) sends $A_nB$ to $A^\prime B$ by the final operation. Thus all $n+1$ operations carry $AB$ to $A^\prime B$. Induction proves the assertion for every finite length. All products have size $m\times q$, so these are legal row operations on matrices of one fixed size.

Question 4

The $3\times5$ matrices follow $A_1\xrightarrow{R_3+2R_1}A_2\xrightarrow{R_2\leftrightarrow R_3}A_3\xrightarrow{3R_1}A_4$. (a)–(c) Give $J_1,J_2,J_3$ with $A_{j+1}=J_jA_j$. (d) Give $J$ with $A_4=JA_1$. (e) Give $J^\prime$ with $A_1=J^\prime A_4$.

Complete solution

Work over the real numbers. Row replacement always uses distinct source and target rows; scaling factors are nonzero. An operation acts on the entire row, including every augmented block. In a finite chain the first operation acts first, so the combined left multiplier lists elementary matrices in reverse order.

Each $J_j$ is obtained by doing its one specified operation to $I_3$. Thus substitution gives $A_4=J_3J_2J_1A_1$. Explicitly:

$$J_1=\begin{bmatrix}1 & 0 & 0\\0 & 1 & 0\\2 & 0 & 1\end{bmatrix}$$ $$J_2=\begin{bmatrix}1 & 0 & 0\\0 & 0 & 1\\0 & 1 & 0\end{bmatrix}$$ $$J_3=\begin{bmatrix}3 & 0 & 0\\0 & 1 & 0\\0 & 0 & 1\end{bmatrix}$$ $$J=J_3J_2J_1=\begin{bmatrix}3 & 0 & 0\\2 & 0 & 1\\0 & 1 & 0\end{bmatrix}$$ $$J^\prime=J^{-1}=\begin{bmatrix}\frac{1}{3} & 0 & 0\\0 & 0 & 1\\- \frac{2}{3} & 1 & 0\end{bmatrix}$$

The inverse acts by first scaling row 1 by $1/3$, then swapping rows 2 and 3, then replacing row 3 by row 3 minus twice row 1. Applying these to the displayed $J$ gives $I_3$, so $J^\prime J=JJ^\prime=I_3$ and the reverse equality follows for every $A_1$.

Question 5

The following six $4\times6$ matrices are consecutive stages $A,A^{(1)},\ldots,A^{(5)}=A^\prime$. (a) Identify all five row operations $\rho_1,\ldots,\rho_5$. (b) Give an explicit $4\times4$ matrix $H$ with $A^\prime=HA$.

$$A^{\mathrm{stage}}_{0}=\begin{bmatrix}2 & 1 & -1 & 4 & 3 & 8\\1 & 3 & 0 & 8 & -4 & -4\\0 & 1 & 1 & 4 & -3 & -4\\-1 & -2 & 3 & 0 & 0 & -1\end{bmatrix}$$ $$A^{\mathrm{stage}}_{1}=\begin{bmatrix}1 & 3 & 0 & 8 & -4 & -4\\2 & 1 & -1 & 4 & 3 & 8\\0 & 1 & 1 & 4 & -3 & -4\\-1 & -2 & 3 & 0 & 0 & -1\end{bmatrix}$$ $$A^{\mathrm{stage}}_{2}=\begin{bmatrix}1 & 3 & 0 & 8 & -4 & -4\\0 & -5 & -1 & -12 & 11 & 16\\0 & 1 & 1 & 4 & -3 & -4\\-1 & -2 & 3 & 0 & 0 & -1\end{bmatrix}$$ $$A^{\mathrm{stage}}_{3}=\begin{bmatrix}1 & 3 & 0 & 8 & -4 & -4\\0 & -5 & -1 & -12 & 11 & 16\\0 & 1 & 1 & 4 & -3 & -4\\0 & 1 & 3 & 8 & -4 & -5\end{bmatrix}$$ $$A^{\mathrm{stage}}_{4}=\begin{bmatrix}1 & 3 & 0 & 8 & -4 & -4\\0 & 1 & 1 & 4 & -3 & -4\\0 & -5 & -1 & -12 & 11 & 16\\0 & 1 & 3 & 8 & -4 & -5\end{bmatrix}$$ $$A^{\mathrm{stage}}_{5}=\begin{bmatrix}1 & 3 & 0 & 8 & -4 & -4\\0 & 1 & 1 & 4 & -3 & -4\\0 & 1 & \frac{1}{5} & \frac{12}{5} & - \frac{11}{5} & - \frac{16}{5}\\0 & 1 & 3 & 8 & -4 & -5\end{bmatrix}$$

Complete solution

Work over the real numbers. Row replacement always uses distinct source and target rows; scaling factors are nonzero. An operation acts on the entire row, including every augmented block. In a finite chain the first operation acts first, so the combined left multiplier lists elementary matrices in reverse order.

(a) Comparing complete rows, including both final columns, gives the operations in order:

$$\begin{gathered}\text{1. }R_1\leftrightarrow R_2\\\text{2. }R_2\leftarrow R_2+(-2)R_1\\\text{3. }R_4\leftarrow R_4+(1)R_1\\\text{4. }R_2\leftrightarrow R_3\\\text{5. }R_3\leftarrow (- \frac{1}{5})R_3\end{gathered}$$

For example, after the swap, row 2 minus twice row 1 is $(0,-5,-1,-12,11,16)$; row 4 plus row 1 is $(0,1,3,8,-4,-5)$. The fourth step swaps rows 2 and 3. The fifth scales the current row 3 by $-1/5$, including its last two entries. (b) Track the same operations on $I_4$:

$$H_{0}=\begin{bmatrix}1 & 0 & 0 & 0\\0 & 1 & 0 & 0\\0 & 0 & 1 & 0\\0 & 0 & 0 & 1\end{bmatrix}$$ $$H_{1}=\begin{bmatrix}0 & 1 & 0 & 0\\1 & 0 & 0 & 0\\0 & 0 & 1 & 0\\0 & 0 & 0 & 1\end{bmatrix}$$ $$H_{2}=\begin{bmatrix}0 & 1 & 0 & 0\\1 & -2 & 0 & 0\\0 & 0 & 1 & 0\\0 & 0 & 0 & 1\end{bmatrix}$$ $$H_{3}=\begin{bmatrix}0 & 1 & 0 & 0\\1 & -2 & 0 & 0\\0 & 0 & 1 & 0\\0 & 1 & 0 & 1\end{bmatrix}$$ $$H_{4}=\begin{bmatrix}0 & 1 & 0 & 0\\0 & 0 & 1 & 0\\1 & -2 & 0 & 0\\0 & 1 & 0 & 1\end{bmatrix}$$ $$H_{5}=\begin{bmatrix}0 & 1 & 0 & 0\\0 & 0 & 1 & 0\\- \frac{1}{5} & \frac{2}{5} & 0 & 0\\0 & 1 & 0 & 1\end{bmatrix}$$

Take $H=H_5$. Each tracked row is the corresponding combination of original rows, which proves $A^\prime=HA$ entrywise.

Question 6

Consider the following chain of $5\times7$ matrices; $U_0,U_1,U_2,U_3$ name the previously unnamed stages. The arrows are $A\xrightarrow{\rho_1}U_0\to\cdots\to U_1\xrightarrow{\rho_2}U_2\to\cdots\to U_3\xrightarrow{\rho_3}B_1$, followed by the five displayed arrows $B_1\to\cdots\to B_6$. (a) Identify $\rho_1,\rho_2,\rho_3$. (b) Fill $(I),(II),(III)$ in $B_3\xrightarrow{(I)}(II)\xrightarrow{(III)}B_1$. (c) Give $K$ with $B_5=KB_4$. (d) Is there a row-operation chain from $I_5$ to an $H$ with $B_6=HB_1$? If yes, display all operations and every intermediate matrix, including $H$; otherwise say no such sequence exists.

$$A=\begin{bmatrix}3 & 2 & 1 & -2 & 1 & -2 & -3\\1 & 1 & 1 & 0 & 3 & -1 & 1\\1 & 2 & 3 & -1 & 2 & -2 & 1\\-1 & -1 & -1 & -2 & -9 & 2 & -2\\4 & 3 & 2 & -2 & 4 & -3 & -2\end{bmatrix}$$ $$U_0=\begin{bmatrix}1 & 1 & 1 & 0 & 3 & -1 & 1\\3 & 2 & 1 & -2 & 1 & -2 & -3\\1 & 2 & 3 & -1 & 2 & -2 & 1\\-1 & -1 & -1 & -2 & -9 & 2 & -2\\4 & 3 & 2 & -2 & 4 & -3 & -2\end{bmatrix}$$ $$U_1=\begin{bmatrix}1 & 1 & 1 & 0 & 3 & -1 & 1\\0 & -1 & -2 & -2 & -8 & 1 & -6\\0 & 1 & 2 & -1 & -1 & -1 & 0\\0 & 0 & 0 & -2 & -6 & 1 & -1\\4 & 3 & 2 & -2 & 4 & -3 & -2\end{bmatrix}$$ $$U_2=\begin{bmatrix}1 & 1 & 1 & 0 & 3 & -1 & 1\\0 & -1 & -2 & -2 & -8 & 1 & -6\\0 & 1 & 2 & -1 & -1 & -1 & 0\\0 & 0 & 0 & -2 & -6 & 1 & -1\\0 & -1 & -2 & -2 & -8 & 1 & -6\end{bmatrix}$$ $$U_3=\begin{bmatrix}1 & 1 & 1 & 0 & 3 & -1 & 1\\0 & 1 & 2 & 2 & 8 & -1 & 6\\0 & 0 & 0 & -3 & -9 & 0 & -6\\0 & 0 & 0 & -2 & -6 & 1 & -1\\0 & 0 & 0 & 0 & 0 & 0 & 0\end{bmatrix}$$ $$B_1=\begin{bmatrix}1 & 1 & 1 & 0 & 3 & -1 & 1\\0 & 1 & 2 & 2 & 8 & -1 & 6\\0 & 0 & 0 & 1 & 3 & 0 & 2\\0 & 0 & 0 & -2 & -6 & 1 & -1\\0 & 0 & 0 & 0 & 0 & 0 & 0\end{bmatrix}$$ $$B_2=\begin{bmatrix}1 & 1 & 1 & 0 & 3 & -1 & 1\\0 & 1 & 2 & 2 & 8 & -1 & 6\\0 & 0 & 0 & 1 & 3 & 0 & 2\\0 & 0 & 0 & 0 & 0 & 1 & 3\\0 & 0 & 0 & 0 & 0 & 0 & 0\end{bmatrix}$$ $$B_3=\begin{bmatrix}1 & 0 & -1 & -2 & -5 & 0 & -5\\0 & 1 & 2 & 2 & 8 & -1 & 6\\0 & 0 & 0 & 1 & 3 & 0 & 2\\0 & 0 & 0 & 0 & 0 & 1 & 3\\0 & 0 & 0 & 0 & 0 & 0 & 0\end{bmatrix}$$ $$B_4=\begin{bmatrix}1 & 0 & -1 & 0 & 1 & 0 & -1\\0 & 1 & 2 & 2 & 8 & -1 & 6\\0 & 0 & 0 & 1 & 3 & 0 & 2\\0 & 0 & 0 & 0 & 0 & 1 & 3\\0 & 0 & 0 & 0 & 0 & 0 & 0\end{bmatrix}$$ $$B_5=\begin{bmatrix}1 & 0 & -1 & 0 & 1 & 0 & -1\\0 & 1 & 2 & 0 & 2 & -1 & 2\\0 & 0 & 0 & 1 & 3 & 0 & 2\\0 & 0 & 0 & 0 & 0 & 1 & 3\\0 & 0 & 0 & 0 & 0 & 0 & 0\end{bmatrix}$$ $$B_6=\begin{bmatrix}1 & 0 & -1 & 0 & 1 & 0 & -1\\0 & 1 & 2 & 0 & 2 & 0 & 5\\0 & 0 & 0 & 1 & 3 & 0 & 2\\0 & 0 & 0 & 0 & 0 & 1 & 3\\0 & 0 & 0 & 0 & 0 & 0 & 0\end{bmatrix}$$

The five arrows after $B_1$ are, in order:

$$\begin{gathered}\text{1. }R_4\leftarrow R_4+(2)R_3\\\text{2. }R_1\leftarrow R_1+(-1)R_2\\\text{3. }R_1\leftarrow R_1+(2)R_3\\\text{4. }R_2\leftarrow R_2+(-2)R_3\\\text{5. }R_2\leftarrow R_2+(1)R_4\end{gathered}$$

Complete solution

Work over the real numbers. Row replacement always uses distinct source and target rows; scaling factors are nonzero. An operation acts on the entire row, including every augmented block. In a finite chain the first operation acts first, so the combined left multiplier lists elementary matrices in reverse order.

(a) Read the rows at the three marked arrows:

$$\rho_1:R_1\leftrightarrow R_2,\qquad \rho_2:R_5\leftarrow R_5-4R_1,\qquad \rho_3:R_3\leftarrow-\tfrac13R_3.$$

For $\rho_2$, subtracting four times $(1,1,1,0,3,-1,1)$ from $(4,3,2,-2,4,-3,-2)$ gives $(0,-1,-2,-2,-8,1,-6)$. For $\rho_3$, scaling $(0,0,0,-3,-9,0,-6)$ gives $(0,0,0,1,3,0,2)$. (b) Undo the two arrows $B_1\to B_2\to B_3$ in reverse:

$$(I):R_1\leftarrow R_1+R_2,\qquad (II)=B_2,\qquad (III):R_4\leftarrow R_4-2R_3.$$

(c) Only row 2 is replaced by row 2 minus twice row 3, so:

$$K=\begin{bmatrix}1 & 0 & 0 & 0 & 0\\0 & 1 & -2 & 0 & 0\\0 & 0 & 1 & 0 & 0\\0 & 0 & 0 & 1 & 0\\0 & 0 & 0 & 0 & 1\end{bmatrix}$$

(d) Yes. Apply the following same five operations to $I_5$:

$$\begin{gathered}\text{1. }R_4\leftarrow R_4+(2)R_3\\\text{2. }R_1\leftarrow R_1+(-1)R_2\\\text{3. }R_1\leftarrow R_1+(2)R_3\\\text{4. }R_2\leftarrow R_2+(-2)R_3\\\text{5. }R_2\leftarrow R_2+(1)R_4\end{gathered}$$ $$H_{0}=\begin{bmatrix}1 & 0 & 0 & 0 & 0\\0 & 1 & 0 & 0 & 0\\0 & 0 & 1 & 0 & 0\\0 & 0 & 0 & 1 & 0\\0 & 0 & 0 & 0 & 1\end{bmatrix}$$ $$H_{1}=\begin{bmatrix}1 & 0 & 0 & 0 & 0\\0 & 1 & 0 & 0 & 0\\0 & 0 & 1 & 0 & 0\\0 & 0 & 2 & 1 & 0\\0 & 0 & 0 & 0 & 1\end{bmatrix}$$ $$H_{2}=\begin{bmatrix}1 & -1 & 0 & 0 & 0\\0 & 1 & 0 & 0 & 0\\0 & 0 & 1 & 0 & 0\\0 & 0 & 2 & 1 & 0\\0 & 0 & 0 & 0 & 1\end{bmatrix}$$ $$H_{3}=\begin{bmatrix}1 & -1 & 2 & 0 & 0\\0 & 1 & 0 & 0 & 0\\0 & 0 & 1 & 0 & 0\\0 & 0 & 2 & 1 & 0\\0 & 0 & 0 & 0 & 1\end{bmatrix}$$ $$H_{4}=\begin{bmatrix}1 & -1 & 2 & 0 & 0\\0 & 1 & -2 & 0 & 0\\0 & 0 & 1 & 0 & 0\\0 & 0 & 2 & 1 & 0\\0 & 0 & 0 & 0 & 1\end{bmatrix}$$ $$H_{5}=\begin{bmatrix}1 & -1 & 2 & 0 & 0\\0 & 1 & 0 & 1 & 0\\0 & 0 & 1 & 0 & 0\\0 & 0 & 2 & 1 & 0\\0 & 0 & 0 & 0 & 1\end{bmatrix}$$

Take $H=H_5$. We have displayed every matrix in $I_5=H_0\to H_1\to\cdots\to H_5$. Each step changes a row combination of the original input in exactly the same way, so applying the chain to $B_1$ gives $H_jB_1=B_{j+1}$ at stage $j$, in particular $HB_1=B_6$. This argument applies to rectangular $B_1$ and does not attempt to invert it.

Question 7

The $3\times4$ matrices $A_1,\ldots,A_5$ follow the four operations below. (a) Give $J_1,\ldots,J_4$ with $A_{j+1}=J_jA_j$. (b) Suppose the augmented matrices $[A_1\mid B_1],\ldots,[A_4\mid B_4],[A_5\mid I_3]$ follow exactly the same four operations, where every $B_j$ is $3\times3$. Find all four $B_j$. (c) Is $B_1A_1$ row-equivalent to $A_5$? If yes, give all operations in a suitable chain; if no, explain why not.

$$\begin{gathered}\text{1. }R_2\leftarrow R_2+(-1)R_1\\\text{2. }R_3\leftarrow R_3+(-2)R_1\\\text{3. }R_3\leftarrow R_3+(-1)R_2\\\text{4. }R_1\leftarrow R_1+(-1)R_2\end{gathered}$$

Complete solution

Work over the real numbers. Row replacement always uses distinct source and target rows; scaling factors are nonzero. An operation acts on the entire row, including every augmented block. In a finite chain the first operation acts first, so the combined left multiplier lists elementary matrices in reverse order.

(a) Applying each indicated operation to $I_3$ gives:

$$J_1=\begin{bmatrix}1 & 0 & 0\\-1 & 1 & 0\\0 & 0 & 1\end{bmatrix}$$ $$J_2=\begin{bmatrix}1 & 0 & 0\\0 & 1 & 0\\-2 & 0 & 1\end{bmatrix}$$ $$J_3=\begin{bmatrix}1 & 0 & 0\\0 & 1 & 0\\0 & -1 & 1\end{bmatrix}$$ $$J_4=\begin{bmatrix}1 & -1 & 0\\0 & 1 & 0\\0 & 0 & 1\end{bmatrix}$$

(b) Every row operation affects the right block too, so $J_1B_1=B_2$, $J_2B_2=B_3$, $J_3B_3=B_4$, $J_4B_4=I_3$. Start with the last equality and successively apply the inverse operations:

$$B_4=J_4^{-1},\quad B_3=J_3^{-1}J_4^{-1},\quad B_2=J_2^{-1}J_3^{-1}J_4^{-1},\quad B_1=J_1^{-1}J_2^{-1}J_3^{-1}J_4^{-1}.$$ $$B_1=\begin{bmatrix}1 & 1 & 0\\1 & 2 & 0\\2 & 3 & 1\end{bmatrix}$$ $$B_2=\begin{bmatrix}1 & 1 & 0\\0 & 1 & 0\\2 & 3 & 1\end{bmatrix}$$ $$B_3=\begin{bmatrix}1 & 1 & 0\\0 & 1 & 0\\0 & 1 & 1\end{bmatrix}$$ $$B_4=\begin{bmatrix}1 & 1 & 0\\0 & 1 & 0\\0 & 0 & 1\end{bmatrix}$$

These explicit matrices can also be checked by the four right-block equalities above, so they are not inferred from cancellation of a rectangular $A_j$. (c) Yes. Put $P=J_4J_3J_2J_1$. The augmented chain gives both $A_5=PA_1$ and $PB_1=I_3$. Hence applying the four operations once to $B_1A_1$ gives $P(B_1A_1)=A_1$; applying them a second time gives $PA_1=A_5$. Thus a fully specified chain consists of:

$$\begin{gathered}\text{1. }R_2\leftarrow R_2+(-1)R_1\\\text{2. }R_3\leftarrow R_3+(-2)R_1\\\text{3. }R_3\leftarrow R_3+(-1)R_2\\\text{4. }R_1\leftarrow R_1+(-1)R_2\\\text{5. }R_2\leftarrow R_2+(-1)R_1\\\text{6. }R_3\leftarrow R_3+(-2)R_1\\\text{7. }R_3\leftarrow R_3+(-1)R_2\\\text{8. }R_1\leftarrow R_1+(-1)R_2\end{gathered}$$

Question 8

For arbitrary real $\alpha_1,\alpha_2,\alpha_3,\beta_1,\beta_2,\beta_3$, matrices $A,B$ have four rows and follow the six operations below. Give explicit $4\times4$ matrices $G,H$ such that $B=GA$ and $A=HB$.

$$\begin{gathered}\text{1. }R_2\leftarrow R_2+(\alpha_{1})R_1\\\text{2. }R_3\leftarrow R_3+(\alpha_{2})R_1\\\text{3. }R_4\leftarrow R_4+(\alpha_{3})R_1\\\text{4. }R_1\leftarrow R_1+(\beta_{1})R_2\\\text{5. }R_1\leftarrow R_1+(\beta_{2})R_3\\\text{6. }R_1\leftarrow R_1+(\beta_{3})R_4\end{gathered}$$

Complete solution

Work over the real numbers. Row replacement always uses distinct source and target rows; scaling factors are nonzero. An operation acts on the entire row, including every augmented block. In a finite chain the first operation acts first, so the combined left multiplier lists elementary matrices in reverse order.

Write the original rows as $a_1,a_2,a_3,a_4$. After the first three operations the rows are $a_1$, $a_2+\alpha_1a_1$, $a_3+\alpha_2a_1$, $a_4+\alpha_3a_1$. The final three operations use those updated rows, so the final first row is $(1+\alpha_1\beta_1+\alpha_2\beta_2+\alpha_3\beta_3)a_1+\beta_1a_2+\beta_2a_3+\beta_3a_4$. The other three rows remain as above. These four row combinations give $G$. Undoing the six operations in reverse order gives $H$:

$$G=\begin{bmatrix}\alpha_{1} \beta_{1} + \alpha_{2} \beta_{2} + \alpha_{3} \beta_{3} + 1 & \beta_{1} & \beta_{2} & \beta_{3}\\\alpha_{1} & 1 & 0 & 0\\\alpha_{2} & 0 & 1 & 0\\\alpha_{3} & 0 & 0 & 1\end{bmatrix}$$ $$H=\begin{bmatrix}1 & - \beta_{1} & - \beta_{2} & - \beta_{3}\\- \alpha_{1} & \alpha_{1} \beta_{1} + 1 & \alpha_{1} \beta_{2} & \alpha_{1} \beta_{3}\\- \alpha_{2} & \alpha_{2} \beta_{1} & \alpha_{2} \beta_{2} + 1 & \alpha_{2} \beta_{3}\\- \alpha_{3} & \alpha_{3} \beta_{1} & \alpha_{3} \beta_{2} & \alpha_{3} \beta_{3} + 1\end{bmatrix}$$

More explicitly, subtract $\beta_3R_4$, $\beta_2R_3$, $\beta_1R_2$ from row 1, in that order, restoring $a_1$. Then subtract $\alpha_3R_1$ from row 4, $\alpha_2R_1$ from row 3 and $\alpha_1R_1$ from row 2. All original rows are restored. Starting with final rows $b_j$, this means $a_1=b_1-\beta_1b_2-\beta_2b_3-\beta_3b_4$ and $a_{i+1}=b_{i+1}-\alpha_i a_1$, which expands exactly to the displayed $H$. Thus $HG=GH=I_4$. No parameter needs to be nonzero: these are all row replacements, even when the upper-left entry of $G$ is zero.

Question 9

Let $\alpha_1,\alpha_2,\beta_1,\beta_2$ be real and $\beta_1\beta_2\ne0$. Four-row $A,B$ follow the five operations below. (a) Display one explicit $4\times4$ matrix $G$ with $B=GA$ and a chain from $I_4$ to $G$; intermediate matrices need not be displayed. (b) Give a chain from $G$ back to $I_4$.

$$\begin{gathered}\text{1. }R_3\leftarrow R_3+(\alpha_{1})R_2\\\text{2. }R_1\leftarrow (\beta_{1})R_1\\\text{3. }R_1\leftrightarrow R_4\\\text{4. }R_1\leftarrow R_1+(\alpha_{2})R_3\\\text{5. }R_2\leftarrow (\beta_{2})R_2\end{gathered}$$

Complete solution

Work over the real numbers. Row replacement always uses distinct source and target rows; scaling factors are nonzero. An operation acts on the entire row, including every augmented block. In a finite chain the first operation acts first, so the combined left multiplier lists elementary matrices in reverse order.

(a) If the original rows are $a_1,a_2,a_3,a_4$, then the first step gives row 3 equal to $a_3+\alpha_1a_2$. Scaling row 1 and swapping rows 1 and 4 puts $a_4$ in row 1 and $\beta_1a_1$ in row 4. Adding $\alpha_2$ times the current row 3 to row 1 gives $a_4+\alpha_2a_3+\alpha_1\alpha_2a_2$. Finally row 2 is $\beta_2a_2$. Hence:

$$G=\begin{bmatrix}0 & \alpha_{1} \alpha_{2} & \alpha_{2} & 1\\0 & \beta_{2} & 0 & 0\\0 & \alpha_{1} & 1 & 0\\\beta_{1} & 0 & 0 & 0\end{bmatrix}$$

The required chain from $I_4$ is exactly the five original operations in their original order. Applying them to the standard rows produces the displayed four rows of $G$. (b) Undo them in reverse order:

$$\begin{gathered}\text{1. }R_2\leftarrow (\frac{1}{\beta_{2}})R_2\\\text{2. }R_1\leftarrow R_1+(- \alpha_{2})R_3\\\text{3. }R_1\leftrightarrow R_4\\\text{4. }R_1\leftarrow (\frac{1}{\beta_{1}})R_1\\\text{5. }R_3\leftarrow R_3+(- \alpha_{1})R_2\end{gathered}$$

After the first two reverse steps, row 2 is $e_2$ and row 1 is $e_4$. The swap restores row 4 to $e_4$ and row 1 to $\beta_1e_1$. Reciprocal scaling restores $e_1$, and the final row replacement changes row 3 from $e_3+\alpha_1e_2$ to $e_3$. Thus the endpoint is $I_4$. The nonzero assumptions on $\beta_1,\beta_2$ are used exactly for the reciprocal scalings.

Question 10

Let $A,A^\prime$ be $m\times n$ matrices and suppose they are row-equivalent. Prove that $AB$ and $A^\prime B$ are row-equivalent for every $n\times p$ matrix $B$.

Complete solution

Work over the real numbers. Row replacement always uses distinct source and target rows; scaling factors are nonzero. An operation acts on the entire row, including every augmented block. In a finite chain the first operation acts first, so the combined left multiplier lists elementary matrices in reverse order.

For the proof, denote the inner and output dimensions by $p$ and $q$, respectively; this only relabels the dimensions in the question.

(a): single-operation forward transport

To prove the forward identity entrywise, in the replacement case only output row $k$ changes:

$$(A^\prime B)_{kj}=\sum_{r=1}^{p}(a_{kr}+\alpha a_{ir})b_{rj}=(AB)_{kj}+\alpha(AB)_{ij}.$$

Every other output row agrees. Scaling gives $(A^\prime B)_{kj}=\beta(AB)_{kj}$ and leaves other rows fixed. Swapping rows $i,k$ of $A$ interchanges exactly rows $i,k$ of $AB$. This proves all three forward transport identities directly, and applying the inverse operation proves the reverse identities.

(b): induction on the length of the row-operation sequence

For length zero the matrices are identical and so are their products. Suppose the assertion holds for a sequence of length $n$. For a sequence of length $n+1$, let $A_n$ be the matrix after the first $n$ operations. The induction hypothesis sends $AB$ to $A_nB$ by those same operations. The forward identity proved entrywise in (a) sends $A_nB$ to $A^\prime B$ by the final operation. Thus all $n+1$ operations carry $AB$ to $A^\prime B$. Induction proves the assertion for every finite length. All products have size $m\times q$, so these are legal row operations on matrices of one fixed size.