Reduced Row Echelon Form
Definition 1. A matrix is said to be in reduced row echelon form(RREF) if the following three conditions are satisfied:
i) Any row containing a nonzero entry precedes any row in which all the entries are zero.
ii) The first nonzero entry in each row is the only nonzero entry in its column.
iii) The first nonzero entry in each row is 1 and it occurs in a column to the right of the first nonzero entry in the preceding row.
위와 같은 조건을 만족하는 행렬을 기약 행 사다리 꼴, 줄여서 RREF라고 부른다. 쉽게 생각해서 upper triangle matrix를 만든다고 생각하면 된다.
Gaussian Elimination
Definition 2. The procedure for reducing an augmented matrix $(A \,|\, b)$ corresponding to the system $Ax = b$ to RREF by performing the elementary row operations is called Gaussian elimination.
Theorem 1
Theorem 1. Gaussian elimination transforms any matrix into its RREF.
Proof. We may apply the induction to $m$, where $A \neq O \in M_{m \times n}(F)$. If $m = 1$, then $R_{\frac{1}{A_{11}}1}(A)$ is the RREF of $A$.
Suppose that the theorem is true for $m-1$ for some $m > 1$. Denote $R_{\frac{1}{A_{11}}1}(A) = A'$, i.e., $A' = \begin{pmatrix} 1 & \cdots & A'_{1n} \\
& B \end{pmatrix}$, where $B \in M_{(m-1) \times n}$. By the induction hypothesis, $B$ can be transformed into its RREF. By means of at most $n$ type 2 row operation, we can transform $A'$ into its RREF. $\blacksquare$
Theorem 2
Theorem 2. Let $A \in M_{m \times n}(F)$ such that rank($A$) = $r > 0$, and let $B$ be the RREF of $A$. Then the followings hold:
(a) The number of nonzero rows in $B$ is $r$.
(b) $\forall i \in \{1, ..., r\}, \exists$ $[B]^{j_i}$ such that $[B]^{j_i} = e_i$, where $e_i$ is the standard ordered basis vector of $\mathbb{R}^r$.
(c) $\{[A]^{j_1}, \cdots, [A]^{j_r}\}$ are linearly independent.
(d) $\forall k \in \{1, ..., n\}$, if $[B]^k = \sum_{i=1}^r d_ie_i$, then $[A]^k = \sum_{i=1}^r d_i[A]^{j_i}$.
Proof.
(a) Since elementary row operation is rank-preserving and $B$ is the RREF of $A$, rank($B$) = $r$. This means that the maximum number of linearly independent rows of $B$ is $r$. Clearly zero rows are not the linearly independent rows. Thus the number of nonzero rows in $B$ is $r$.
(b) Since rank($B$) = $r$, there is $r$ linearly independent columns in $B$. By the definition of RREF, the each columns are same to $e_i$. Thus for each $i = 1, ..., r, \exists [B]^{j_i}$ such that $[B]^{j_i} = e_i$.
(c) Suppose that $\sum_{i=1}^r c_i[A]^{j_i} = \mathbf{0}$ for some $c_i \in F$. Since $B$ is the RREF of $A$, we denote that $B = R_p \cdots R_1 (A) = R_p(I) \cdots R_1(I)A = MA$, where $M := R_p(I) \cdots R_1(I)A$. Note that $[B]^{j_i} = M[A]^{j_i} (i = 1, ..., r)$. Thus $$M(\sum_{i=1}^r c_i[A]^{j_i}) = \sum_{i=1}^r c_i[B]^{j_i} = \sum_{i=1}^r c_ie_i = (c_1, \cdots, c_r)^t = \mathbf{0} \\
\Longrightarrow c_1 = \cdots = c_r = 0.$$ Hence $\{[A]^{j_1}, \cdots, [A]^{j_r}\}$ is linearly independent.
(d) Note that $A = M^{-1}B$, i.e., $[A]^k = M^{-1}[B]^k (k = 1, ..., n)$. Since $[B]^k = \sum_{i=1}^r d_ie_i$, $[A]^k = M^{-1}\sum_{i=1}^r d_ie_i = M^{-1} \sum_{i=1}^r d_i[B]^{j_i} = \sum_{i=1}^r d_i[A]^{j_i}$. $\blacksquare$
Corollary
Corollary. The RREF of a matrix is unique.
Proof. Assume that $B$ and $C$ are the RREF of $A \in M_{m \times n}(F)$ that rank($A$) = $r > 0$. By Theorem 2, we can write $[B]^k = \sum_{i=1}^r c_ie_i$ and $[C]^k = \sum_{i=1}^r d_ie_i$ for some $c_i, d_i \in F (i=1, ..., r)$, respectively. Then $$[A]^k = \sum_{i=1}^r c_i[A]^{j_i} = \sum_{i=1}^r d_i[A]^{j_i} \\ \Longrightarrow \sum_{i=1}^r (c_i - d_i)[A]^{j_i} = \mathbf{0} \\ \Longrightarrow c_i = d_i (i = 1, ..., r) \Longleftrightarrow B = C,$$ where $[B]^{j_i} = e_i (i = 1, ..., r)$. $\blacksquare$
