Reduced Row Echolen Form

Forward Elimination and Backward Substitution

Definition 48. (1) Forward elimination is the procedure making below each first nonzero coefficients in the nonzero rows of the augmented matrix of the system into a column of zeros.
(2) After the forward elimination, the first nonzero coefficients in the nonzero rows are the pivots.
(3) The first nonzero number $1$'s at the pivotal positions are called the leading $1$'s.
(4) Backward substitution is the procedure making each column of the augmented matrix of the system containing a leading $1$ into a column of zeros. 

Reduced Row Echelon Form

Definition 49. A matrix is said to be in row echelon form (REF) if it satisfies the following conditions:
(1) The zero rows, if there exist, come last in the order of rows.
(2) The first nonzero entry in each row is $1$, called the leading $1$.
(3) Below each leading $1$ in the coefficient part is a column of zeros. Thus, in any two consecutive rows, the leading $1$ in the lower row appears farther to the right than the leading $1$ in the upper row. 
A matrix is said to be in reduced row echelon form (RREF) if it is in row echelon form and satisfies the following additional condition:
(4) Each column of the coefficient part containing a leading $1$ has zeros everywhere else.

쉽게 생각해서 REF는 upper triangle matrix와 유사한 꼴이고, 더 나아가 RREF는 leading $1$을 포함하는 열의 성분을 싹 다 $0$으로 만들어 버린 행렬이다. 

Gauss-Jordan Elimination

Definition 50. The procedure for reducing the augmented matrix to REF by performing the elementary row operations is called Gaussian elimination. Furthermore, if this procedure reduces the augmented matrix to RREF, then it is called Gauss-Jordan elimination.

Theorem 57

Theorem 57. Gauss-Jordan 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$ and we say the nonzero entry $A_{1j}$ ($1 \leq j \leq n$), then $R_{\frac{1}{A_{1j}}1}(A)$ is the RREF of $A$.
Suppose that the theorem is true for $m-1$ for some $m > 2$. Let's say that $j$-th colmun has the leftmost nonzero entry, and we can apply the type 1 elementary row operation to the matrix so that the first row has this nonzero entry. Denote $R_{\frac{1}{A_{1j}}1}(A) = A'$, i.e., $$A' = \begin{bmatrix} 0 & \cdots & 0 & 1 & \cdots & A'_{1n} \\ \\ & & & B & & & \\ & \end{bmatrix},$$ where $B \in M_{(m-1) \times n}$. By the induction hypothesis, $B$ can be transformed into its RREF.
If $B$ has the leading $1$ in the $j$-th column, we can apply the type 3 elementary row operation to $A'$ to satisfy the condition (4) of Definition 44 for $A_{1j}$. This makes the submatrix $B$ into $B'$ and $A'$ into $A''$, and by the induction hypothesis again, $B'$ can be transformed into its RREF. By means of at most $n-1$ type 3 row operations, we can transform $A''$ into its RREF.
If $B$ does not have the leading $1$ in the $j$-th column, then by means of at most $n-1$ type 3 row operations, we can transform $A'$ into its RREF. $\blacksquare$

    따라서 모든 행렬은 유한 번의 elementary row operation을 통해 항상 RREF로 만들 수 있다. 또한 RREF는 유일하게 결정된다.

Theorem

Theorem. 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$

    어떤 행렬과 그 행렬의 RREF는 row-equivalent하고, Theorem 48에 의하면 두 행렬은 동일한 해집합을 가지므로 우리는 주어진 system of linear equations $Ax = b$를 RREF로 바꾸어서 풀어도 동일한 결과를 얻게 된다. RREF는 그 구조상 해를 구하기 매우 쉽게 설계되어 있는데, RREF로 바꿔서 푸는 $Ax = b$는 다음의 두 가지 종류의 변수로 나누어서 풀게 된다.

Basic and Free Variables

Definition 51. Among the variables in a system, the ones corresponding to the columns containing leading $1$'s in its RREF are called the basic variables, and the ones corresponding to the columns without leading $1$'s, if there are any, are called the free variables. 

   자명하게 basic variable과 free variable의 합은 전체 unknown의 개수이고 이는 곧 coefficient matrix의 행의 개수이다. 만약 모든 변수가 basic variable이라면 주어진 시스템은 어떤 모양이겠는가? 이는 모든 행에 leading $1$이 있다는 뜻이고, 그렇게 되기 위해서는 행과 열의 개수가 같아야 한다. 즉 coefficient matrix가 square란 뜻이고 이때 모든 행에 leading $1$이 있으려면 coefficient matrix는 identity이어야 한다. 이런 경우는 해가 딱 하나밖에 존재하지 않는다.

    반대로 임의의 system에 free variable이 하나라도 존재한다고 해보자. 만약 system이 consistent하다면 직관적으로 주어진 system은 무한히 많은 해를 가질 수 밖에 없음을 알 수 있다. 

Theorem 58

Theorem 58. Every system of linear equations having more unknowns than equations, i.e., having a wide coefficient matrix, has always infinitely many solutions.

    앞서 언급했듯이, 선형 연립 방정식은 RREF로 바꾸어서 주로 풀게 된다. 예시를 들어보자.

Example

$$\begin{cases} 2x_1 + 3x_2 + x_3 + 4x_4 - 9x_5 = 17 \\ x_1 + x_2 + x_3 + x_4 -3x_5 = 6 \\ x_1 + x_2 + x_3 + 2x_4 -5x_5 = 8 \\ 2x_1 + 2x_2 + 2x_3 + 3x_4 - 8x_5 = 14 \end{cases}$$ 다음과 같이 연립방정식이 주어졌다고 하자. 가우스 소거법을 적용하여 RREF로 변환하면 다음과 같다. $$\begin{bmatrix} A & b \end{bmatrix} = \begin{bmatrix} 2&3&1&4&-9&17 \\ 1&1&1&1&-3&6 \\ 1&1&1&2&-5&8 \\ 2&2&2&3&-8&14 \end{bmatrix} \sim \begin{bmatrix} 1&0&2&0&-2&3 \\ 0&1&-1&0&1&1 \\ 0&0&0&1&-2&2 \\ 0&0&0&0&0&0 \end{bmatrix} = \begin{bmatrix} A' b' \end{bmatrix}$$ 변환한 방정식을 새로 쓰면 다음과 같다. $$\begin{cases} x_1 + 2x_3 - 2x_5 = 3 \\ x_2 - x_3 + x_5 = 1 \\ x_4 - 2x_5 = 2 \end{cases}$$ 이제 free variable $x_3, x_5$에 매개변수 $t_1, t_2$를 부여하고 정리하면 다음과 같다. $$\begin{cases} x_1 = -2t_1 + 2t_2 + 3 \\ x_2 = t_1 - t_2 + 1 \\ x_4 = 2t_2 + 2 \end{cases}$$ Free variable은 그 이름과 같이 basic variable처럼 정확히 결정되지 않는 변수이므로 임의의 실수를 배정해도 된다. 따라서 방정식의 일반해는 다음과 같이 얻어진다. $$\begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{bmatrix} = \begin{bmatrix} -2t_1 + 2t_2 + 3 \\ t_1 - t_2 + 1 \\ t_1 \\ 2t_2 + 2 \\ t_2 \end{bmatrix} = \begin{bmatrix} 3 \\ 1 \\ 0 \\2 \\0 \end{bmatrix} + t_1 \begin{bmatrix} -2 \\ 1 \\ 1 \\ 0 \\ 0 \end{bmatrix} + t_2 \begin{bmatrix} 2 \\ -1 \\ 0 \\ 2 \\1 \end{bmatrix}, \text{ where } t_1, t_2 \in \mathbb{R}.$$ .