행간소사다리꼴(Reduced Row Echelon Form)

행간소사다리꼴(Reduced Row Echelon Form)이란?

행간소사다리꼴은 행렬 중 특정 조건들을 만족하는 행렬들을 일컫는 용어이다. 즉, 다양한 형태의 행렬 중에 “이 조건을 만족하면 너는 RREF야 “라고 정의 내리는 것이다.

아래 내용이 어떤 행렬이 행간소사다리꼴로 불리기 위해 필요한, 행간소사다리꼴의 정의 이다.

정의 다음 세 조건을 만족하는 행렬을 행간소사다리꼴 또는 기약행사다리꼴(reduced row echelon form)이라 한다.

1.0이 아닌 성분을 가지는 행은 모든 성분이 0인 행보다 위에 위치한다(모든 성분이 0인 행이 존재하지 않을 수 도 있다)

2.각 행의 처음으로 0이 아닌 성분은 그 성분을 포함한 열에서 유일하게 0이 아닌 성분이다.

3.각 행의 처음으로 0이 아닌 성분은 1이고, 이전 행의 처음으로 0이 아닌 성분보다 오른쪽에 위치한다.
- 스티븐 H.프리드버그 외 2명, 『프리드버그 선형대수학 5판』, 210p, 한빛 아카데미(2020)

사실 위 정의만으로는 어떤 행렬을 보고 행간소사다리꼴이라고 하는지 짐작하기는 쉽지 않은 것 같다. 먼저 행간소사다리꼴의 예시를 보자.

\[\begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}\]

위 행렬을 행렬 A라 하면, A가 바로 바로 행간소사다리꼴의 예시이다. 정의와 매치시켜서 보면 조금 더 이해하기가 쉬울 것 같다.

• “0이 아닌 성분을 가지는 행” : A에서는 모든 행이 0이 아닌 성분을 가진다, 따라서 3개의 행 모두 이 행에 해당된다.

• “모든 성분이 0인 행보다 위에 위치한다” :모든 성분이 0인 행렬은$\left( 0 \ 0 \ 0 \ 0 \right)$ 처럼 특정 행의 모든 원소가 0인 행을 의미한다. A 행렬에는 존재하지 않고, 이 행렬이 있다해도, 가장 1번 조건에 만족하는 행보다는 아래 쪽에 있어야 행간소사다리꼴이다

• “각 행의 처음으로 0이 아닌 성분은 그 성분을 포함한 열에서 유일하게 0이 아닌 성분이다” : A에서는 1행의 처음으로 0이 아닌 성분이 1로써 1열에 있다. 1열에는 이 1을 제외하곤 전부 0이므로 이 조건에 만족한다. 2행의 처음으로 0이 아닌 성분은$A_{22}$성분에 해당하는 1인데, 2열에는 $A_{22}$을 제외하고는 전부 0이므로 역시 이조건에 만족한다.

• “각 행의 처음으로 0이 아닌 성분은 1이고” : 각 행별로 왼쪽에서 오른쪽으로 훑어보면서 처음으로 0이 아닌 성분을 찾아봤을 때, 모두 1이어야 한다. A는 모두 1이므로 이 조건을 만족한다.

• “이전 행의 처음으로 0이 아닌 성분보다 오른쪽에 위치한다” : 말로 하면 어려운데, 각 행별로 처음으로 0이 아닌 성분이 왼쪽에서 오른쪽으로 비스듬히 위치해야 한다.

여기까지도 사실 어떤 형태인지 감이 안올 수 있으므로, 행간소사다리꼴이 아닌 형태를 보자.

\[\begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix}\]

위 행렬은 (3,1)에 위치한 1 이 3번 조건에 어긋난다. 1행에서 처음으로 0이 아닌 성분은 (1,1)에 위치한 1 하나만 있어야 하는데, (1,3)에 위치한 1이 이를 망쳤다.

\[\begin{pmatrix} 0 & 1 & 0 & 2 \\ 1 & 0& 0 & 1 \\ 0 & 0 & 1 & 1 \end{pmatrix}\]

위 행렬은 (2,1)에 위치한 1이 5번 조건에 위배 된다. 1행에서 처음으로 0이 아닌 성분이 (1,2)에 위치한 1이므로, 이보다 왼쪽에 1이 위치하면 행간소사다리꼴이라 할 수 없다.

\[\begin{pmatrix} 2 & 1 & 0\\ 0 & 1& 0 \end{pmatrix}\]

위 행렬은 4번 조건에 위배 된다. (1,1)에 위치한 2는 1행에서 처음으로 0이 아닌 성분이므로 1이어야 하는데 2이므로 아웃이다.

왜 행간소사다리꼴을 알아야 되지?

행간소사다리꼴이 어떤 형태인지 충분히 이해 됬다면, 도대체 이 행간소사다리꼴을 왜 알아야 하는지도 공부해보자.

\[\begin{array}{lcl} 3x_1 + 2x_2 + 3x_3 - 2x_4 & = & 1 \\ x_1 + x_2 + x_3 & = & 3 \\ x_1 + 2x_2 + x_3 - x_4 & = & 2 \end{array}\]

위와 같은 형태는 쉽게 볼 수 있는 연립 일차 방정식(system of linear equations)이다. 위 연립 일차 방정식은 방정식의 계수로 된 행렬과 미지수들로 구성되어 있는 벡터의 곱으로 나타낼 수도 있는데 이는 아래와 같다.

\[A\mathbf{x = b}, \ A = \begin{pmatrix} 3 & 2 & 3 & -2 \\ 1 & 1 & 1 & 0 \\ 1 & 2 & 1 & -1 \ \end{pmatrix} , \mathbf{x} = \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix} , \mathbf{b} = \begin{pmatrix} 1 \\ 3 \\ 2 \\ \end{pmatrix}\]

우선 이 연립일차 방정식의 해가 rank(A) 와 rank(A|b) 같은지를 체크하여 해가 존재하는 지를 확인해 보자(해의 존재를 확인하기 위해 rank(A) 와 rank(A|b) 같은지를 확인하는 이유는 간단하다. 해가 존재 한다는 것은 $A\mathbf{x = b}$ 를 A의 column vector 들과 $\mathbf{x}$ 의 선형결합이 $R(L_A)$ 에 존재한다는 것과 동일하기 때문이다. rank(A) = 3이고, rank(A|b) = 3 이므로, 해가 존재하는 것을 알 수 있다. 보통 이러한 연립 일차 방정식을 풀기 위해서는 손으로 풀어도 상당히 번거로운 계산을 해야 하지만, 이 행렬을 행간소사다리꼴로 만든다면 어떨까?

우선 아래와 같은 사실들을 미리 알고 있어야 한다.

• 모든 행렬은 가우스 소거법(Gaussian Elimination)을 사용하여 행간소사다리꼴로 만들 수 있다.
• 주어진 행렬의 행간소사다리꼴은 유일하다.

행렬(augmented matrix) A|b의 행간소사다리꼴은 아래와 같다.

\[\left( \begin{array}{cccc|c} 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 3 \\ 0 & 0 & 0 & 1 & 2 \end{array} \right)\]

그리고 이 행렬은 다음 연립 일차 방정식에 대응한다.

\[\begin{array}{lcl} x_1 + x_3 & = & 1 \\ x_2 & = & 3 \\ x_4 & = & 2 \ \end{array}\]

원래 형태보다 행간소사다리꼴의 해를 구하는 것이 계산의 복잡성에서 확연하게 차이가 나는 것을 알 수 있다. 책의 내용을 인용해 정확하게 표현하자면

이러한 효율성 때문에 컴퓨터로 연립 일차 방정식을 풀 때 가우스 소거법을 선호한다.
- 스티븐 H.프리드버그 외 2명, 『프리드버그 선형대수학 5판』, 211p, 한빛 아카데미(2020)

행간소사다리꼴의 활용

$A\mathbf{x}=\mathbf{b}$의 일반해는 $A\mathbf{x}=\mathbf{b}$의 해집합의 원소와 $A\mathbf{x}=\mathbf{0}$의 해집합의 선형결합으로 표현할 수 있다. 즉, $A\mathbf{x}=\mathbf{b}$의 해를 이에 대응하는 동차 연립일차방정식의 해와 $A\mathbf{x}=\mathbf{b}$의 해의 합으로 표현할 수 있다는 뜻이다.

이는 행렬 A와 이에 대응하는 left multiplication transformation $L_A$를 생각해보면 이해가 가능하다. $A\mathbf{x}=\mathbf{b}$의 해가 존재한다는 것은 $L_A(\mathbf{x}) = A\mathbf{x} \in R(L_A)$를 의미한다. m * n 행렬 A의 j번째 열을 $a_j$이라 할 때, $A\mathbf{x}$는 곧 $x_1a_1 + … + x_na_n$ 에 대응하는 $\mathbf{b}$가 치역에 존재한다는 뜻이기 때문이다. 또, $A\mathbf{x} = 0$의 해는 $L_A$의 kernel의 원소와 동일하다.

rank와 nullity의 관계를 설명해주는 차원 정리(dimension theorem)에 의하면, 정의역의 차원을 n이라 할 때, rank + nullity = n이 성립한다. 이는 연립일차방정식의 해로 생각하면 $A\mathbf{x}=\mathbf{b}$의 차원(rank) + $A\mathbf{x}=\mathbf{0}$의 차원(nullity) = n의 관계로 생각해볼 수 있다.

위 내용을 담은 증명이 아래와 같다.

Theorem $A\mathbf{x}=b$를 n 개의 미지수와 r개의 영이 아닌 방정식으로 이루어진 연립일차방정식이라하자. $rank(A) = rank(A|b)$이고 (A|b)가 행간소사다리꼴이면 다음이 성립한다.

1. $rank(A)$ = r
2. 앞선 과정을 거쳐 얻은 일반해가 다음과 같은 꼴이라 하자. \(s = s_0 + t_1u_1 + t_2u_2 + \cdots + t_{n-r}u_{n-r}\) 이 때, ${u_1, u_2, … , u_{n-r}}$는 대응하는 동차 연립일차방정식의 해집합의 기저이고, $s_0$은 처음 연립일차방정식의 해이다.

위 정리에서 $s_0$은 비동차 연립일차방정식의 해이다. 동차 연립일차방정식의 해집합의 차원이 n-r인 이유는 앞에서 설명한 바와 같이 차원 정리에 의해서다.

이정도면 행간사다리꼴 공부한 내용은 얼추 정리가 된 것 같다. 후!

Reference - 스티븐 H.프리드버그, 아놀드 J.인셀, 로렌스 E, 스펜스, 『프리드버그 선형대수학 5판』,한빛 아카데미(2020)