6.27 행 사다리꼴과 기약 행 사다리꼴

1. 사다리꼴 형태의 도입

행 사다리꼴(row echelon form, REF)과 기약 행 사다리꼴(reduced row echelon form, RREF)은 가우스 소거법과 가우스-조르단 소거법의 결과로 얻어지는 행렬의 표준 형태이며, 연립 일차 방정식의 해의 구조, 행렬의 랭크, 영 공간과 상 공간 등 많은 선형대수학적 개념을 직접 읽어낼 수 있게 한다. 본 절에서는 두 사다리꼴 형태의 정의, 그 유일성, 변환 절차, 그리고 로봇공학에서의 응용을 체계적으로 다룬다.

2. 행 사다리꼴의 정의

정의 6.27.1 (행 사다리꼴, REF). 행렬이 다음의 세 조건을 모두 만족할 때 행 사다리꼴이라 한다.

(REF1) 영행이 존재한다면 그 영행들은 모두 행렬의 가장 아래쪽에 위치한다.

(REF2) 비0 행에서 가장 왼쪽의 비0 성분(이를 선행 성분 또는 피벗이라 한다)은 그 위 행의 선행 성분보다 오른쪽에 위치한다.

(REF3) 한 행의 선행 성분 아래 같은 열의 모든 성분은 0이다.

세 번째 조건은 두 번째 조건으로부터 유도되므로, 본질적으로 (REF1)과 (REF2)가 정의의 핵심이다.

행 사다리꼴 행렬의 시각적 형태는 다음과 같다.

$\begin{bmatrix} \blacksquare & * & * & * & * & * \\ 0 & 0 & \blacksquare & * & * & * \\ 0 & 0 & 0 & \blacksquare & * & * \\ 0 & 0 & 0 & 0 & 0 & \blacksquare \\ 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}$

여기서 $\blacksquare$ 는 비0인 선행 성분(피벗)을, $*$ 는 임의의 값을 나타낸다.

기약 행 사다리꼴의 정의

정의 6.27.2 (기약 행 사다리꼴, RREF). 행 사다리꼴 행렬이 다음의 두 추가 조건을 만족할 때 기약 행 사다리꼴이라 한다.

(RREF1) 모든 선행 성분(피벗)이 1이다.

(RREF2) 각 선행 1의 위와 아래의 같은 열 성분은 모두 0이다.

기약 행 사다리꼴의 시각적 형태:

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

여기서 각 선행 1이 그 열의 유일한 비0 성분이다.

3. 사다리꼴 형태의 핵심 정리

정리 6.27.1 (RREF의 유일성). 임의의 행렬 $A$ 에 대해 행 연산으로 도달할 수 있는 RREF는 유일하다.

이는 매우 중요한 정리이다. 행 사다리꼴(REF)은 환원 절차의 선택에 따라 여러 형태가 가능하지만, RREF는 원래 행렬에 의해 유일하게 결정된다. 따라서 RREF는 행렬의 행 동치 클래스(row equivalence class)에서의 표준 대표(canonical representative) 역할을 한다.

정리 6.27.2. 두 행렬 $A$ 와 $B$ 가 같은 RREF를 가질 필요 충분 조건은 $A$ 와 $B$ 가 행 동치(row equivalent)인 것, 즉 한 행렬이 다른 행렬에 일련의 기본 행 연산을 적용하여 얻어질 수 있다는 것이다.

4. 사다리꼴 형태로의 변환

4.1 REF로의 변환 (가우스 소거법)

행렬 $A$ 를 REF로 변환하는 절차는 가우스 소거법의 전진 소거 단계와 동일하다.

첫 번째 비0 열에서 피벗을 선택한다.
피벗 행을 가장 위로 이동한다.
피벗 아래의 모든 성분을 0으로 만든다.
첫 번째 행과 첫 번째 열을 무시하고, 나머지 부분 행렬에 대해 같은 절차를 반복한다.

이 절차의 결과로 얻어지는 REF는 피벗의 정확한 값과 비0 성분의 값에서 환원 방식에 따라 차이가 있을 수 있지만, 피벗 위치(즉 비0 행과 비0 선행 열의 위치)는 동일하다.

4.2 RREF로의 변환 (가우스-조르단 소거법)

REF로 변환한 후, 다음의 추가 단계를 수행한다.

각 피벗을 그 행 전체로 나누어 1로 만든다.
각 피벗 위의 같은 열 성분을 0으로 만든다.

이 추가 단계는 가우스-조르단 소거법의 후진 단계이며, 결과는 유일한 RREF이다.

5. 피벗 열과 자유 열

정의 6.27.3 (피벗 열). RREF에서 피벗을 포함하는 열을 피벗 열(pivot column) 또는 기본 열(basic column)이라 하고, 그렇지 않은 열을 자유 열(free column)이라 한다.

대응하는 미지수를 각각 기본 변수(basic variable)와 자유 변수(free variable)라 한다. 자유 변수의 수는 시스템의 자유도이며, 해 공간의 차원과 같다.

6. 사다리꼴 형태와 시스템의 해

가우스 소거법 후의 REF 또는 RREF는 시스템의 해의 구조를 명시적으로 보여 준다.

6.1 해의 존재 판정

확장 행렬 $[A \mid \mathbf{b}]$ 의 RREF에서:

모순 행 ( $[0, 0, \ldots, 0 \mid c]$ with $c \neq 0$ )이 존재하면 시스템은 불일치이며 해가 없다.
모순 행이 없으면 시스템은 일관되며 적어도 하나의 해를 가진다.

6.2 유일 해와 무한 해

일관된 시스템에서:

모든 미지수에 대응하는 열이 피벗 열이면 (즉 자유 변수가 없으면) 시스템은 유일 해를 가진다.
자유 변수가 존재하면 시스템은 무한히 많은 해를 가지며, 해 공간은 (자유 변수의 수)차원의 아핀 부분 공간이다.

6.3 해의 매개변수 표현

자유 변수가 존재하는 경우, 자유 변수를 매개변수로 두고 기본 변수를 자유 변수의 함수로 표현한다. 이 매개변수 표현이 모든 해의 집합을 명시적으로 기술한다.

7. 계산 예시

다음의 시스템을 고려하자.

$\begin{aligned} x_1 + 2x_2 - x_3 + 3x_4 &= 4 \\ 2x_1 + 4x_2 - 2x_3 + 6x_4 &= 8 \\ x_1 + 2x_2 + x_3 + x_4 &= 6 \end{aligned}$

확장 행렬:

$\left[ \begin{array}{cccc|c} 1 & 2 & -1 & 3 & 4 \\ 2 & 4 & -2 & 6 & 8 \\ 1 & 2 & 1 & 1 & 6 \end{array} \right]$

소거 단계 1: $R_2 \to R_2 - 2 R_1$ , $R_3 \to R_3 - R_1$ :

$\left[ \begin{array}{cccc|c} 1 & 2 & -1 & 3 & 4 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & -2 & 2 \end{array} \right]$

행 교환: $R_2 \leftrightarrow R_3$ :

$\left[ \begin{array}{cccc|c} 1 & 2 & -1 & 3 & 4 \\ 0 & 0 & 2 & -2 & 2 \\ 0 & 0 & 0 & 0 & 0 \end{array} \right]$

이것이 REF이다. RREF로 변환하기 위해 두 번째 행을 2로 나누고, 첫 번째 행에서 두 번째 행을 더한다.

$R_2 \to (1/2) R_2$ :

$\left[ \begin{array}{cccc|c} 1 & 2 & -1 & 3 & 4 \\ 0 & 0 & 1 & -1 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{array} \right]$

$R_1 \to R_1 + R_2$ :

$\left[ \begin{array}{cccc|c} 1 & 2 & 0 & 2 & 5 \\ 0 & 0 & 1 & -1 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{array} \right]$

이것이 RREF이다. 1열과 3열이 피벗 열이며, 2열과 4열이 자유 열이다. 따라서 $x_2$ 와 $x_4$ 가 자유 변수이며, 해는 다음과 같이 매개변수화된다.

$x_1 = 5 - 2 x_2 - 2 x_4, \quad x_3 = 1 + x_4$

$\mathbf{x} = \begin{bmatrix} 5 \\ 0 \\ 1 \\ 0 \end{bmatrix} + x_2 \begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix} + x_4 \begin{bmatrix} -2 \\ 0 \\ 1 \\ 1 \end{bmatrix}$

해 공간은 2차원 아핀 부분 공간이다.

8. 사다리꼴 형태로부터 추출되는 정보

RREF는 다음의 행렬 정보를 직접 제공한다.

8.1 랭크

행렬의 랭크는 RREF에서 비0 행의 수와 같다. 동치적으로 피벗의 수와 같다.

$\text{rank}(A) = \text{(피벗의 수)}$

영 공간의 기저

자유 변수에 대해 한 변수만 1이고 나머지가 0인 값을 대입하여 얻은 해 벡터들이 영 공간의 기저를 이룬다. 위의 예시에서 영 공간 $\text{Null}(A)$ 는 다음 두 벡터로 생성된다.

$\left\{ \begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix}, \begin{bmatrix} -2 \\ 0 \\ 1 \\ 1 \end{bmatrix} \right\}$

8.2 열 공간의 기저

원래 행렬 $A$ 의 열 중 RREF의 피벗 열에 해당하는 열들이 $A$ 의 열 공간 $\text{Col}(A)$ 의 기저를 이룬다. 주의: RREF의 피벗 열 자체가 아니라 원래 행렬의 해당 열을 사용해야 한다.

8.3 행 공간의 기저

RREF의 비0 행이 $A$ 의 행 공간의 기저를 이룬다. 행 연산은 행 공간을 보존하므로 RREF의 행이 그대로 사용 가능하다.

8.4 차원 정리

피벗의 수와 자유 변수의 수의 합은 행렬의 열의 수와 같다.

$\text{rank}(A) + \text{nullity}(A) = n$

이를 랭크-널리티 정리(rank-nullity theorem)라 한다.

일반화된 사다리꼴 개념

헤르미트 표준형

RREF는 실수 또는 유리수 행렬에 대한 표준형이지만, 정수 행렬에 대해서는 헤르미트 표준형(Hermite normal form)이 유사한 역할을 한다. 정수 행 연산만 사용하여 변환된다.

스미스 표준형

행 연산과 열 연산을 모두 허용하면 스미스 표준형(Smith normal form)이 얻어지며, 이는 정수 행렬의 더 강한 표준형이다.

로봇공학에서의 응용

자코비안의 랭크 결정과 특이점 식별

매니퓰레이터 자코비안 $J(\mathbf{q})$ 의 랭크는 현재 자세에서 도달 가능한 작업 공간 자유도의 수를 나타낸다. 자코비안을 사다리꼴로 환원하여 그 랭크를 결정할 수 있으며, 랭크가 작업 공간 차원보다 작으면 특이 형상에 있음을 의미한다.

영 공간의 명시적 계산

여유 자유도 로봇에서 자코비안의 영 공간은 말단 장치의 자세를 변경하지 않는 내부 운동(self-motion)을 표현한다. 사다리꼴 환원을 통해 영 공간의 기저를 명시적으로 계산하고, 이를 활용하여 부차 목표(예: 장애물 회피, 관절 한계 회피)를 최적화할 수 있다.

강체 변환의 일관성 검증

다중 강체 시스템의 폐연쇄 제약 조건은 동차 변환 행렬의 곱이 항등 행렬이 되어야 함을 요구한다. 이러한 제약 조건을 선형화한 시스템의 사다리꼴 환원을 통해 일관성과 자유도를 결정할 수 있다.

칼만 필터의 관측 가능성 분석

선형 시스템의 관측 가능성 행렬

$\mathcal{O} = \begin{bmatrix} C \\ CA \\ CA^2 \\ \vdots \\ CA^{n-1} \end{bmatrix}$

의 랭크는 시스템이 완전 관측 가능한지 판정한다. 사다리꼴 환원을 통해 랭크를 결정하고, 관측 불가능한 부공간을 명시적으로 식별할 수 있다.

8.5 제약 조건이 있는 최적화

KKT 조건의 등호 제약 부분이 정의하는 선형 시스템의 사다리꼴 환원은 활성 집합 알고리즘과 등호 제약 이차 계획법의 핵심 단계이다.

8.6 그래프 SLAM의 변수 의존성 분석

SLAM의 인수 그래프에서 측정으로부터 결정되지 않는 변수(예: 전역 자세의 절대 위치)를 식별할 때 정보 행렬의 사다리꼴 환원이 사용된다. 0인 피벗 또는 자유 변수에 대응하는 부공간이 게이지 자유도(gauge freedom)를 나타낸다.

8.7 컴퓨터 비전의 호모그래피 추정

호모그래피의 직접 선형 변환(DLT) 방법은 측정으로부터 구성된 행렬을 사다리꼴로 환원하여 호모그래피의 매개변수를 결정한다. 이 과정에서 선형 종속성과 자유도의 분석이 수행된다.

참고문헌

Strang, G. (2023). Introduction to Linear Algebra (6th ed.). Wellesley-Cambridge Press.
Axler, S. (2024). Linear Algebra Done Right (4th ed.). Springer.
Golub, G. H., & Van Loan, C. F. (2013). Matrix Computations (4th ed.). Johns Hopkins University Press.
Anton, H., & Rorres, C. (2014). Elementary Linear Algebra (11th ed.). Wiley.

Version: 1.0