Gaussian Elimination, Elementary Matrices and Reduced Row Echelon Form

A swap is its own inverse; the inverse of $R_p\leftarrow cR_p$ is $R_p\leftarrow c^{-1}R_p$ because $c\ne0$ in a field; and the inverse of $R_p\leftarrow R_p+cR_q$ is $R_p\leftarrow R_p-cR_q$.

The empty operation sequence proves reflexivity, reversing a sequence and replacing every operation by its inverse proves symmetry, and concatenating two finite sequences proves transitivity. These arguments also cover empty matrices and the empty reduction.

If $E$ swaps rows $r,s$ of $I_n$, the displayed sum exchanges rows $r,s$ of $A$; if $E$ scales row $r$ of $I_n$ by $c$, it replaces row $r$ of $A$ by $cR_r$; and if $E$ adds $c$ times row $s$ to row $r$ of $I_n$, it replaces row $r$ of $A$ by $R_r+cR_s$, leaving every other row fixed.

These are precisely the three corresponding row operations on $A$, so left multiplication by $E$ performs the operation. The assertion is vacuous when there is no row on which an elementary operation can be defined, and it remains valid when $p=0$.

Let $E'$ be the elementary matrix of $\rho^{-1}$. Applying $\rho$ and then $\rho^{-1}$ to $I_n$ gives $E'E=I_n$, while applying them in the reverse order gives $EE'=I_n$.

Thus $E'$ is a two-sided inverse of $E$, so $E$ is invertible and $E^{-1}=E'$.

After no operations the intermediate matrix is $A=I_nA$, the empty-product formula. If after $k$ operations it is $E_k\cdots E_1A$, then [L1] says the next operation gives $E_{k+1}(E_k\cdots E_1A)$.

Associativity rewrites the successor expression as $E_{k+1}E_k\cdots E_1A$; induction therefore gives the formula after all $r$ operations, including $r=0$.

A row swap only reorders equations; multiplying an equation by $c\ne0$ preserves it in both directions after multiplication by $c^{-1}$; and replacing one equation by itself plus $c$ times another preserves simultaneous satisfaction because the added equation already holds. Thus every solution of the original system solves the transformed system.

Apply the same argument to the inverse operation from [L2] to obtain the reverse inclusion. Hence the solution sets are equal, without any assumption that $A$ is square or invertible; iteration gives the finite-reduction claim.

If $A$ is not zero, locate the leftmost column containing a nonzero entry, swap one such entry into the first available row, scale it to $1$, and use row additions to clear every entry below it. These are elementary operations and create the first pivot with all earlier columns zero.

Apply the same construction inductively to the strictly smaller submatrix below and to the right of that pivot. Operations confined to its rows do not change the earlier zero columns or pivot row, so the successive pivots move strictly right.

The procedure terminates when no row, no column or no nonzero entry remains; the unused rows are zero and lie at the bottom. The resulting matrix satisfies all echelon conditions, including the all-zero and zero-sized cases.

Use [L1] to reach row echelon form, and scale every nonzero row by the inverse of its pivot so that each pivot is $1$.

Process the pivots from bottom to top. For a pivot in column $j$, add suitable multiples of its row to all rows above it to clear column $j$; later pivot columns remain unchanged because the current row is zero in those columns.

Echelon order and the zero rows are preserved, every pivot is $1$, and every pivot column is zero off its pivot. Thus the output is reduced row echelon form, including when there is no pivot.

Existence is [L1]. For uniqueness, [L2] applied to $Ax=0$ shows that $R$ and $S$ have the same homogeneous solution set.

The common homogeneous solution set determines the pivot columns. Indeed, column $j$ is a pivot column exactly when every solution $x$ satisfying $x_k=0$ for all $k>j$ also satisfies $x_j=0$. For a pivot column this follows from its pivot equation; for a nonpivot column, set that free variable to $1$ and every other free variable to $0$. Induction over the finite ordered columns therefore gives the same pivot positions for $R$ and $S$.

For each nonpivot column $j$, there is a unique homogeneous solution whose nonpivot coordinates are $1$ at $j$ and $0$ elsewhere. Its coordinate at pivot $p_i$ is the negative of the entry in row $i$, column $j$; pivot columns are unit columns by [L3]. Thus the common solution set determines every entry. With no columns, no rows, or no pivots the same description is empty or all zero, so in every case $R=S$.

Every row of $B$ is a row of $A$, a nonzero scalar multiple of one, or a linear combination of two rows of $A$. Hence $\operatorname{Row}(B)\subseteq\operatorname{Row}(A)$.

Applying step 1.1 to the inverse operation from [L2] gives the reverse inclusion. Thus the row spaces, and therefore their dimensions and row ranks, are equal; iteration covers row equivalence.

The nonzero rows span $\operatorname{Row}(R)$ because deleting zero rows does not change a span, and this equals $\operatorname{Row}(A)$ by [L1].

In a linear combination of the nonzero rows equal to zero, inspect the pivot column of the first row: every later row is zero there, so its coefficient is zero. Repeating down the strictly increasing pivot columns forces every coefficient to be zero. Thus the rows are independent and form a basis; their number is the pivot count.

If $A$ and $B$ are row equivalent, [L2] gives equal row spaces, and reducing either one gives a reduced form in the same row-equivalence class, so [L1] gives the same RREF.

Suppose the row spaces are the same space $W$. If the nonzero rows of an RREF have pivots $p_1<\cdots<p_r$, then [L3] expresses every nonzero $w\in W$ uniquely as a linear combination of those rows. The first row with nonzero coefficient makes the leading position of $w$ equal to its pivot. Hence the pivot columns are exactly the possible leading positions of nonzero vectors in $W$, so both RREFs have the same pivots. Corresponding nonzero rows have $1$ in the same pivot and $0$ in every other pivot column. Their difference lies in $W$ and vanishes at every possible leading position, so it is zero. The nonzero rows, and then the zero rows, agree.

If $A$ and $B$ have a common RREF, reverse the reduction from $B$ to that form using [L4] and concatenate it with the reduction from $A$; this gives a row reduction from $A$ to $B$.

The equation $Ac=0$ says exactly that the columns of $A$, with coefficients $c_j$, have zero linear combination.

Apply the same row operations to $[A\mid0]$. Its last column stays zero, so [L1] gives $Ac=0$ if and only if $Bc=0$.

Restricting $c$ to any chosen column subfamily shows that it is independent for $A$ exactly when it is independent for $B$. Hence the largest independent column families and their dimension agree, although the literal column spaces may differ.

In $R$, the pivot columns are distinct unit columns, so they are independent. Every nonpivot column equals the linear combination of those unit columns whose coefficients are its entries in the pivot rows, so the pivot columns span every column of $R$.

Each relation used in step 1.1 holds among the corresponding columns of $A$ by [L1], and every relation among the pivot columns transfers in both directions.

Therefore the original pivot-indexed columns are independent and span every column of $A$, hence form a basis of $\operatorname{Col}(A)$.

There is one nonzero echelon row for each pivot, so [L1] and [L3] make the row rank equal to the pivot count of $R$. This applies to every echelon form of $A$.

Let $Q$ be the RREF of $A$. Step 1.1 makes the number of pivots of $Q$ equal to the row rank, while [L2] and [L3] make that same number equal to the column rank. Hence the two ranks are equal, and step 1.1 shows that both equal the pivot count of the originally chosen echelon form $R$. This includes pivot count zero.

Fact [L5] shows that $L_A(x)=Ax$ is linear. By [L4], every value $Ax$ is a linear combination of the columns of $A$, with coefficients $x_j$, and every such combination is $Ax$ for that coefficient column. Hence $\operatorname{im}L_A=\operatorname{Col}(A)$.

Taking dimensions and using [L1]–[L3] gives $\operatorname{rank}L_A=\dim\operatorname{Col}(A)=\operatorname{rank}A$.

Apply rank–nullity to $L_A:F^n\to F^m$ to obtain $n=\operatorname{rank}L_A+\dim\ker L_A$.

By [L1] the first term is $\operatorname{rank}A$, and by [L3] the kernel is $N(A)$. Substitution proves the formula, including $n=0$.

If $z\in N(A)$, then $A(x_p+z)=Ax_p+Az=b+0=b$, so $x_p+z\in S(A,b)$.

Conversely, if $x\in S(A,b)$, then $A(x-x_p)=Ax-Ax_p=b-b=0$, so $x-x_p\in N(A)$ and $x=x_p+(x-x_p)\in x_p+N(A)$. Thus $S(A,b)=x_p+N(A)$.

Since $N(A)=\ker L_A$, facts [L3] and [L4] make it a linear subspace. Its translate $x_p+N(A)$ is therefore an affine subspace by [L5].

Replace $[A\mid b]$ by its unique RREF $R$. By [L1] this changes no solution.

A pivot in the augmented column produces a row $0=1$, after its pivot has been normalized, so the system is inconsistent. Conversely, if there is no such pivot, every nonzero row has a coefficient pivot and imposes an equation for that pivot variable.

Choose arbitrary values for the nonpivot variables. Each pivot row then determines its pivot variable uniquely, and substituting these values satisfies every nonzero row while zero rows impose nothing. Every solution has those same free coordinates and therefore arises uniquely from this construction.

Row reduce the augmented matrix. Its coefficient block is an echelon form row equivalent to $A$, while the whole reduced matrix is an echelon form of $[A\mid b]$. Thus [L2] identifies their respective pivot counts with the two ranks. Those counts differ exactly when the augmented column supplies one additional pivot.

By [L1], absence of that additional augmented pivot is equivalent to consistency. Step 1.1 therefore proves both directions.

If the augmented column is a pivot column, [L1] gives no solution.

If there is no augmented pivot and no free variable, [L1] determines every variable uniquely, so there is exactly one solution.

If a free variable exists, fix all other free variables and let that one range through $F$. The parametrisation of [L1] assigns distinct solutions to distinct scalars, injecting the infinite set $F$ into the solution set; hence the solution set is not finite and is infinite.

By [L6], matrix invertibility is equivalent to the multiplication map being an isomorphism. An isomorphism has a two-sided inverse by [L8], hence is injective, and [L7] then gives $N(A)=\{0\}$.

By [L2], trivial nullspace is equivalent to rank $n$, and [L4] makes this equivalent to having $n$ pivots. A square matrix has $n$ pivots exactly when every row and column contains one.

An $n\times n$ RREF with a pivot in every row and column is $I_n$. By [L1], RREF $I_n$ is equivalent to the assertion that every right-hand side produces a consistent system with no free variable, hence exactly one solution.

Under condition 7, define $S(b)$ to be the unique solution of $Ax=b$. Then $L_A(S(b))=b$, and uniqueness for the right-hand side $Ax$ gives $S(L_A(x))=x$. Moreover, linearity of $L_A$ from [L3] gives $L_A(S(\lambda y+z))=\lambda y+z=L_A(\lambda S(y)+S(z))$; applying the inverse function $S$ proves that $S$ is linear. Thus $L_A$ has a two-sided linear inverse and is a linear isomorphism by [L8], so [L6] returns condition 1. Together with steps 1.1–3.1, this closes the implication cycle and proves all seven conditions equivalent. For $n=0$, the unique empty matrix is $I_0$, its map on the zero space is bijective, and every condition holds.

By [L1] row reduction takes $A$ to $I_n$; by [L2] there are elementary real matrices with $E_r\cdots E_1A=I_n$.

Multiply by the explicit inverses in reverse order to obtain $A=E_1^{-1}\cdots E_r^{-1}$, and each factor is elementary by [L3].

If $A=I_n$, take $r=0$ and the empty product. No determinant is used.

Let $E$ be the product encoding the row operations. The two output blocks are $EA$ and $EI_n=E$.

If the output is $[I_n\mid B]$, then $EA=I_n$ and $B=E$. By [L1], $A$ is invertible, and multiplying $EA=I_n$ by $A^{-1}$ gives $E=A^{-1}=B$.

Conversely, if $A$ is invertible, [L1] supplies a reduction of $A$ to $I_n$; applying it to $[A\mid I_n]$ gives $[I_n\mid A^{-1}]$ by step 2.1. If the left block cannot reach $I_n$, [L1] says no inverse exists.