1. 좌표계 기반 벡터
2. 순열과 조합
3. 행렬
연립 방정식(聯立方程式, simultaneous equations)의 해답이 딱 하나인지 아니면 없거나 무한히 있는지를 쉽게 판단할 수 있는 공식이 행렬식(行列式, determinant)이다. 이름만 보면 행렬식은 행렬과 더 밀접하게 관계되어 있을 것 같지만, 행렬식의 역사를 보면 행렬보다 연립 방정식이 더 관련이 깊다. 예를 들면 행렬식의 영어인 디터미넌트(determinant)를 직역하면 결정식이나 판별식이 된다. 연립 방정식의 해답을 결정하는 식이므로 직역하면 판별식(determinant)이라는 표현을 쓴다. 행렬식(determinant)이란 용어는 1801년가우스 24세, 조선 순조 시절에 가우스Carl Friedrich Gauss(1777–1855)가 제안했다. 하지만 행렬식의 역사는 더 길어서 라이프니츠Gottfried Wilhelm Leibniz(1646–1716), 크라메르Gabriel Cramer(1704–1752), 라플라스Pierre-Simon Laplace(1749–1827), 라그랑주Joseph-Louis Lagrange(1736–1813)와 같은 수학자들이 큰 기여를 했다. 쉽게 생각하면, 행렬식은 연립 방정식이 내포한 다양한 의미를 단 하나의 숫자로 표현해 주는 기상천외한 공식이다. 행렬식 공식은 다소 복잡하지만 그 의미를 기하학적으로 해석하면 충분히 이해할 수 있다. 즉, 행렬식의 기하학적인 의미는 $n$차원 공간의 방향성 있는 부피이다. $n$차원에서 부피가 있다는 의미는 부피를 구성하는 벡터가 [그림 1]과 같은 평행이 아님을 뜻한다. 그래서 이 벡터로 구성된 연립 방정식은 [그림 2]와 같이 반드시 유일한 해를 가진다. 좀더 구체적인 의미는 아래에서 증명을 통해 자세히 설명한다.
[그림 1] 평행의 의미(출처: wikipedia.org)
[그림 2] 연립 방정식 유일해의 의미(출처: wikipedia.org)
행렬식을 정의하기 위해 간단한 2개의 미지수 $(x, y)$를 가진 연립 선형 방정식(simultaneous linear equation)을 살펴본다.
(1)
식 (1)의 두 방정식에 임의의 수 $m, n$을 곱해서 빼준다.
(2)
식 (2)에서 미지수 $x, y$의 계수가 0이 되는 조건을 구하면 [그림 3]과 같은 평행선 조건을 얻을 수 있다. 즉, 미지수의 계수가 0이 되면 $x, y$에 관계없이 전체값이 0이 되므로 이 조건하에서는 연립 방정식의 해가 유일하지 않다.
[그림 3] 평행인 2원소 연립 선형 방정식(출처: wikipedia.org)
식 (1)을 행렬(行列, matrix)로 표현해서 행렬식을 정의하기 위한 실마리를 찾아본다.
(3)
식 (3)을 이용해 식 (2)의 최종 결과를 설명하면 다음 조건을 정의할 수 있다.
- 열 벡터(column vector) 원소 중에서 하나의 원소만을 택하고[예를 들면 $a, c$ 중에서 $a$ 선택, $b, d$ 중에서 $d$ 선택] 이 원소를 곱하여 원소 곱을 생성한다.[예를 들면 $ad$ 혹은 $bc$]
- 열 벡터에서 원소 선택시 동일한 행에서는 뽑지 않는다.[예를 들어 $a$가 선택되었으면 $b$는 선택될 수 없음, 대신 $d$를 선택]
- 인접한 원소 곱은 부호를 다르게 설정한다.[예를 들면 $ad$는 ($+$) 선택, $bc$는 ($-$) 선택]
이상의 관찰을 기반으로 $n \times n$ 행렬의 행렬식 $|{\bf A}|$를 다음처럼 정의한다. 행렬식은 ${\rm det}({\bf A})$라고 표기하기도 한다.
(4)
여기서 $\sigma$는 모든 가능한 순열(順列, permutation)중 하나, $\sigma(i)$는 순열 중 $i$번째 원소, $a_{ij}$는 행렬 $\bf A$ 원소 중에서 $i$번행 및 $j$번열의 원소, $\Pi$는 수열의 곱(product of sequence)을 의미한다. 식 (4)는 라이프니츠 공식(Leibniz formula)이라 부른다.
[그림 4] 1,2,3,4를 순열한 경우의 수(출처: wikimedia.org)
식 (4)를 이해하기 힘들게 만드는 근본 원인은 순열 개념이다. 순열 이론은 복잡한 수학 이론을 쓰지 않고 단순한 교환(exchange or transposition)만으로 구성된다. 두 개의 항을 서로 교환하는 연산만으로 구성된 순열 이론은 단순하지만 그 계산량으로 인해 매우 복잡해 보인다. 그래서, 순열 증명에서는 구체적으로 계산을 하는 경우는 드물고 그 일을 할 수 있는 알고리즘(algorithm or algorism)을 주로 제시한다. 요즘처럼 컴퓨터(computer)가 대중화된 시점에는 알고리즘 연구가 가치 있지만, 수백년 전에 이런 개념을 고안한 수학자들의 머리속에는 무엇이 들어있었을까? 참 상상하기조차 어려운 천재들이 많다. 순열을 이해하기 위해 [그림 4]와 같이 1,2,3,4를 순서대로 나열하는 경우를 아래와 같이 생각한다.
(5)
식 (5)에서 위에 있는 숫자는 고정된 자리, 아래에 있는 숫자는 그 자리에 있는 현재값이다. 식 (4)의 행렬 입장에서 보면 위에 있는 숫자는 열 번호, 아래에 있는 숫자는 행 번호가 된다. 즉, 각 열에 대해 단 하나의 서로 다른 행이 선택되는 순서이다. 순열 $\sigma_1$에서 (1 2 3 4)가 (1 2 4 3)이 되기 위한 교환 회수를 계산한다. 당연히 위에 있는 값 (3 4)를 서로 바꾸어주면 된다. 즉, 교환 회수는 1번이다. $\sigma_2$는 조금 복잡하다. (1 2 3 4)가 (1 4 2 3)이 되려면 (2 4)를 바꾸고 다시 (2 3)을 바꾸어야 한다. $\sigma_2$에 대한 교환 회수는 2번이다. 식 (5)에서 교환은 연산(演算, operation)이기 때문에 마지막에 있는 교환부터 먼저 수행해야 한다. 순열은 우리에게 익숙한 함수(函數, function) 개념으로 봐도 충분하다. 예를 들어, $\sigma_2$는 $f(1)$ = $1$, $f(2)$ = $4$, $f(3)$ = $2$, $f(4)$ = $3$인 일대일 대응(one-to-one mapping)과 동일하다.
순열에 대한 감을 잡은 상태에서 교환에 의해 모든 순열은 1,2,3,4와 같은 항등 순열(恆等順列, identity permutation)로 만들 수 있음을 증명한다.
[교환 기반 항등 순열로 변환성]
모든 종류의 순열은 최대 $N-1$번의 교환을 통해 항상 항등 순열로 변환할 수 있다. 여기서 $N$은 순열 원소의 개수이다.
[증명]
어떤 순열이든지 교환을 통해 주어진 순열의 순서를 바꿀 수 있다. 순서를 바꿀 때 항등 순열의 순서가 되도록 바꾼다. 항등 순열의 순서가 맞는 숫자는 순열 고려에서 제외하도록 한다.[∵ 이미 제위치에 있기 때문에 바꿀 필요가 없다.] 예를 들면 식 (5)에서 $\sigma_2$를 본다. (1 4 2 3)에서 1은 제위치[첫번째]이므로 바꿀 필요가 없고 항등 순열 순서를 만족하므로 우리가 고려할 필요도 없다. 1을 고려하지 않으므로 순열은 (4 2 3)만을 생각한다. 첫번째에 있는 숫자인 4를 바꾼다. 4를 바꿀 때는 아무 위치나 하지 않고 본래 위치[(4 2 3)에서는 세번째, (1 4 2 3)에서는 네번째]에 있는 3이랑 바꾼다. 그러면 (3 2 4)로 만들 수 있다. 이제 4는 제위치이므로 고려할 순열은 (3 2)가 된다. 3과 2를 서로 바꾸면 우리가 원하는 항등 순열로 바꿀 수 있다. 이와 같은 교환 과정을 통해 항상 항등 순열로 변환할 수 있다. 최대 교환 회수는 당연히 $N-1$번이 된다. 왜냐하면 하나씩 바꾸어가다가 마지막에 고려하는 순열은 두 개의 숫자만 남으므로 교환을 한 번만 하면 되기 때문이다.
______________________________
교환을 통해 임의의 순열을 항등 순열로 바꿀 수 없는 경우가 생긴다면 다음에 정의할 순열의 패리티(parity) 정의식인 (7)이 의미가 없어진다. 즉, 부호를 정할 수 없는 경우가 생기기 때문이다. 하지만 위 증명에 의해 임의의 순열은 교환 과정을 통해 항상 항등 순열로 바뀔 수 있다. 모든 순열이 항등 순열로 변환되므로 그 다음에 고려할 부분은 항등 순열로 변환되기 위한 교환 회수이다. 위의 증명에 소개한 특정 순열의 교환 회수 정의는 다음과 같다.
- 현재 위치의 숫자가 제위치인가 확인한다.
- 제위치이면 다음 위치의 숫자를 동일한 방법으로 확인한다.
- 제위치가 아니면 본래 위치에 있는 숫자와 교환한다.
위의 방법으로 순열의 교환 회수를 정의할 수도 있지만 주어진 순열을 항등 순열로 변환해야 교환 회수를 얻을 수 있는 문제가 있다. 순열의 관찰을 통해 더욱 단순한 아래 방법을 도입할 수 있다. 아래 방법은 숫자 비교를 통해 교환 회수를 바로 정할 수 있다.
[순열의 총교환 회수]
순열에 있는 현재 위치의 숫자 $i$와 오른쪽에 있는 나머지 숫자 전체를 비교하여 현재 위치 숫자보다 작은 숫자의 개수 $N_s(i)$를 계산한다. 첫번째부터 마지막번째까지 헤아린 숫자를 모두 더하면 항등 순열이 되기 위한 순열의 총교환 회수($N_{\rm tot}$)가 된다.
(6)
위 총교환 회수 정의를 이해하기 위해 순열 (3 2 4 1 5) 경우를 살펴본다. 숫자 3인 경우, $N_s(3)$ = $2$이다. 왜냐하면 3보다 작으면서 오른쪽에 있는 숫자는 1과 2이기 때문이다. 2인 경우는 2보단 작은 오른쪽 숫자는 1이기 때문에 $N_s(2)$ = $1$이 된다. 마찬가지로 $N_s(4)$ = $1$, $N_s(1)$ = $0$, $N_s(5)$ = $0$이 된다. 그러면 총교환 회수 $N_{\rm tot} $ = $0 + 1 + 2 + 1 + 0 = 4$가 된다. 그런데, 식 (6)의 정의에서 왜 오른쪽 숫자만 고려하는가? 이를 이해하기 위해 항등 순열 (1 2 3 4 5)를 본다. 모든 숫자에 대해 작은 오른쪽 숫자는 없다. 그래서 $N_{\rm tot}$ = $0$이 된다. 교환할 필요가 없다. 하지만 위에 살펴본 순열 (3 2 4 1 5)처럼 섞여있는 경우는 교환이 필요하다. 즉, $N_s(i)$는 숫자 $i$가 제위치로 가기 위해 필요한 교환 회수가 된다. 왜냐하면 오른쪽 숫자가 항상 크면 항등 순열이므로 전체 순열 위치를 흩뜨리지 않으면서 교환을 하기 위해서는 $N_s(i)$만큼의 교환이 필요하다. 예를 들어 순열 (3 2 4 1 5)의 $N_s(1)$ = $0$이라는 의미는 숫자 1의 오른쪽은 제위치가 맞기 때문에[∵ 숫자 1의 오른쪽 숫자 전부가 1보다 항상 크다. 이는 항상 성립한다.] 교환할 필요가 없다는 뜻이다. 다음으로 $N_s(2)$ = $1$이면 순열 (3 2 4 1 5)이 (3 1 4 2 5)로 되기 위해 1번의 교환을 한다는 의미이다. 숫자 1, 2의 오른쪽은 제위치가 된다.[∵ 숫자 2의 오른쪽 전부가 2보다 크다.] 다시 $N_s(3)$ = $2$가 되면 (3 1 4 2 5)가 2번의 교환을 통해 (1 2 4 3 5)로 바뀌게 된다. $N_s(4)$ = $1$을 적용하면 (1 2 4 3 5)가 항등 순열 (1 2 3 4 5)가 되어 교환을 끝내게 된다. 이 규칙에서 재미있는 부분은 숫자 $i$를 위해 $N_s(i)$ 번의 교환을 하더라도 숫자 $i+1$의 $N_s(i+1)$에는 영향을 주지 못한다. 이 부분을 이해하기 위해 세 가지 경우를 생각한다.
- $i+1$이 $i$의 왼쪽에 있는 경우: $i$를 위해 교환을 하더라도 어차피 $i$는 $i+1$의 오른편에 있다. 즉, 숫자 $i+1$ 입장에서는 숫자 배치[오른쪽에 $i+1$보다 작은 수가 있는지 여부]의 변동이 없기 때문에 $N_s(i+1)$에는 영향을 못 준다.
- $i+1$이 $i$의 오른쪽에 있고 교환을 하더라도 여전히 오른쪽인 경우: 교환이 일어난 숫자의 위치가 $i$와 $i+1$ 사이에 있기 때문에 $i+1$ 입장에서는 바뀜이 없다. 즉, $N_s(i+1)$에는 영향을 못 준다.
- $i+1$이 $i$의 오른쪽에 있고 교환을 통해 $i+1$이 $i$의 왼쪽에 오는 경우: $i$는 $i$보다 작은 어떤 숫자와 교환을 하기 때문에 $i+1$ 입장에서는 교환 회수 $N_s(i+1)$이 변하지 않는다. 왜냐하면 $i+1$은 $i+1$보다 작으면서 오른쪽에 배치된 숫자를 헤아려서 $N_s(i+1)$을 결정하기 때문이다.
______________________________
식 (6)에서는 총교환 회수를 엄격히 정하지만, 항등 순열이 되기 위한 교환 회수는 순열별로 고정되지 않고 어떤 방법으로 교환을 하는가에 따라 바뀌게 된다. 하지만, 순열의 교환 회수 중에서 바뀌지 않는 부분이 있다. 항등 순열이 되기 위한 교환 회수가 짝수인지 홀수인지 여부는 내가 어떻게 순열을 교환하더라도 바뀌지 않는다. 그래서, 이 성질을 순열 패리티(parity of a permutation)의 보존이라고 한다. 순열의 패리티는 아래로 정의한다.
(7)
여기서 ${\rm sgn}(\cdot)$은 부호 함수(sign function)라고 한다. 부호 함수는 짝수 순열(even permutation)이면 $1$을 택하고 홀수 순열(odd permutation)이면 $-1$을 택한다. 패리티라는 말자체는 동등성을 의미한다. 항등 순열이 되도록 교환할 수 있는 여러 방법의 동등성(parity)을 패리티라고 부른다. 골프에 쓰이는 파(par, 평균)의 어원도 패리티와 같다.
[교환과 부호 함수 관계식]
순열 $\sigma$를 한 번 교환한 순열을 $\tau$라 하면 다음 부호 관계가 성립한다.
(8)
[증명]
순열 $\sigma$를 아래처럼 표현한다.
(9)
식 (9)에서 $j$와 $k$를 바꾸면 순열 $\tau$가 된다. 다음으로 식 (6)을 이용하여 식 (9)의 총교환 회수 $N_{\rm tot}$를 계산한다[1]. 숫자 $j$와 $k$ 밖에 있는 숫자는 순열의 총교환 회수 정의에 의해 총교환 회수에 영향을 주지 못한다. 따라서, $j$와 $k$ 사이에 있는 숫자가 받는 영향을 생각한다. 숫자 $j$와 $k$ 중간에 있는 어떤 숫자 하나를 $l$이라 한다. $j$와 $k$를 서로 교환하면 총교환 회수는 $2$의 배수만큼 커지거나 작아진다. 만약 $l$이 $j, k$보다 작거나 큰 경우는 총교환 회수에 영향을 주지 않음은 자명하다. 즉, $l < j, k$이면 $j$와 $k$를 교환하든 하지 않든 $l$에 대한 교환 회수 $N_s(l)$은 변하지 않는다.[∵ $l$의 오른쪽 숫자 $j$ 혹은 $k$는 항상 $l$보다 크다.] 비슷하게 $l > j, k$인 경우도 $N_s(l)$은 변화 없다. 다음 단계로 숫자 배치가 $j < l < k$를 만족하는 사이수 $l$을 고려한다. 교환하기 전에는 순서가 맞지만[오른쪽이 큰 조건에 있다.] 교환하면 역순이 되므로 교환 회수가 이전보다 $2$만큼 증가하게 된다. 왜냐하면 $k$보다 작은 $l$이 오른쪽에 있으므로 $k$에 대해 $1$만큼 증가하고 $l$보다 작은 $j$가 오른쪽에 있으므로 또한 $1$만큼 증가한다. 또한 $j > l > k$인 경우도 마찬가지로 생각하면 교환 회수가 $2$만큼 감소함을 알 수 있다. 종합하면, $j$와 $k$ 중간에 있는 숫자 $l$의 교환 회수 $N_s(l)$은 교환 여부에 따라 $2$의 배수[$0, \pm2$]만큼 감소하거나 증가함을 알 수 있다. 모든 $l$에 대해, 교환 회수 $N_s(l)$은 2의 배수만큼 변하기 때문에, $N_s(l)$은 짝수는 짝수로 혹은 홀수는 홀수로만 변할 수 있다. 마지막으로 고려하지 않은 부분은 $j$와 $k$의 교환 회수 관계이다. 예를 들어, $j > k$인 경우는 교환이 발생함에 따라 $k$보다 큰 $j$가 오른쪽에 가서 정상적 순서가 된다. 그래서 $j, k$만 고려한 $N_s(j)$는 원래보다 $1$만큼 작아지고 $N_s(k)$는 그대로이다. 조건 $j > l > k$가 성립하는 사이수 $l$은 이전 단계에서 이미 반영했으므로, 더이상 $N_{\rm tot}$에 넣지 않는다. 비슷하게 $j < k$라면, 교환에 따라 $j, k$에 대한 $N_s(j)$는 변화 없고 $N_s(k)$는 $1$만큼 커진다. 결국 $j$와 $k$를 서로 교환하면, 총교환 회수 $N_{\rm tot}$는 짝수에서 홀수로 혹은 홀수에서 짝수로만 바뀐다. 즉, 교환에 의해 부호 함수의 부호가 필연적으로 바뀐다.
______________________________
위의 증명은 단순하지만 다소 번잡하다. 좀더 단순하게 생각해서 그냥 한 번 교환하므로,[$j$와 $k$를 교환] 이전 총교환 회수에서 $1$만큼 더하거나 빼주면 식 (8)이 증명될 것 같다. 하지만, 이렇게 하면 안된다. 순열의 총교환 회수는 식 (6)으로 정의하기 때문에 식 (6)에 따라 총교환 회수를 일일이 헤아려야 된다. 식 (6)을 쓰지 않고 이전 총교환 회수 $\pm 1$로 식 (8)을 증명하려면 순열 패리티의 보존 정리(conservation theorem of permutation parity)에 대한 증명을 이용해야 한다. 하지만, 아래 보존 정리 증명에서 식 (8)을 사용하기 때문에 보존 정리를 이용해 식 (8)을 증명할 수는 없다.[∵ 순환 논리에 빠지기 때문에] 또한, 식 (8)을 이용하면 순열에 대한 부호 함수를 아래와 같이 일반화할 수 있다.
(10)
여기서 $\sigma_i$는 순열의 교환을 나타내는 연산이다. 식 (10)은 순열 $\sigma$의 부호는 교환 연산 $\sigma_i$의 부호 곱으로 나타낼 수 있음을 의미한다. 즉, 식 (8)에 의해 한 번 교환할 때마다 부호가 바뀌기 때문에 식 (10)이 성립함은 당연하다. 혹은 $\sigma_i$의 교환 회수를 $N_i$라 하면 ${\rm sgn}(\sigma_i)$ = $(-1)^{N_i}$로 표현할 수 있다는 뜻이다. 항등 순열 $\epsilon$을 생성하는 $\sigma$의 역순열 중의 하나를 $\sigma^{-1}$이라 한다. 쉽게 생각하기 위해 $\sigma^{-1}$는 순열의 교환 연산을 거꾸로 배치한 순열로 정의할 수도 있다. 식 (10)에 의해 역순열의 부호 함수는 다음 관계를 갖는다.
(11)
식 (11)이 성립하기 때문에 항등 순열 $\epsilon$에서 순열 $\sigma$가 되는 교환 회수의 패리티와 순열 $\sigma$가 항등 순열 $\epsilon$로 바뀌는 패리티는 서로 같다. 이상의 증명을 바탕으로 순열 패리티의 보존 정리를 증명한다.
[순열 패리티의 보존 정리(conservation theorem of permutation parity)]
항등 순열이 되기 위한 순열 총교환 회수의 부호 함수는 순열이 주어진 경우 변동되지 않는다. 예를 들어 식 (6)으로 계산해서 짝수이면 어떤 방법을 쓰더라도 순열 총교환 회수는 짝수가 된다. 홀수이면 교환 방법에 관계없이 항상 홀수가 된다.
[증명]
(12)
여기서 $\sigma, \tau$는 교환한 최종 결과는 같지만 교환 연산은 서로 다른 임의의 순열이다.
______________________________
식 (12) 증명에서 $\sigma$ = $\tau$이므로 바로 ${\rm sgn}(\sigma)$ = ${\rm sgn}(\tau)$라고 하면 안된다. 교환의 최종 결과는 같지만 중간 과정은 다를 수 있으므로 역순열[$\tau^{-1}$]을 통해 식 (12)처럼 증명함이 원칙이다. 다시 생각해 보면 거창한 이름의 순열 패리티 보존 정리 증명은 다소 허무하다. 식 (12) 증명의 핵심은 자명한 관계인 식 (8)이다. 순열의 교환 방법에 관계없이 패리티는 동일하기 때문에 식 (6)에 있는 순열의 총교환 회수 계산법을 이용해서 모든 순열의 패리티를 쉽게 계산할 수 있다. 우리가 지금 고민하는 부분은 행렬식이지만, 중요한 행렬식의 성질은 주로 순열 관점으로 설명한다. 이름은 행렬식이지만 실제 주인공은 순열이라는 특성은 약간 이상하지만, 식 (4)에 있는 행렬식 정의의 중요 부분이 순열의 부호 함수 ${\rm sgn}(\cdot)$이라서 오히려 당연하다.
순열을 기반으로 행렬식을 완전하게 정의하기 때문에, 안심하고 식 (4)를 적용해 행렬식의 다양한 성질을 증명할 수 있다.
1. 기본(basics)
(1.1)[증명]
식 (4)의 정의를 이용하면 각 열에 대해 선택할 수 있는 유일한 행은 대각선 행이다.[∵ 대각선을 제외한 나머지 원소는 모두 0이다.] 대각선 원소(diagonal element)를 모두 곱하면 1이 된다. 또한, 대각선 선택에 대한 순열은 $(1~2 \cdots n)$이기 때문에 항등 순열이 되어 부호 함수는 항상 1이 된다.
______________________________
(1.2)
(1.3)
(1.4)
(1.5)
(1.6)
(1.7)
(1.8)
(1.9)
(1.10)
[한 번 교환(exchange or transposition)된 행렬]
(1.11)
[증명]
[라플라스 전개(Laplace expansion)]
(1.12)
[삼각 행렬(triangular matrix)]
(1.2)
[증명]
삼각 행렬은 상삼각 행렬(upper triangular matrix) $\bf U$와 하삼각 행렬(lower triangular matrix) $\bf L$로 아래와 같이 표현할 수 있다.
(1.3) (1.4)
식 (4)의 정의를 이용하면 각 열에 대해 선택할 수 있는 유일한 행은 대각선 행이다. 예를 들어 식 (1.3)의 상삼각 행렬을 보면 1열에서 선택할 수 있는 유일한 행은 1행[$u_{11}$]이다. 왜냐하면 나머지 행은 1열에서 0이기 때문이다. 다음으로 2열을 선택한다면 1열에서 1행이 선택되었기 때문에 1행을 제외한 나머지 행이 선택되어야 한다. 하지만, 2행[$u_{22}$]을 제외하고는 모두 0이므로 2행이 선택되어야 한다. 이런 식으로 계산하면 선택하는 모든 원소는 대각선 원소이다. 또한, 대각선 선택에 대한 순열은 $(1~2 \cdots n)$이기 때문에 항등 순열이 되어 부호 함수는 항상 1이 된다. 따라서 식 (1.2)가 증명된다. 식 (1.4)에 제시한 하삼각 행렬의 경우는 조금 더 생각해야 한다. 가장 왼쪽에 있는 1열에서는 모든 행이 선택될 수 있다.[∵ 일반적으로 1열의 모든 행이 0은 아니기 때문에] 하지만, 1행[$l_{11}$]을 제외한 다른 행을 선택한다면 다음번 1행 선택시[1열을 제외한 나머지 열의 행 선택에서] 0이 반드시 선택되기 때문에 식 (4)에 의해 이런 경우는 0이 된다. 따라서, 1열에서는 반드시 1행[$l_{11}$]이 선택되어야 한다. 나머지 열도 마찬가지이므로 식 (1.2)가 증명된다.
______________________________
식 (1.2)는 행렬식을 계산할 수 있는 손쉬운 방법을 알려준다. 기본 행 연산(elementary row operations)을 써서 일반 행렬을 사다리꼴 형태(echelon form)인 식 (1.3)이나 (1.4)로 만들면, 변형한 삼각 행렬의 행렬식은 대각선 원소를 곱함으로써 쉽게 계산된다. 식 (1.2)를 이용하면 식 (1.1)에 있는 항등 행렬(identity matrix)이나 대각 행렬(diagonal matrix)의 행렬식도 쉽게 계산할 수 있다. 즉 대각선 원소만 곱해주면, 항등 행렬이나 대각 행렬의 행렬식을 얻을 수 있다.
[전치 행렬(transpose)]
(1.5)
[증명]
행렬 $\bf A$의 전치 행렬[행 번호와 열 번호 관점에서 서로 원소를 바꾸어 주는 행렬]은 식 (1.6)으로 정의한다.
(1.6)
전치 행렬을 고려하여 식 (4)를 다시 쓰면 다음과 같다.
(1.7)
식 (1.7) 증명에서 중요한 부분은 순열 $\sigma, \tau$의 관계이다. 순열 $\sigma, \tau$는 보통 위와 아래 순열을 바꾸어 식 (5)와 (1.8)처럼 정의한다. 식 (4)의 $\sigma$는 각 열에 대해 적당한 행 번호를 택하지만 식 (1.7)의 $\tau$는 행과 열을 바꾸어 생각해서 각 행에 대해 적당한 열 번호를 택한다. 예를 들면 식 (5)는 $\sigma$ 입장에서 기술한 순열이고 식 (1.8)은 $\tau$ 입장에서 기술하는 순열이 된다.
(1.8)
식 (1.7)에 있는 $\sigma, \tau$ 관계를 찾아본다. $\sigma$는 식 (5)처럼 위쪽 숫자가 항등 순열이지만 $\tau$는 식 (1.8)처럼 아래쪽 숫자가 항등 순열이라 가정한다. 그러면 순열 $\sigma$를 연산 $p$를 이용해 서로 교환하여 순열 $\tau$가 되었다고 아래와 같이 생각할 수 있다.
(1.9)
여기서 순열은 위열과 아래열로 분해해서 간편하게 생각한다. 연산 $p$를 정의할 때 위열과 아래열을 $p'$로 한 의미는 위열과 아래열을 동일하게 바꿈을 뜻한다.[∵ 당연히 순열을 교환할 때는 위열과 아래열을 함께 바꾸어야 한다.] 식 (1.9)를 통해 $\sigma, \tau$의 부호 함수는 같고 서로 역함수 관계임을 알 수 있다. 따라서, 식 (1.9)에 의해 식 (1.7)이 증명된다. 좀더 쉽게 생각하기 위해 다음과 같은 예를 하나 본다. 즉, 식 (5)에 있는 $\sigma_2$ 관점으로 식 (1.7)을 다시 쓴다.
(1.10)
______________________________
[한 번 교환(exchange or transposition)된 행렬]
(1.11)
여기서 $A_{ij}$는 서로 다른 $i$행과 $j$행을 교환한 행렬이다.
[증명]
한 번 행을 교환해주면 식 (8)의 교환과 부호 함수 관계에 의해 순열의 부호가 바뀌게 된다. 순열의 부호가 바뀌면 식 (4)에 의해 행렬식의 전체 부호가 바뀌게 된다. 또한, 식 (4)의 행렬식 계산에서 선택하는 행렬 원소[$a_{ij}$]의 종류는 행을 교환하더라도 바뀌지 않기 때문에 식 (1.11)이 증명된다.
______________________________
식 (1.5)와 (1.11)을 같이 적용하면, 서로 다른 열과 열을 교환해도 식 (1.11)이 성립한다.
[라플라스 전개(Laplace expansion)]
(1.12)
여기서 $C_{ij}$는 행렬 $\bf A$의 여인자(餘因子, cofactor), $M_{ij}$는 원소 $a_{ij}$의 소행렬식(小行列式, minor)이다. 행렬 원소 $a_{ij}$의 여인자 $C_{ij}$는 $\operatorname{cof}(a_{ij})$라고 표기하기도 한다. 예를 들어, 소행렬식 $M_{23}$은 아래와 같이 계산할 수 있다.
(1.13)
여기서 $M_{23}$은 2행과 3열 원소 전체를 식 (1.13)처럼 삭제한 후 계산하는 행렬식이다.
[증명]
일반식 (1.12)를 증명하기 위해 식 (1.12)에서 열 번호를 고정하여 $j$ = $1$이라 가정한다. 그러면 식 (4)는 다음으로 표현할 수 있다.
(1.14)
식 (4)에 있는 임의의 순열 $\sigma$는 식 (1.14)에서 $\sigma$ = $(i~\tau)$로 정하였다. 순열 $\tau$는 첫번째 원소가 $i$로 정해진 순열 $\sigma$의 나머지 부분을 뜻한다. 순열 $\sigma$ = $(i~\tau)$로 정의해도 괜찮은 이유는 $\sigma$가 임의이기 때문이다. 즉, 우리가 $\sigma$를 선택할 수 있기 때문에, 순열의 첫번째 원소가 $1, 2, \cdots, n$인 경우를 차례로 모아 $\sigma$ = $(i~\tau)$로 정한다. 이렇게 하면 순열에 대한 합($\Sigma_\sigma$)을 지표(index) $i$에 대한 합[$\Sigma_{i=1}^n$]으로 바꿀 수 있다. 또한, 식 (6)에 의해 순열의 부호 함수를 아래로 분해할 수 있다.
(1.15)
식 (1.15)에서 $N_s(i)$ = $i-1$이 됨은 자명하다. 이를 이해하기 위해 식 (6)에 있는 순열의 총교환 회수 정의를 상기한다. $i$ = $1$이면 $1$보다 작은 수가 오른편에 있을 수 없다. 지표 $i$ = $2$이면 $2$보다 작은 수가 반드시 오른쪽에 하나있다.[∵ 2보다 작은 1이 오른편에 있으므로] 이런 식으로 생각하면 식 (1.15)가 증명된다. 다음으로 $j$ = $2$라면 $j$ = $1$ 열과 교환하여 식 (1.14)와 동일한 논의를 진행할 수 있다. 열을 교환하므로 식 (1.11)에 의해 부호가 바뀌어야 한다. 즉 식 (1.14)에 있는 부호 함수를 $(-1)^{i+2}$로 정할 수 있다. 만약 $j$ = $3$이면 $j$ = $2$ 열과 바꾸고 다시 $j$ = $1$ 열과 바꾸어야 하므로 2번 교환하게 된다. 따라서 식 (1.14)에 있는 부호 함수를 $(-1)^{i+3}$으로 바꾸어야 한다. 이 과정을 계속 반복하면 식 (1.12)가 증명된다.
______________________________
식 (1.12)에 제시한 라플라스 전개(Laplace expansion)는 행렬식 정의의 정수이다. 소행렬식을 이용한 라플라스 전개는 1772년라플라스 23세, 조선 영조 시절에 라플라스Pierre-Simon Laplace(1749–1827)가 제안하였다. 식 (1.5)가 성립하기 때문에 식 (1.12)에 있는 행(row)에 대한 라플라스 전개는 열(column)에 대한 라플라스 전개와 당연히 같다.
[행렬의 곱(matrix product)]
행렬 곱의 행렬식은 각 행렬의 행렬식 곱과 같다.
(1.16)
[증명]
먼저 행렬 $\bf A$의 역행렬이 존재한다고 가정한다. 그러면 $\bf A$는 다음과 같은 기본 행렬 ${\bf E}_i$의 곱으로 분해할 수 있다.[행렬의 곱(matrix product)]
행렬 곱의 행렬식은 각 행렬의 행렬식 곱과 같다.
(1.16)[증명]
(1.17)
여기서 $r$은 기본 행 연산이 쓰인 회수이다. 식 (1.17)을 이용해 행렬의 곱을 다시 쓴다.
(1.18)
식 (1.18)에 다음과 같은 기본 행렬과 일반 행렬 곱의 행렬식 공식을 적용한다.
(1.19)
그러면 다음 관계가 성립해서 역행렬이 존재하는 경우는 식 (1.16)을 만족한다.
(1.20)
다음으로 $\bf A$의 역행렬이 없다고 가정한다. 행렬 $\bf A$의 역행렬은 없지만 $\bf AB$의 역행렬은 있을 수 있다. 그래서 $\bf C$를 $\bf AB$의 역행렬이라 생각하면 다음 식이 성립해야 한다.
(1.21)
하지만 ${\bf A}^{-1}$은 존재할 수 없으므로, $\bf AB$의 역행렬도 없다. 이 결과를 식 (1.16)에 대입한다. 행렬 $\bf A$와 $\bf AB$의 역행렬이 없어서 $|{\bf A}|$ = $|{\bf AB}|$ = $0$이다. 따라서 $\bf A$의 역행렬이 없는 경우에도 식 (1.16)은 타당하다.
______________________________[엄격 대각 지배 행렬(strictly diagonally dominant matrix)] [2]
엄격 대각 지배 행렬의 행렬식은 항상 $0$이 아니다.
[증명]
엄격 대각 지배 행렬은 다음 관계를 만족한다.
(1.22)여기서 $a_{ij}$는 행렬 $\bf A$의 원소이다. 만약 $\bf A$의 행렬식이 $0$이라면, 연립 방정식 $\bf Ax$ = $\bf 0$의 해인 열 벡터 $\bf x$는 영 벡터가 아니다. 다음으로 열 벡터 $\bf x$에서 크기가 가장 큰 $0$이 아닌 원소를 $|x_m|$이라 한다. 그러면 다음 부등식이 성립한다.
(1.23)하지만 식 (1.23)의 결과는 정확히 식 (1.22)와 상충한다. 그래서 엄격 대각 지배 행렬의 행렬식은 $0$일 수 없다.
______________________________
[기약 및 약한 대각 지배 행렬(irreducible and weakly diagonally dominant matrix)] [2]
기약이면서 약한 대각 지배인 행렬의 행렬식은 항상 $0$이 아니다. 여기서 한 행 이상은 엄격 대각 지배 행렬의 조건인 식 (1.22)를 만족한다.
[증명]
전체적인 증명 방식은 엄격 대각 지배 행렬의 경우와 비슷하다. 먼저 약한 대각 지배 행렬(weakly diagonally dominant matrix)은 다음 관계를 만족한다.
(1.24)
(1.25)식 (1.25)가 성립하지 않는 행렬은 기약 행렬(旣約行列, irreducible matrix)이라 부른다. 행렬식을 $0$이 가정하면, $\bf Ax$ = $\bf 0$의 해 $\bf x$는 영 벡터가 아니다. 다음으로 열 벡터 $\bf x$에서 크기가 가장 큰 $0$이 아닌 원소를 $|x_m|$이라 정한 후, 식 (1.23)처럼 제$m$행에 대해 부등식을 적용한다. 제$m$행에서 식 (1.24)의 등식이 아닌 부등식이 성립하면, 엄격 대각 지배 행렬의 경우와 같아서 행렬식은 $0$이 아님이 쉽게 증명된다. 결국 우리는 제$m$행에 대해 식 (1.24)의 등식 관계를 추가로 고려해야 한다. 이때 해의 원소 $x_j$는 다음 관계를 가진다.
(1.26)또한 한 행 이상은 식 (1.22)를 만족하므로, 모든 $|x_j|$가 최대값인 $|x_m|$일 수 없다. 따라서 $|x_m|$과 다른 모든 $|x_t|$에 대해 $a_{mt}$ = $0$이 성립한다. 여기서 $t$는 행렬의 열 번호이다. 임의의 행 번호 $s$에서도 행렬 원소의 관계가 식 (1.24)의 등식이 된다면, 항상 $a_{st}$ = $0$이 된다. 이와 같은 특성은 가약 행렬의 성질이므로, 기약 행렬인 조건과 상충된다. 따라서 행렬식은 반드시 $0$이 아니다.
______________________________
2. 부등식(inequality)
[아다마르의 부등식(Hadamard's inequality)] [3]
(2.1)[증명: QR 분해]
행렬 $\bf A$의 행렬식이 $0$이면 식 (2.1)은 바로 성립한다. 그래서 $\bf A$의 행렬식은 $0$이 아니라고 가정한다. 이로 인해 $\bf A$의 모든 열 벡터는 서로 선형 독립(linearly independent)이므로, QR 분해(decomposition)가 성립해서 $\bf A$ = $\bf Q R$로 만들 수 있다. 여기서 $\bf Q$의 열 벡터는 정규 직교 기저(orthonormal basis)를 이루고 $\bf R$은 상삼각 행렬(upper triangular matrix)이다. 따라서 행렬식의 절대값 $\left| {\rm det}({\bf A})\right|$는 다음과 같다.
(2.2)
(2.3)[증명: 양의 정부호 행렬(positive definite matrix)]
행렬 $\bf A$가 에르미트 행렬(Hermitian matrix)이며 양의 정부호 행렬(positive definite matrix)인 경우는 고유치(eigenvalue)를 이용해서 식 (2.1)을 증명할 수 있다. 먼저 $\bf A$의 각 열 벡터를 정규화해서 만든 행렬 $\bf N$의 행렬식은 다음과 같다.
(2.4)여기서 $\bf N$을 구성하는 열 벡터의 크기는 모두 $1$, 열 벡터의 정규화에 쓰인 $\left\| {\bf v}_j \right\|$는 행렬식의 기하학적 성질에 의해 행렬식의 바깥으로 나올 수 있다. 행렬 $\bf N$과 켤레 전치 행렬(conjugate transpose) ${\bf N}^H$를 곱해서 만든 행렬을 $\bf P$ = ${\bf N}^H {\bf N}$으로 정의한다. 두 행렬의 곱으로 만든 $\bf P$의 대각선 원소는 항상 $1$이다.[∵ $\bf N$의 열 벡터 크기가 $1$이다.] 행렬 $\bf P$의 행렬식은 고유치의 곱과 같다.
(2.5)
(2.6)
(2.7)______________________________
행렬 $\bf A$를 구성하는 모든 원소 크기의 최대값을 $M$라 하면[$|a_{ij}| \le M$], 식 (2.1)에 의해 다음 부등식도 성립한다.
(2.8)여기서 $\|{\bf v}_j \| \le M \sqrt{n}$이다.
3. 다양한 응용(various applications)
[연립 방정식의 해법: 크라메르의 규칙(Cramer's rule)]
(3.1)여기서 열 벡터 $\bf x$ = $[x_1~x_2~\cdots~x_j~\cdots~x_n]^T$, ${\bf B}_j$는 $\bf A$에서 제$j$번 열 벡터(column vector)를 $\bf b$로 바꾼 행렬이다.
[증명]
행렬 $\bf A$의 역행렬(inverse matrix)을 다음처럼 표현할 수 있다.
(3.2)여기서 $C_{ij}$는 여인자(cofactor)이다. 식 (3.2)를 식 (3.1)의 왼쪽 식에 대입해서 정리하면 다음 결과를 얻는다.
(3.3)
(3.4)______________________________
[2] O. Taussky, "A recurring theorem on determinants," The American Mathematical Monthly, vol. 56, no. 10, pp. 672–676, Dec. 1949.
[3] J. Hadamard, "Résolution d'une question relative aux déterminants (Resolution of a question related to determinants)," Bulletin des Sciences Mathématiques (Bulletin of Mathematical Sciences), vol. 17, pp. 240–246, 1893.
[다음 읽을거리]
1. 행렬식의 기하학적 의미
2. 가우스 소거법
