누가 뭐라고 하더라도 행렬(行列, Matrix) 이론이 시작되고 행렬이 강점을 발하는 분야는 연립 방정식(聯立方程式, simultaneous equations or system of linear equations)의 체계적인 해법이다. 예를 들어 아래와 같은 3원 1차 연립 방정식의 해를 행렬로 구하자.
(1)
여기서 값을 모르는 원소(元素, element) 혹은 변수(變數, variable)가 세 개이므로 3원(元)이다. 식 (1)에 나온 미지수 $x, y, z$를 풀기 위해 다음과 같은 행렬을 만든다.
(2)
식 (2)를 풀 때 손쉬운 방법은 다음처럼 역행렬(inverse matrix)을 구해서 행렬 곱을 계산하면 된다.
(3)
하지만 식 (3)이 연립 방정식을 푸는 효과적인 방법일까? 식 (3)에는 복잡한 연산이 필요한 역행렬이 있고 계산 시간을 늘리는 행렬 곱이 있다. 식 (3)과는 다르지만 쉽고 빠른 연립 방정식 풀이법이 있을까? 이러한 기초적인 의문에 효과적인 대답이 가우스 소거법(Gaussian elimination) 혹은 행 줄임(row reduction)이다. 가우스 소거법을 식 (2)에 적용하면 다음과 같은 사다리꼴 형태(echelon form)로 만들 수 있다.
(4)
식 (4)에 의해 미지수 $x, y, z$는 다음처럼 간략히 표현된다.
(5)
식 (2)로 표현한 행렬을 식 (4)처럼 만들기 위해서 가우스 소거법은 다음 세 가지의 기본 행 연산(elementary row operation)을 반복해서 사용한다.
(6)
여기서 $a_{in} + c a_{jn}$ = $0$, $c = - a_{in}/a_{jn}$이다. 식 (6)에 등장하는 기본 행 연산이 $e^{(m)}$과 $e^{(a)}$이다. 또한 곱하는 행이 항상 다르기 때문에, 연산 $e^{(m)}$과 $e^{(a)}$는 서로 같을 수 없다. 다음과 같은 계산 절차를 사용하면, $e^{(s)}$를 $e^{(m)}$과 $e^{(a)}$로 만들 수 있다[1]. 우리가 교환하고 싶은 행 번호가 $i, j$라면, 다음과 같은 순서로 기본 행 연산을 반복해서 $e^{(s)}$를 만들 수 있다.
기본 행 연산을 수학적으로 더 세련되게 다루려면, 기본 행 연산을 행렬로 표현해야 한다. 이를 위해 $i$번째 기본 행 연산 $e_i$에 해당하는 기본 행렬(elementary matrix)을 ${\bf E}_i$라 하자. 그러면 가우스 소거법을 행렬로 처리하기 위한 다음 관계가 성립한다.
(7)
물론 식 (7)처럼 표기한다고 그 관계가 성립된다는 뜻은 아니다. 연산 $e^{(m)}$과 $e^{(a)}$에 대해 식 (7)을 하나씩 증명해야 한다. 연산 $e^{(s)}$는 $e^{(m)}$과 $e^{(a)}$의 결합이기 때문에 따로 증명할 필요는 없다. 먼저 $e^{(m)}$에 대한 ${\bf E}^{(m)}$의 원소(element)를 $E_{ij}^{(m)}$라 한다. 그러면 $n$번째 행에 대한 행 곱하기 연산 $e^{(m)}$은 다음과 같다.
(8)
여기서 $\delta_{ij}$는 크로네커 델타(Kronecker delta)이다. 크로네커 델타는 $i$ = $j$이면 $1$, 아니면 $0$이 된다. 식 (8)을 식 (7)에 대입해 행렬 곱 ${\bf E}^{(m)} {\bf A}$의 원소를 구하면 다음 관계를 얻는다.
(9)
여기서 ${\bf A}$의 원소는 $a_{ij}$이다. 마찬가지로 $l$번째 행에 $c$를 곱해 $n$번째 행에 더하는 행 더하기 연산 $e^{(a)}$도 행렬로 표현할 수 있다.
(10)
여기서 $e^{(a)}$에 대한 ${\bf E}^{(a)}$의 원소는 $E_{ij}^{(a)}$이다. 행렬 곱 ${\bf E}^{(a)} {\bf A}$의 결과는 다음과 같다.
(11)
또한 행 바꾸기 연산 $e^{(s)}$를 위한 기본 행렬 ${\bf E}^{(s)}$의 원소 $E_{ij}^{(s)}$도 다음처럼 기술한다.
(12)
식 (12)에 나오는 크로네커 델타 $\delta_{ij}$는 $i,j$를 바꿀 수 있으므로, ${\bf E}^{(s)}$ = $({\bf E}^{(s)})^T$가 성립해서 ${\bf E}^{(s)}$는 대칭 행렬(symmetric matrix)이 된다. 이를 종합하면, 기본 행 연산을 식 (7)과 같은 기본 행렬로 항상 표현할 수 있다. 또한 행 바꾸기 연산 $e^{(s)}$는 $e^{(m)}$과 $e^{(a)}$의 기본 행렬의 곱으로도 나타낼 수 있다.
(13)
최종적으로 식 (4)에 제시한 상삼각 행렬(upper triangular matrix) ${\bf U}$를 만들기 위한 가우스 소거법을 기본 행렬의 유한 곱으로 멋있게 표현할 수 있다.
(14)
여기서 $r$은 기본 행 연산을 적용한 회수이다. 행렬식(determinant)의 정의 혹은 행렬식은 방향성 있는 부피 개념에 따라 기본 행렬의 행렬식도 구해본다.
(15)
기본 행렬의 행렬식은 $0$이 아니므로 역행렬(inverse matrix)이 항상 존재한다. 기본 행렬의 역행렬은 기본 행 연산의 역연산 관점으로 쉽게 이해할 수 있다. 우리가 기본 행렬의 행렬식을 계산하지 않더라도, 행 곱하기, 행 더하기, 행 바꾸기는 당연히 역연산이 존재하므로 기본 행렬의 역행렬은 반드시 존재함을 바로 알 수 있다. 그러므로 기본 행렬 ${\bf E}^{(m)}$과 ${\bf E}^{(a)}$의 역행렬인 $({\bf E}^{(m)})^{-1}$과 $({\bf E}^{(a)})^{-1}$은 행렬 원소를 다음처럼 정의할 수 있다.
(16)
(17)
여기서 $n$은 기본 행 연산을 적용한 행 번호이다. 행렬 ${\bf E}^{(s)}$의 역행렬은 식 (12)처럼 $({\bf E}^{(s)})^{-1}$ = ${\bf E}^{(s)}$이다.
행렬 이론에서 가장 중요한 분해법인 LU 분해(lower–upper decomposition) 혹은 LU 인수 분해(lower–upper factorization)는 식 (14)를 이용해서 아래처럼 증명할 수 있다.
[LU 분해]
행렬 ${\bf A}$의 모든 선행 주부분 행렬(leading principal submatrix)의 행렬식이 $0$이 아니면, 다음 분해를 만족하는 행렬 ${\bf L}, {\bf U}$는 유일하게 존재한다.
(18)
여기서 ${\bf L}$은 대각선 원소가 모두 $1$인 하삼각 행렬(lower triangular matrix), ${\bf U}$는 대각선 원소가 $0$이 아닌 상삼각 행렬이다.
[증명]
가우스 소거법을 적용해 식 (14)처럼 ${\bf A}$를 ${\bf U}$로 바꾼다. 기본 행렬의 행렬식은 항상 0이 아니므로, 식 (14)의 좌변과 우변에 기본 행렬의 역행렬을 계속 적용해서 다음 관계식을 얻는다.
(19)
여기서 $r$은 기본 행렬을 만든 회수이다. 행렬 ${\bf L}$의 특성을 이해하기 위해 기본 행렬을 살펴본다. 기본 행렬 ${\bf E}^{(m)}$은 대각 행렬(diagonal matrix)이므로 특이한 점은 없다. 기본 행렬 ${\bf E}^{(a)}$는 식 (10)으로 인해 항상 하삼각 행렬이다. 이 특성을 간단히 증명해본다. 가우스 소거법을 적용해서 상삼각 행렬 ${\bf U}$를 만들고 있는 중이므로[∵ 대각선 원소의 아래쪽을 0으로 만들어야 상삼각 행렬], $l$번째 행에 $c$를 곱해 더해주는 행 번호인 $n$은 $n > l$이 성립한다. 따라서 행 더하기인 식 (10)으로 인해 대각선 원소[대각선 열 번호는 $n$]의 왼쪽 위치[$l < n$]에 원소 $c$가 생긴다. 이 성질은 ${\bf E}^{(a)}$가 하삼각 행렬임을 의미한다. 또한 행렬 곱 관점으로 보면, 하삼각 행렬끼리는 서로 곱하더라도 항상 하삼각 행렬이다. 마찬가지로 하삼각 행렬의 역행렬도 하삼각 행렬이다. 예를 들어, 어떤 하삼각 행렬 ${\bf T}_l$의 역행렬 ${\bf T}_l^{-1}$을 만들려면 식 (14)처럼 상삼각 행렬을 만드는 기본 행 연산을 적용하면 된다.
(20)
여기서 ${\bf I}$는 항등 행렬(identity matrix)이다. 그러면 ${\bf U}$를 만드는 기본 행렬의 곱은 항상 하삼각 행렬이다. 이 모든 고찰을 합치면, 식 (19)에 정의한 ${\bf L}$은 필연적으로 하삼각 행렬이다. 추가적으로 ${\bf L}$의 대각선 원소가 $1$이 아닐 수도 있다. 이때는 ${\bf L}$의 대각선 원소를 가지는 대각 행렬 ${\bf D}$를 정의해서 ${\bf L}$을 다음처럼 분해한다. 그러면 대각선 원소가 $1$인 ${\bf L}'$과 그 짝인 ${\bf U}'$으로 분해할 수 있다.
(21)
식 (21)에 의해 LU 분해의 존재성(existence)이 증명되었으므로, LU 분해의 유일성(uniqueness)을 살펴보자. 먼저 선행 주부분 행렬(leading principal submatrix)을 정의하자. 주부분 행렬(principal submatrix)은 특정 행이나 열을 지워서 만든 정방 행렬(square matrix)이다. 행렬의 좌측 상단(upper left)을 시작점으로 1행 1열로 구성한 가장 작은 주부분 행렬에서 행렬의 차원(matrix dimension)을 하나씩 키워서 원래 행렬까지 커지는 주부분 행렬 중의 하나를 선행 주부분 행렬이라 한다. 더 쉬운 말로 선행 주부분 행렬을 좌측 상단 주부분 행렬(upper left principal submatrix)이라 할 수 있다. 즉 좌측 상단 원소를 항상 포함하는 주부분 행렬이 선행 주부분 행렬이다. 예를 들어 식 (2)에 있는 $\bf A$의 모든 선행 주부분 행렬은 다음과 같다.
(22)
여기서 $a_{ij}$는 ${\bf A}$의 원소이다. 선행 주부분 행렬의 차원을 키워갈 때, 기본 행 연산으로 상삼각 행렬을 항상 만들 수 있는지 알아보자. 첫번째 부분 행렬에 대해 $a_{11} = u_{11}$이므로, $a_{11} \ne 0$이면 상삼각 행렬이 된다. 여기서 $u_{ij}$는 ${\bf U}$의 원소이다. 만약 $k \times k$의 차원을 가진 $k$번째 부분 행렬로 상삼각 행렬을 잘 만들었다면, $k+1$번째 부분 행렬은 다음과 같다.
(23)
LU 분해의 조건에 의해 식 (23)의 행렬식은 $0$이 아니므로, 식 (23)을 구성하는 벡터는 모두 선형 독립(linearly independent)이다. 그러면 적절한 기본 행 연산을 적용해서 식 (23)의 $k+1$번째 행에서 $k+1$열을 제외한 모든 원소를 다음처럼 $0$으로 만들 수 있다.
(24)
여기서 $\bar r_i$는 $i$번째 행 벡터이다. 따라서 모든 선행 주부분 행렬의 행렬식이 0이 아니면 대각선 원소가 $0$이 아닌 상삼각 행렬 ${\bf U}$를 항상 만들 수 있다. LU 분해의 유일성을 보려면 식 (21)에서 얻은 상삼각 행렬과 하삼각 행렬의 곱을 살펴봐야 한다.
(25)
여기서 $\min(\cdot)$는 최소값, $l_{ij}$는 ${\bf L}$의 원소이다. 예를 들어 처음 세번째 행까지 다음 관계가 성립한다.
(26)
행렬 ${\bf L}$과 ${\bf U}$의 원소에 대해 식 (26)을 다시 정리한다.
(27)
그러면 $k+1$번째 행에서 $j \le k$인 $l_{k+1, j}$는 식 (27)처럼 딱 한 값만 가능하다. 마찬가지로 $j \ge k+1$인 $u_{k+1, j}$는 이미 얻은 $l_{k+1, m}$과 $u_{m, j}$[$m = 1,2,\cdots,k$]를 식 (27)처럼 연산해 유일하게 결정된다. 따라서 ${\bf A}$가 정해지면 식 (18)을 만족하는 ${\bf L}$과 ${\bf U}$는 딱 하나만 존재한다.
______________________________
행렬 $\bf L$, $\bf U$의 역행렬이 존재하면 LU 분해의 유일성은 더 쉽게 증명된다. 행렬 $A$에 대한 LU 분해가 두 종류가 있다면, 다음 관계가 성립한다.
(28)
LU 분해는 행렬 연산에서 매우 중요한 위치에 있기 때문에, LU 분해를 열심히 적용하면 다양한 행렬 연산을 좀더 쉽게 처리할 수 있다.
1. 기본(basics)
[순열 행렬의 역행렬]
순열 행렬의 역행렬은 전치 행렬이다.
(1.1)
여기서 $(\cdot)^T$는 전치 행렬을 의미한다.
[증명]
식 (29)에 있는 순열 행렬은 다음과 같은 행 바꾸기 연산의 기본 행렬 ${\bf E}^{(s)}$의 곱으로 표현할 수 있다.
(1.2)
여기서 $p$는 행 바꾸기 연산을 적용한 회수이다. 동일한 행 바꾸기를 한 번 더 하면 원래 행으로 되돌아가기 때문에, 행 바꾸기 연산의 역연산은 자기 자신이다. 따라서 순열 행렬의 역행렬은 식 (1.2)를 반대로 적용하면 구할 수 있다.
(1.3)
여기서 $({\bf E}^{(s)})^T$ = ${\bf E}^{(s)}$이다. 식 (1.3)의 행렬 곱을 전치 행렬로 묶으면 식 (1.1)을 얻을 수 있다.
______________________________
식 (15)와 (1.2)에 의해 순열 행렬의 행렬식은 $|{\bf P}| = (-1)^p$이다.
[기본 행렬과 일반 행렬 곱의 행렬식]
기본 행렬과 일반 행렬 곱의 행렬식은 각 행렬식의 곱과 같다.
(1.4)
(1.5)
[증명]
행렬식의 기하학적 의미를 고려하면 식 (1.4)는 쉽게 증명된다. 식 (1.5)의 좌변에 식 (1.4)를 연속적으로 적용하면 식 (1.5)의 우변을 얻을 수 있다.
______________________________
식 (1.5)를 두 행렬의 곱으로 확장하면, 행렬 곱의 행렬식 특성을 증명할 수 있다.
2. 다양한 연산(various operations)
[행렬식(determinant)]
행렬 ${\bf A}$를 LU 분해하면, ${\bf A}$의 행렬식은 상삼각 행렬 ${\bf U}$에 있는 모든 대각선 원소의 곱이다.
(2.1)
(2.7)
(2.8)
식 (2.8)에서 적용한 기본 행렬을 모두 곱하면 식 (2.7)의 첫째식이 된다. 역행렬인 식 (2.7)의 첫째식에 역행렬을 다시 적용하면 식 (2.7)의 둘째식이 된다.
______________________________
연립 방정식을 풀기 위한 사다리꼴 형태인 식 (4)를 만들 때, 기본 행 연산을 더 적용해서 식 (4)를 다음과 같은 대각 행렬 형태로 만들 수도 있다.
(2.9)
식 (2.9)를 관찰하면, 행렬이 대각선 원소만 가지고 있으므로 $x_i = b_i'' / a_{ii}''$를 이용해 쉽게 해를 구할 수 있다. 이러한 연립 방정식의 해법은 가우스–요르단 소거법(Gauss–Jordan elimination)이라 한다. 가우스Carl Friedrich Gauss(1777–1855)를 이어서 요르단Wilhelm Jordan(1842–1899)이 1888년요르단 46세, 조선 고종 시절에 이 방식을 처음 제안했다. 가우스–요르단 소거법은 역행렬을 구할 때도 매우 유용하다. 식 (2.7)의 첫째식은 기본 행렬을 계속 적용해 항등 행렬을 만들면 사용한 기본 행렬의 곱이 역행렬임을 뜻한다. 이 개념을 식 (2.8)에 적용하자. 행렬 $\bf A$를 $\bf I$로 만들 때 사용한 기본 행렬의 곱을 순서대로 $\bf I$에 곱하면 역행렬이 얻어진다. 따라서 가우스–요르단 소거법을 적용한 역행렬의 해법은 다음과 같다.
(2.10)
[대칭 행렬(symmetric matrix)]
(2.11)
(2.12)
(4)식 (4)에 의해 미지수 $x, y, z$는 다음처럼 간략히 표현된다.
(5)식 (2)로 표현한 행렬을 식 (4)처럼 만들기 위해서 가우스 소거법은 다음 세 가지의 기본 행 연산(elementary row operation)을 반복해서 사용한다.
- 행 곱하기 $e^{(m)}$(row multiplication): 현재 행에 $0$이 아닌 스칼라[$c$]를 곱한다.[$\bar r_i \leftarrow c \bar r_i$]
- 행 더하기 $e^{(a)}$(row addition): 현재 행과 $0$이 아닌 스칼라[$c$]를 곱한 다른 행을 더한다.[$\bar r_i \leftarrow \bar r_i + c \bar r_j$] 여기서 두 행은 서로 다르다.
- 행 바꾸기 $e^{(s)}$(row switching): 두 행을 서로 바꾼다.[$\bar r_i \leftrightarrow \bar r_j$]
(6)여기서 $a_{in} + c a_{jn}$ = $0$, $c = - a_{in}/a_{jn}$이다. 식 (6)에 등장하는 기본 행 연산이 $e^{(m)}$과 $e^{(a)}$이다. 또한 곱하는 행이 항상 다르기 때문에, 연산 $e^{(m)}$과 $e^{(a)}$는 서로 같을 수 없다. 다음과 같은 계산 절차를 사용하면, $e^{(s)}$를 $e^{(m)}$과 $e^{(a)}$로 만들 수 있다[1]. 우리가 교환하고 싶은 행 번호가 $i, j$라면, 다음과 같은 순서로 기본 행 연산을 반복해서 $e^{(s)}$를 만들 수 있다.
- $e^{(a)}$: $c = 1$일 때 $\bar r_j' \leftarrow \bar r_j + \bar r_i$
- $e^{(a)}$: $c = -1$일 때 $\bar r_i' \leftarrow \bar r_i - \bar r_j' = - \bar r_j$
- $e^{(a)}$: $c = 1$일 때 $\bar r_j' \leftarrow \bar r_j' + \bar r_i' = \bar r_i$
- $e^{(m)}$: $c = -1$일 때 $\bar r_i' \leftarrow -\bar r_i' = \bar r_j$
기본 행 연산을 수학적으로 더 세련되게 다루려면, 기본 행 연산을 행렬로 표현해야 한다. 이를 위해 $i$번째 기본 행 연산 $e_i$에 해당하는 기본 행렬(elementary matrix)을 ${\bf E}_i$라 하자. 그러면 가우스 소거법을 행렬로 처리하기 위한 다음 관계가 성립한다.
(7)물론 식 (7)처럼 표기한다고 그 관계가 성립된다는 뜻은 아니다. 연산 $e^{(m)}$과 $e^{(a)}$에 대해 식 (7)을 하나씩 증명해야 한다. 연산 $e^{(s)}$는 $e^{(m)}$과 $e^{(a)}$의 결합이기 때문에 따로 증명할 필요는 없다. 먼저 $e^{(m)}$에 대한 ${\bf E}^{(m)}$의 원소(element)를 $E_{ij}^{(m)}$라 한다. 그러면 $n$번째 행에 대한 행 곱하기 연산 $e^{(m)}$은 다음과 같다.
(8) (9) (10) (11)또한 행 바꾸기 연산 $e^{(s)}$를 위한 기본 행렬 ${\bf E}^{(s)}$의 원소 $E_{ij}^{(s)}$도 다음처럼 기술한다.
(12)식 (12)에 나오는 크로네커 델타 $\delta_{ij}$는 $i,j$를 바꿀 수 있으므로, ${\bf E}^{(s)}$ = $({\bf E}^{(s)})^T$가 성립해서 ${\bf E}^{(s)}$는 대칭 행렬(symmetric matrix)이 된다. 이를 종합하면, 기본 행 연산을 식 (7)과 같은 기본 행렬로 항상 표현할 수 있다. 또한 행 바꾸기 연산 $e^{(s)}$는 $e^{(m)}$과 $e^{(a)}$의 기본 행렬의 곱으로도 나타낼 수 있다.
(13)최종적으로 식 (4)에 제시한 상삼각 행렬(upper triangular matrix) ${\bf U}$를 만들기 위한 가우스 소거법을 기본 행렬의 유한 곱으로 멋있게 표현할 수 있다.
(14)여기서 $r$은 기본 행 연산을 적용한 회수이다. 행렬식(determinant)의 정의 혹은 행렬식은 방향성 있는 부피 개념에 따라 기본 행렬의 행렬식도 구해본다.
(15)기본 행렬의 행렬식은 $0$이 아니므로 역행렬(inverse matrix)이 항상 존재한다. 기본 행렬의 역행렬은 기본 행 연산의 역연산 관점으로 쉽게 이해할 수 있다. 우리가 기본 행렬의 행렬식을 계산하지 않더라도, 행 곱하기, 행 더하기, 행 바꾸기는 당연히 역연산이 존재하므로 기본 행렬의 역행렬은 반드시 존재함을 바로 알 수 있다. 그러므로 기본 행렬 ${\bf E}^{(m)}$과 ${\bf E}^{(a)}$의 역행렬인 $({\bf E}^{(m)})^{-1}$과 $({\bf E}^{(a)})^{-1}$은 행렬 원소를 다음처럼 정의할 수 있다.
(16) (17)여기서 $n$은 기본 행 연산을 적용한 행 번호이다. 행렬 ${\bf E}^{(s)}$의 역행렬은 식 (12)처럼 $({\bf E}^{(s)})^{-1}$ = ${\bf E}^{(s)}$이다.
행렬 이론에서 가장 중요한 분해법인 LU 분해(lower–upper decomposition) 혹은 LU 인수 분해(lower–upper factorization)는 식 (14)를 이용해서 아래처럼 증명할 수 있다.
[LU 분해]
행렬 ${\bf A}$의 모든 선행 주부분 행렬(leading principal submatrix)의 행렬식이 $0$이 아니면, 다음 분해를 만족하는 행렬 ${\bf L}, {\bf U}$는 유일하게 존재한다.
(18)여기서 ${\bf L}$은 대각선 원소가 모두 $1$인 하삼각 행렬(lower triangular matrix), ${\bf U}$는 대각선 원소가 $0$이 아닌 상삼각 행렬이다.
[증명]
가우스 소거법을 적용해 식 (14)처럼 ${\bf A}$를 ${\bf U}$로 바꾼다. 기본 행렬의 행렬식은 항상 0이 아니므로, 식 (14)의 좌변과 우변에 기본 행렬의 역행렬을 계속 적용해서 다음 관계식을 얻는다.
(19)여기서 $r$은 기본 행렬을 만든 회수이다. 행렬 ${\bf L}$의 특성을 이해하기 위해 기본 행렬을 살펴본다. 기본 행렬 ${\bf E}^{(m)}$은 대각 행렬(diagonal matrix)이므로 특이한 점은 없다. 기본 행렬 ${\bf E}^{(a)}$는 식 (10)으로 인해 항상 하삼각 행렬이다. 이 특성을 간단히 증명해본다. 가우스 소거법을 적용해서 상삼각 행렬 ${\bf U}$를 만들고 있는 중이므로[∵ 대각선 원소의 아래쪽을 0으로 만들어야 상삼각 행렬], $l$번째 행에 $c$를 곱해 더해주는 행 번호인 $n$은 $n > l$이 성립한다. 따라서 행 더하기인 식 (10)으로 인해 대각선 원소[대각선 열 번호는 $n$]의 왼쪽 위치[$l < n$]에 원소 $c$가 생긴다. 이 성질은 ${\bf E}^{(a)}$가 하삼각 행렬임을 의미한다. 또한 행렬 곱 관점으로 보면, 하삼각 행렬끼리는 서로 곱하더라도 항상 하삼각 행렬이다. 마찬가지로 하삼각 행렬의 역행렬도 하삼각 행렬이다. 예를 들어, 어떤 하삼각 행렬 ${\bf T}_l$의 역행렬 ${\bf T}_l^{-1}$을 만들려면 식 (14)처럼 상삼각 행렬을 만드는 기본 행 연산을 적용하면 된다.
(20)여기서 ${\bf I}$는 항등 행렬(identity matrix)이다. 그러면 ${\bf U}$를 만드는 기본 행렬의 곱은 항상 하삼각 행렬이다. 이 모든 고찰을 합치면, 식 (19)에 정의한 ${\bf L}$은 필연적으로 하삼각 행렬이다. 추가적으로 ${\bf L}$의 대각선 원소가 $1$이 아닐 수도 있다. 이때는 ${\bf L}$의 대각선 원소를 가지는 대각 행렬 ${\bf D}$를 정의해서 ${\bf L}$을 다음처럼 분해한다. 그러면 대각선 원소가 $1$인 ${\bf L}'$과 그 짝인 ${\bf U}'$으로 분해할 수 있다.
(21)식 (21)에 의해 LU 분해의 존재성(existence)이 증명되었으므로, LU 분해의 유일성(uniqueness)을 살펴보자. 먼저 선행 주부분 행렬(leading principal submatrix)을 정의하자. 주부분 행렬(principal submatrix)은 특정 행이나 열을 지워서 만든 정방 행렬(square matrix)이다. 행렬의 좌측 상단(upper left)을 시작점으로 1행 1열로 구성한 가장 작은 주부분 행렬에서 행렬의 차원(matrix dimension)을 하나씩 키워서 원래 행렬까지 커지는 주부분 행렬 중의 하나를 선행 주부분 행렬이라 한다. 더 쉬운 말로 선행 주부분 행렬을 좌측 상단 주부분 행렬(upper left principal submatrix)이라 할 수 있다. 즉 좌측 상단 원소를 항상 포함하는 주부분 행렬이 선행 주부분 행렬이다. 예를 들어 식 (2)에 있는 $\bf A$의 모든 선행 주부분 행렬은 다음과 같다.
(22)여기서 $a_{ij}$는 ${\bf A}$의 원소이다. 선행 주부분 행렬의 차원을 키워갈 때, 기본 행 연산으로 상삼각 행렬을 항상 만들 수 있는지 알아보자. 첫번째 부분 행렬에 대해 $a_{11} = u_{11}$이므로, $a_{11} \ne 0$이면 상삼각 행렬이 된다. 여기서 $u_{ij}$는 ${\bf U}$의 원소이다. 만약 $k \times k$의 차원을 가진 $k$번째 부분 행렬로 상삼각 행렬을 잘 만들었다면, $k+1$번째 부분 행렬은 다음과 같다.
(23)LU 분해의 조건에 의해 식 (23)의 행렬식은 $0$이 아니므로, 식 (23)을 구성하는 벡터는 모두 선형 독립(linearly independent)이다. 그러면 적절한 기본 행 연산을 적용해서 식 (23)의 $k+1$번째 행에서 $k+1$열을 제외한 모든 원소를 다음처럼 $0$으로 만들 수 있다.
(24)여기서 $\bar r_i$는 $i$번째 행 벡터이다. 따라서 모든 선행 주부분 행렬의 행렬식이 0이 아니면 대각선 원소가 $0$이 아닌 상삼각 행렬 ${\bf U}$를 항상 만들 수 있다. LU 분해의 유일성을 보려면 식 (21)에서 얻은 상삼각 행렬과 하삼각 행렬의 곱을 살펴봐야 한다.
(25)여기서 $\min(\cdot)$는 최소값, $l_{ij}$는 ${\bf L}$의 원소이다. 예를 들어 처음 세번째 행까지 다음 관계가 성립한다.
(26)행렬 ${\bf L}$과 ${\bf U}$의 원소에 대해 식 (26)을 다시 정리한다.
(27)그러면 $k+1$번째 행에서 $j \le k$인 $l_{k+1, j}$는 식 (27)처럼 딱 한 값만 가능하다. 마찬가지로 $j \ge k+1$인 $u_{k+1, j}$는 이미 얻은 $l_{k+1, m}$과 $u_{m, j}$[$m = 1,2,\cdots,k$]를 식 (27)처럼 연산해 유일하게 결정된다. 따라서 ${\bf A}$가 정해지면 식 (18)을 만족하는 ${\bf L}$과 ${\bf U}$는 딱 하나만 존재한다.
______________________________
(28)하삼각 행렬의 역행렬이나 곱은 하삼각 행렬이며, 상삼각 행렬의 역행렬이나 곱도 상삼각 행렬이다. 그러면 식 (28)의 우변에서 하삼각 행렬과 상삼각 행렬이 서로 같아야 한다. 따라서 식 (28)의 행렬 곱은 대각 행렬이 되어야 한다. 또한 하삼각 행렬의 대각선 원소는 $1$이므로, $({\bf L}')^{-1}{\bf L}$은 항등 행렬이 된다. 따라서 $\bf L$ = ${\bf L}'$, $\bf U$ = ${\bf U}'$가 성립한다.
식 (18)을 모든 행렬에 대해 적용하려면, ${\bf U}$의 대각선 원소가 $0$이 되지 않도록 ${\bf A}$에 행 바꾸기 연산을 다음처럼 적용해야 한다.
(29)
여기서 ${\bf P}$는 모든 행 바꾸기 연산의 합성을 나타내는 순열 행렬(permutation matrix)이다. 임의의 행렬 ${\bf A}$를 LU 분해하는 식 (29)와 같은 분해 방식은 행 연산만 사용하기 때문에 부분적 추축(部分的樞軸, partial pivoting)이라 한다. 만약 행과 함께 열에도 바꾸기 연산을 적용하면 전추축(全樞軸, full pivoting)이 된다. 행 바꾸기 한 행렬[$\bf PA$]까지 원래 행렬[$\bf A$]과 동일하다고 생각하면, LU 분해의 유일성은 성립하지 않는다. 예를 들어, ${\bf P}_1$과 ${\bf P}_2$을 사용한 LU 분해는 서로 다른 삼각 행렬로 분해된다.
(30)
여기서 순열 행렬의 역행렬은 식 (1.1)처럼 전치 행렬(transpose)이다. 식 (19)는 행렬 ${\bf A}$의 역행렬 존재 유무 혹은 행렬식의 값과는 관계없이 항상 성립한다. 그래서 역행렬이 존재하지 않는 경우 혹은 행렬식이 $0$인 경우에도 ${\bf A}$를 식 (19)처럼 LU 분해할 수 있다. 다만 이 경우는 ${\bf U}$의 대각선 원소 중 일부는 $0$이 되기 때문에 LU 분해의 유일성은 성립하지 않는다. 왜냐하면 ${\bf U}$의 대각선 원소가 $0$이어서 식 (26)에 의해 ${\bf L}$의 원소 일부는 임의로 배정될 수 있기 때문이다.
식 (18)을 모든 행렬에 대해 적용하려면, ${\bf U}$의 대각선 원소가 $0$이 되지 않도록 ${\bf A}$에 행 바꾸기 연산을 다음처럼 적용해야 한다.
(29)여기서 ${\bf P}$는 모든 행 바꾸기 연산의 합성을 나타내는 순열 행렬(permutation matrix)이다. 임의의 행렬 ${\bf A}$를 LU 분해하는 식 (29)와 같은 분해 방식은 행 연산만 사용하기 때문에 부분적 추축(部分的樞軸, partial pivoting)이라 한다. 만약 행과 함께 열에도 바꾸기 연산을 적용하면 전추축(全樞軸, full pivoting)이 된다. 행 바꾸기 한 행렬[$\bf PA$]까지 원래 행렬[$\bf A$]과 동일하다고 생각하면, LU 분해의 유일성은 성립하지 않는다. 예를 들어, ${\bf P}_1$과 ${\bf P}_2$을 사용한 LU 분해는 서로 다른 삼각 행렬로 분해된다.
(30)여기서 순열 행렬의 역행렬은 식 (1.1)처럼 전치 행렬(transpose)이다. 식 (19)는 행렬 ${\bf A}$의 역행렬 존재 유무 혹은 행렬식의 값과는 관계없이 항상 성립한다. 그래서 역행렬이 존재하지 않는 경우 혹은 행렬식이 $0$인 경우에도 ${\bf A}$를 식 (19)처럼 LU 분해할 수 있다. 다만 이 경우는 ${\bf U}$의 대각선 원소 중 일부는 $0$이 되기 때문에 LU 분해의 유일성은 성립하지 않는다. 왜냐하면 ${\bf U}$의 대각선 원소가 $0$이어서 식 (26)에 의해 ${\bf L}$의 원소 일부는 임의로 배정될 수 있기 때문이다.
LU 분해는 행렬 연산에서 매우 중요한 위치에 있기 때문에, LU 분해를 열심히 적용하면 다양한 행렬 연산을 좀더 쉽게 처리할 수 있다.
1. 기본(basics)
순열 행렬의 역행렬은 전치 행렬이다.
(1.1)여기서 $(\cdot)^T$는 전치 행렬을 의미한다.
[증명]
식 (29)에 있는 순열 행렬은 다음과 같은 행 바꾸기 연산의 기본 행렬 ${\bf E}^{(s)}$의 곱으로 표현할 수 있다.
(1.2)여기서 $p$는 행 바꾸기 연산을 적용한 회수이다. 동일한 행 바꾸기를 한 번 더 하면 원래 행으로 되돌아가기 때문에, 행 바꾸기 연산의 역연산은 자기 자신이다. 따라서 순열 행렬의 역행렬은 식 (1.2)를 반대로 적용하면 구할 수 있다.
(1.3)여기서 $({\bf E}^{(s)})^T$ = ${\bf E}^{(s)}$이다. 식 (1.3)의 행렬 곱을 전치 행렬로 묶으면 식 (1.1)을 얻을 수 있다.
______________________________
식 (15)와 (1.2)에 의해 순열 행렬의 행렬식은 $|{\bf P}| = (-1)^p$이다.
[기본 행렬과 일반 행렬 곱의 행렬식]
기본 행렬과 일반 행렬 곱의 행렬식은 각 행렬식의 곱과 같다.
(1.4) (1.5)여기서 $r$은 기본 행렬을 적용한 회수이다.
[증명]
행렬식의 기하학적 의미를 고려하면 식 (1.4)는 쉽게 증명된다. 식 (1.5)의 좌변에 식 (1.4)를 연속적으로 적용하면 식 (1.5)의 우변을 얻을 수 있다.
______________________________
식 (1.5)를 두 행렬의 곱으로 확장하면, 행렬 곱의 행렬식 특성을 증명할 수 있다.
2. 다양한 연산(various operations)
행렬 ${\bf A}$를 LU 분해하면, ${\bf A}$의 행렬식은 상삼각 행렬 ${\bf U}$에 있는 모든 대각선 원소의 곱이다.
(2.1)
여기서 $u_{ii}$는 ${\bf U}$의 $i$번째 대각선 원소이다.
[증명]
행렬 곱의 행렬식은 각 행렬식의 곱으로 쉽게 계산할 수 있다.
(2.2)
또한 삼각 행렬의 행렬식은 대각선 원소의 곱이다. 따라서 $|{\bf L}|$ = $1$이므로, 식 (2.1)이 성립한다.
______________________________
식 (2.1)에서 LU 분해를 적용할 때 순열 행렬을 사용했다면, 식 (2.1)에 순열 행렬의 행렬식인 $(-1)^p$를 곱해야 한다. 여기서 $p$는 행 바꾸기 연산을 적용한 회수이다. LU 분해의 유용성은 식 (2.1)을 봐도 명확히 알 수 있다. 행렬식은 라플라스 전개(Laplace expansion)로 정의하지만, 라플라스 전개를 직접 계산하려면 시간이 너무 많이 걸린다. 이때는 LU 분해를 이용해 원래 행렬을 삼각 행렬로 분해한다. 그러면 식 (2.1)처럼 손쉽게 행렬식을 얻을 수 있다.
[계수 혹은 계급수(rank)]
행렬 ${\bf A}$를 LU 분해하면, ${\bf A}$의 계수는 상삼각 행렬 ${\bf U}$에 있는 $0$이 아닌 대각선 원소의 개수이다.
[증명]
행렬의 계수는 선형 독립(linearly independent)인 행 벡터나 열 벡터의 개수 중에서 최소값이다. 행렬 ${\bf A}$로부터 ${\bf U}$를 만들기 위해 기본 행 연산을 쓴다고 가정한다. 모든 행 벡터가 서로 선형 독립이면, 식 (2.1)에 의해 행렬식은 대각선 원소의 곱이 된다. 이 경우 행렬식은 $0$이 될 수 없기 때문에, 모든 대각선 원소는 $0$이 아니다. 그래서 $0$이 아닌 대각선 원소의 개수가 행렬의 계수가 된다. 만약 행 벡터 중에서 선형 종속(linearly dependent)인 벡터가 있으면, 다음과 같은 선형 결합(linear combination)으로 인해 특정 행의 원소는 모두 $0$이 된다.
(2.3)
당연히 이 행의 대각선 원소도 $0$이 되어서, 선형 종속인 벡터의 개수만큼 $0$인 대각선 원소가 늘어난다. 따라서 $0$이 아닌 ${\bf U}$의 대각선 원소 개수는 행렬의 계수이다.
______________________________
[연립 방정식의 해법]
행렬 ${\bf A}$를 LU 분해하면, 역행렬 없이 연립 방정식을 단계적으로 풀 수 있다.
(2.4)
[증명]
행렬 곱의 행렬식은 각 행렬식의 곱으로 쉽게 계산할 수 있다.
(2.2)또한 삼각 행렬의 행렬식은 대각선 원소의 곱이다. 따라서 $|{\bf L}|$ = $1$이므로, 식 (2.1)이 성립한다.
______________________________
식 (2.1)에서 LU 분해를 적용할 때 순열 행렬을 사용했다면, 식 (2.1)에 순열 행렬의 행렬식인 $(-1)^p$를 곱해야 한다. 여기서 $p$는 행 바꾸기 연산을 적용한 회수이다. LU 분해의 유용성은 식 (2.1)을 봐도 명확히 알 수 있다. 행렬식은 라플라스 전개(Laplace expansion)로 정의하지만, 라플라스 전개를 직접 계산하려면 시간이 너무 많이 걸린다. 이때는 LU 분해를 이용해 원래 행렬을 삼각 행렬로 분해한다. 그러면 식 (2.1)처럼 손쉽게 행렬식을 얻을 수 있다.
[계수 혹은 계급수(rank)]
행렬 ${\bf A}$를 LU 분해하면, ${\bf A}$의 계수는 상삼각 행렬 ${\bf U}$에 있는 $0$이 아닌 대각선 원소의 개수이다.
[증명]
행렬의 계수는 선형 독립(linearly independent)인 행 벡터나 열 벡터의 개수 중에서 최소값이다. 행렬 ${\bf A}$로부터 ${\bf U}$를 만들기 위해 기본 행 연산을 쓴다고 가정한다. 모든 행 벡터가 서로 선형 독립이면, 식 (2.1)에 의해 행렬식은 대각선 원소의 곱이 된다. 이 경우 행렬식은 $0$이 될 수 없기 때문에, 모든 대각선 원소는 $0$이 아니다. 그래서 $0$이 아닌 대각선 원소의 개수가 행렬의 계수가 된다. 만약 행 벡터 중에서 선형 종속(linearly dependent)인 벡터가 있으면, 다음과 같은 선형 결합(linear combination)으로 인해 특정 행의 원소는 모두 $0$이 된다.
(2.3)당연히 이 행의 대각선 원소도 $0$이 되어서, 선형 종속인 벡터의 개수만큼 $0$인 대각선 원소가 늘어난다. 따라서 $0$이 아닌 ${\bf U}$의 대각선 원소 개수는 행렬의 계수이다.
______________________________
[연립 방정식의 해법]
행렬 ${\bf A}$를 LU 분해하면, 역행렬 없이 연립 방정식을 단계적으로 풀 수 있다.
(2.4)
여기서 ${\bf A}$의 차원(dimension)은 $n \times n$, ${\bf x}$와 ${\bf b}$는 열 벡터(column vector)이다.
[증명]
식 (2.4)에 제안된 절차에 따라 열 벡터 ${\bf c}$의 원소 $c_i$를 구하자.
(2.5)
여기서 ${\bf b}$의 원소는 $b_i$, $i$는 $1$부터 시작해 하나씩 더하며 대입한다. 식 (2.5)로 구한 $c_i$를 식 (2.4)의 마지막식에 대입해서 정리하면 ${\bf x}$의 원소 $x_i$를 계산할 수 있다.
(2.6)
여기서 $i$는 $n$부터 시작해 하나씩 빼면서 대입한다.
______________________________
식 (2.5)처럼 $c_i$를 대입하는 방법은 전진 대입법(forward substitution)이라 부른다. 식 (2.6)의 대입 방식은 후진 대입법(backward substitution)이다.
[역행렬(inverse matrix)]
역행렬이 존재하는 행렬 ${\bf A}$는 기본 행렬의 곱으로 표현할 수 있다.
[증명]
식 (2.4)에 제안된 절차에 따라 열 벡터 ${\bf c}$의 원소 $c_i$를 구하자.
(2.5)여기서 ${\bf b}$의 원소는 $b_i$, $i$는 $1$부터 시작해 하나씩 더하며 대입한다. 식 (2.5)로 구한 $c_i$를 식 (2.4)의 마지막식에 대입해서 정리하면 ${\bf x}$의 원소 $x_i$를 계산할 수 있다.
(2.6)여기서 $i$는 $n$부터 시작해 하나씩 빼면서 대입한다.
______________________________
식 (2.5)처럼 $c_i$를 대입하는 방법은 전진 대입법(forward substitution)이라 부른다. 식 (2.6)의 대입 방식은 후진 대입법(backward substitution)이다.
[역행렬(inverse matrix)]
역행렬이 존재하는 행렬 ${\bf A}$는 기본 행렬의 곱으로 표현할 수 있다.
(2.7)여기서 $r$은 기본 행렬을 생성한 회수이다.
[증명]
상삼각 행렬을 만들기 위한 식 (14)의 과정을 더 진행해서 최종적으로 항등 행렬 $\bf I$가 되게 한다.
[증명]
상삼각 행렬을 만들기 위한 식 (14)의 과정을 더 진행해서 최종적으로 항등 행렬 $\bf I$가 되게 한다.
(2.8)식 (2.8)에서 적용한 기본 행렬을 모두 곱하면 식 (2.7)의 첫째식이 된다. 역행렬인 식 (2.7)의 첫째식에 역행렬을 다시 적용하면 식 (2.7)의 둘째식이 된다.
______________________________
연립 방정식을 풀기 위한 사다리꼴 형태인 식 (4)를 만들 때, 기본 행 연산을 더 적용해서 식 (4)를 다음과 같은 대각 행렬 형태로 만들 수도 있다.
(2.9)식 (2.9)를 관찰하면, 행렬이 대각선 원소만 가지고 있으므로 $x_i = b_i'' / a_{ii}''$를 이용해 쉽게 해를 구할 수 있다. 이러한 연립 방정식의 해법은 가우스–요르단 소거법(Gauss–Jordan elimination)이라 한다. 가우스Carl Friedrich Gauss(1777–1855)를 이어서 요르단Wilhelm Jordan(1842–1899)이 1888년요르단 46세, 조선 고종 시절에 이 방식을 처음 제안했다. 가우스–요르단 소거법은 역행렬을 구할 때도 매우 유용하다. 식 (2.7)의 첫째식은 기본 행렬을 계속 적용해 항등 행렬을 만들면 사용한 기본 행렬의 곱이 역행렬임을 뜻한다. 이 개념을 식 (2.8)에 적용하자. 행렬 $\bf A$를 $\bf I$로 만들 때 사용한 기본 행렬의 곱을 순서대로 $\bf I$에 곱하면 역행렬이 얻어진다. 따라서 가우스–요르단 소거법을 적용한 역행렬의 해법은 다음과 같다.
(2.10)[대칭 행렬(symmetric matrix)]
대칭 행렬은 다음처럼 LU 분해할 수 있다.
(2.11)[증명]
식 (21)부터 시작하자. 행렬 $\bf A$는 대칭이므로, 다음 관계가 성립한다.
(2.12)식 (28)과 같은 LU 분해의 유일성으로 인해, 대칭 행렬의 LU 분해는 $\bf U$ = ${\bf L}^T$를 만족해야 한다.
______________________________
[참고문헌]
[1] "Exchange of rows as sequence of other elementary row operations," ProofWiki. (방문일 2020-07-13)
[다음 읽을거리]
1. QR 분해
[참고문헌]
[1] "Exchange of rows as sequence of other elementary row operations," ProofWiki. (방문일 2020-07-13)
[다음 읽을거리]
1. QR 분해
(1a)
(1b)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
(13a)
(13b)
(13c)
(14b)
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(11)
(12)
(13)
(14)
(15)
(16a)
(16b)