27.26 삼각 행렬(Triangular Matrix)의 구조와 연립방정식 풀이

1. 삼각 행렬의 정의

삼각 행렬(triangular matrix)은 주대각선의 한쪽에 있는 원소가 모두 0인 정사각 행렬이다. 두 가지 유형으로 나뉜다.

상삼각 행렬(Upper Triangular Matrix): 주대각선 아래의 모든 원소가 0인 행렬이다. $n \times n$ 상삼각 행렬 $\mathbf{U}$ 는 다음 조건을 만족한다.

$u_{ij} = 0 \quad \text{for } i > j$

$\mathbf{U} = \begin{pmatrix} u_{11} & u_{12} & u_{13} & \cdots & u_{1n} \\ 0 & u_{22} & u_{23} & \cdots & u_{2n} \\ 0 & 0 & u_{33} & \cdots & u_{3n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & u_{nn} \end{pmatrix}$

하삼각 행렬(Lower Triangular Matrix): 주대각선 위의 모든 원소가 0인 행렬이다. $n \times n$ 하삼각 행렬 $\mathbf{L}$ 은 다음 조건을 만족한다.

$l_{ij} = 0 \quad \text{for } i < j$

$\mathbf{L} = \begin{pmatrix} l_{11} & 0 & 0 & \cdots & 0 \\ l_{21} & l_{22} & 0 & \cdots & 0 \\ l_{31} & l_{32} & l_{33} & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ l_{n1} & l_{n2} & l_{n3} & \cdots & l_{nn} \end{pmatrix}$

상삼각 행렬의 전치는 하삼각 행렬이고, 하삼각 행렬의 전치는 상삼각 행렬이다. 즉, $\mathbf{U}^\top$ 은 하삼각이고 $\mathbf{L}^\top$ 은 상삼각이다. 대각 행렬은 상삼각이면서 동시에 하삼각인 행렬이다.

삼각 행렬의 독립적인 원소 수는 주대각선 포함 $n(n+1)/2$ 개이며, 이는 일반 정사각 행렬의 $n^2$ 개에 비해 약 절반이다.

2. 삼각 행렬의 대수적 성질

삼각 행렬은 행렬 연산에 대하여 다음의 닫힘 성질을 가진다.

곱셈에 대한 닫힘: 두 상삼각 행렬의 곱은 상삼각 행렬이다. $\mathbf{U}_1$ 과 $\mathbf{U}_2$ 가 모두 상삼각이면, $(\mathbf{U}_1\mathbf{U}_2)_{ij} = \sum_{k=1}^{n} (u_1)_{ik}(u_2)_{kj}$ 에서 $i > k$ 이면 $(u_1)_{ik} = 0$ 이고, $k > j$ 이면 $(u_2)_{kj} = 0$ 이므로, $i > j$ 이면 모든 항이 0이 된다. 하삼각 행렬에 대해서도 동일한 성질이 성립한다.

행렬식: 삼각 행렬의 행렬식은 주대각선 원소의 곱이다.

$\det(\mathbf{U}) = \prod_{i=1}^{n} u_{ii}, \quad \det(\mathbf{L}) = \prod_{i=1}^{n} l_{ii}$

이는 행렬식의 여인자 전개(cofactor expansion)를 첫 번째 열(하삼각) 또는 첫 번째 행(상삼각)에 대해 반복 적용하면 직접 도출된다.

고유값: 삼각 행렬의 고유값은 주대각선 원소이다. 특성 다항식 $\det(\mathbf{U} - \lambda\mathbf{I}) = \prod_{i=1}^{n}(u_{ii} - \lambda)$ 이므로, 고유값은 $\lambda_i = u_{ii}$ 이다.

역행렬: 모든 대각 원소가 0이 아닌 삼각 행렬은 가역이며, 그 역행렬도 같은 유형의 삼각 행렬이다. 상삼각 행렬의 역행렬은 상삼각이고, 하삼각 행렬의 역행렬은 하삼각이다.

단위 삼각 행렬: 주대각선 원소가 모두 1인 삼각 행렬을 단위 삼각 행렬(unit triangular matrix)이라 한다. 단위 삼각 행렬의 행렬식은 1이며, LU 분해에서 $\mathbf{L}$ 은 일반적으로 단위 하삼각 행렬로 정규화된다.

3. 전방 대입법(Forward Substitution)

하삼각 행렬 시스템 $\mathbf{L}\mathbf{x} = \mathbf{b}$ 를 풀기 위해 전방 대입법을 사용한다. 연립방정식을 전개하면 다음과 같다.

$\begin{aligned} l_{11}x_1 &= b_1 \\ l_{21}x_1 + l_{22}x_2 &= b_2 \\ l_{31}x_1 + l_{32}x_2 + l_{33}x_3 &= b_3 \\ &\vdots \\ \sum_{j=1}^{n} l_{nj}x_j &= b_n \end{aligned}$

첫 번째 방정식에서 $x_1 = b_1 / l_{11}$ 을 직접 구하고, 이를 두 번째 방정식에 대입하여 $x_2$ 를 구하는 식으로 순차적으로 진행한다. 일반적인 공식은 다음과 같다.

$x_i = \frac{1}{l_{ii}}\left(b_i - \sum_{j=1}^{i-1} l_{ij}x_j\right), \quad i = 1, 2, \ldots, n$

이 알고리즘에서 $x_i$ 를 구하기 위해 $(i-1)$ 번의 곱셈과 $(i-1)$ 번의 뺄셈, 1번의 나눗셈이 필요하다. 전체 연산 횟수는 다음과 같다.

$\sum_{i=1}^{n}(2(i-1) + 1) = n^2$

따라서 전방 대입법의 시간 복잡도는 $O(n^2)$ 이다.

4. 후방 대입법(Back Substitution)

상삼각 행렬 시스템 $\mathbf{U}\mathbf{x} = \mathbf{b}$ 를 풀기 위해 후방 대입법을 사용한다. 마지막 방정식에서 $x_n = b_n / u_{nn}$ 을 구하고, 역순으로 진행한다.

$x_i = \frac{1}{u_{ii}}\left(b_i - \sum_{j=i+1}^{n} u_{ij}x_j\right), \quad i = n, n-1, \ldots, 1$

후방 대입법의 시간 복잡도도 전방 대입법과 동일하게 $O(n^2)$ 이다. 이는 일반 행렬에 대한 연립방정식 풀이의 $O(n^3)$ 복잡도에 비해 한 차수 낮으며, 삼각 행렬의 구조적 이점을 잘 보여준다.

5. 삼각 행렬과 행렬 분해

삼각 행렬은 다양한 행렬 분해 기법의 핵심 구성 요소이다.

LU 분해: 행렬 $\mathbf{A}$ 를 하삼각 행렬 $\mathbf{L}$ 과 상삼각 행렬 $\mathbf{U}$ 의 곱 $\mathbf{A} = \mathbf{L}\mathbf{U}$ 로 분해한다. 연립방정식 $\mathbf{A}\mathbf{x} = \mathbf{b}$ 는 $\mathbf{L}\mathbf{U}\mathbf{x} = \mathbf{b}$ 로 변환되며, $\mathbf{L}\mathbf{y} = \mathbf{b}$ (전방 대입)와 $\mathbf{U}\mathbf{x} = \mathbf{y}$ (후방 대입)의 두 단계로 풀 수 있다. LU 분해 자체의 복잡도는 $O(n^3/3)$ 이지만, 분해를 한 번 수행한 후에는 다른 우변 벡터 $\mathbf{b}$ 에 대해 $O(n^2)$ 만으로 해를 구할 수 있다.

촐레스키 분해(Cholesky Decomposition): 대칭 양의 정부호(symmetric positive definite) 행렬 $\mathbf{A}$ 에 대하여 $\mathbf{A} = \mathbf{L}\mathbf{L}^\top$ 으로 분해한다. 여기서 $\mathbf{L}$ 은 양의 대각 원소를 가지는 하삼각 행렬이다. 촐레스키 분해의 연산량은 LU 분해의 약 절반인 $O(n^3/6)$ 이며, 수치적으로도 더 안정적이다.

QR 분해: 행렬 $\mathbf{A}$ 를 직교 행렬 $\mathbf{Q}$ 와 상삼각 행렬 $\mathbf{R}$ 의 곱 $\mathbf{A} = \mathbf{Q}\mathbf{R}$ 로 분해한다. 최소 제곱 문제나 고유값 알고리즘에서 핵심적으로 사용된다.

6. 딥러닝에서의 삼각 행렬 활용

삼각 행렬 구조는 딥러닝의 여러 영역에서 활용된다.

정규화 흐름(Normalizing Flows): 정규화 흐름에서 야코비안 행렬식의 효율적 계산이 필수적이다. 삼각 야코비안 구조를 가지는 변환을 설계하면, 행렬식이 대각 원소의 곱으로 환원되어 $O(n)$ 에 계산할 수 있다. 자기회귀 흐름(autoregressive flow)과 커플링 흐름(coupling flow) 모두 이 원리를 활용한다. 구체적으로, 자기회귀 변환 $y_i = f_i(x_1, \ldots, x_i)$ 의 야코비안은 하삼각 행렬이 되어 $\log \lvert \det \mathbf{J} \rvert = \sum_{i=1}^{n} \log \lvert \partial f_i / \partial x_i \rvert$ 로 계산된다.

인과적 어텐션 마스크(Causal Attention Mask): 트랜스포머의 디코더에서 사용되는 인과적 마스크는 하삼각 행렬 구조를 가진다. 위치 $i$ 의 토큰이 위치 $j \leq i$ 의 토큰에만 주의(attend)할 수 있도록 상삼각 부분을 $-\infty$ 로 설정한다. 이는 자기회귀적 생성(autoregressive generation)의 조건부 독립 구조를 행렬 형태로 강제하는 것이다.

수치 안정성: 역전파에서 기울기 계산 과정의 수치적 안정성을 위해 삼각 분해가 활용된다. 촐레스키 분해는 가우시안 과정(Gaussian process) 모델에서 공분산 행렬의 역행렬과 행렬식을 동시에 효율적으로 계산하는 표준 기법이다. $\log\det(\mathbf{K}) = 2\sum_{i=1}^{n}\log l_{ii}$ 로 계산하면 수치적 오버플로를 방지할 수 있다.