2011년 6월 13일 월요일

행렬식(行列式, determinant)

[경고] 아래 글을 읽지 않고 "행렬식"을 보면 바보로 느껴질 수 있습니다.
1. 좌표계 기반 벡터
2. 순열과 조합
3. 행렬


연립 방정식(聯立方程式, simultaneous equations)의 해답이 딱 하나인지 아니면 없거나 무한히 있는지를 쉽게 판단할 수 있는 공식이 행렬식(行列式, determinant)이다. 이름만 보면 행렬식은 행렬과 더 밀접하게 관계되어 있을 것 같지만, 행렬식의 역사를 보면 행렬보다 연립 방정식이 더 관련이 깊다. 예를 들면 행렬식의 영어인 "determinant"를 직역하면 결정식이나 판별식이 된다. 연립 방정식의 해답을 결정하는 식이므로 "determinant"라는 표현을 쓰는 것이다. 행렬식(determinant)이란 용어는 1801년에 가우스(Carl Friedrich Gauss)가 제안했다. 하지만 행렬식의 역사는 더 길어서 라이프니츠, 크라메르, 라플라스, 라그랑쥐와 같은 수학자들이 큰 기여를 했다.
쉽게 생각하면, 행렬식은 연립 방정식이 내포한 다양한 의미를 단 하나의 숫자로 표현해 주는 기상천외한 공식이다. 행렬식 공식은 다소 복잡하지만 그 의미를 기하학적으로 해석하면 충분히 이해할 수 있다. 즉, 행렬식의 기하학적인 의미는 $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$ or $bc$)  
  • 열벡터에서 원소 선택시 동일한 행에서는 뽑지 않는다. (예: $a$가 선택되었으면 $b$는 선택될 수 없음, 대신 $d$를 선택)
  • 인접한 원소곱은 부호를 다르게 설정한다. (예: $ad$는 (+) 선택, $bc$는 (-) 선택)
이상의 관찰을 기반으로 $N \times N$ 행렬의 행렬식 $|{\bf A}|$를 다음처럼 정의하자.

                          (4)

여기서 $\sigma$는 모든 가능한 순열(順列, permutation)중 하나, $\sigma(i)$는 순열 중 $i$번째 원소, $a_{ij}$는 행렬 $\bf A$ 원소중에서 $i$번행 및 $j$번열의 원소, $\Pi$는 수열의 곱(product of sequence)을 의미한다. 잘 보면 식 (4)를 이해하기 힘들게 만드는 근본 원인은 순열이다.
[그림 4] 1,2,3,4를 순열한 경우의 수(출처: wikimedia.org)

순열 이론은 복잡한 수학 이론을 쓰지 않고 단순한 교환(exchange or transposition)만으로 구성된다. 두 개의 항을 서로 교환하는 연산만으로 구성된 순열 이론은 단순하지만 그 계산량으로 인해 매우 복잡해 보인다. 그래서, 순열 증명에서는 구체적으로 계산을 하는 경우는 드물고 그 일을 할 수 있는 알고리즘(algorithm)을 주로 제시한다.
요즘처럼 컴퓨터(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)이기 때문에 마지막에 있는 교환부터 먼저 수행해야 한다.
순열에 대한 감을 잡았으면 교환에 의해 모든 순열은 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)의 보존이라고 한다. 순열의 패리티는 아래로 정의한다.

                          (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)의 총교환 회수를 계산해보자[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$인 경우도 마찬가지이다.
만약 $j < l < k$인 경우를 생각해보자. 교환하기 전에는 순서가 맞지만(오른쪽이 항상 크다.) 교환하면 역순이 되므로 교환 회수가 이전보다 2만큼 증가하게 된다. 왜냐하면 $k$보다 작은 $l$이 오른쪽에 있으므로 $k$에 대해 1만큼 증가하고 $l$보다 작은 $j$가 오른쪽에 있으므로 또한 1만큼 증가한다. $j > l > k$인 경우도 마찬가지로 생각하면 교환 회수가 2만큼 감소함을 알 수 있다.
따라서 $j$와 $k$ 중간에 있는 숫자의 교환 회수 $N_s(l)$은 교환 여부에 따라 2배수만큼 감소하거나 증가함을 알 수 있다. 2배수만큼 변하기 때문에 짝수는 짝수로, 홀수는 홀수로만 변할 수 있다.
마지막으로 고려하지 않은 것은 $j$와 $k$의 교환 회수 관계이다. 예를 들어 $j > k$인 경우 교환이 발생함에 따라 $k$보다 큰 $j$가 오른쪽에 오기 때문에 $N_s(k)$가 1만큼 작아지게 된다. $j < k$가 되면 교환에 따라 $N_s(k)$가 1만큼 커진다.
최종적으로 $j$와 $k$를 서로 교환하면 총교환 회수는 짝수에서 홀수로 혹은 홀수에서 짝수로 바뀐다. 즉, 부호 함수의 부호가 바뀌게 된다.
______________________________

위의 증명은 단순하지만 다소 번잡하다. 좀더 단순하게 생각해서 그냥 한 번 교환했으니($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­)$인 것을 생각하면 당연하다.
이제 행렬식 정의가 완료되었기 때문에 다양한 행렬식 성질을 증명하도록 하자.

[항등행렬(identity matrix)의 행렬식]

                          (13)

[증명]
식 (4)의 정의를 이용하면 각 열에 대해 선택할 수 있는 유일한 행은 대각선행이다. (∵ 대각선을 제외한 나머지 원소는 모두 0이다.) 대각선 원소(diagonal element)를 모두 곱하면 1이 된다.
또한, 대각선 선택에 대한 순열은 $(1~2 \cdots N)$이기 때문에 항등 순열이 되어 부호 함수는 항상 1이 된다.
______________________________

[삼각행렬(identity matrix)의 행렬식]

                            (14)

[증명]
삼각행렬은 상삼각행렬(upper triangular matrix) $\bf U$와 하삼각행렬(lower triangular matrix) $\bf L$로 아래와 같이 표현할 수 있다.

                       (15)

                       (16)

식 (4)의 정의를 이용하면 각 열에 대해 선택할 수 있는 유일한 행은 대각선행이다.
예를 들어 식 (15)의 상삼각행렬을 보면 1열에서 선택할 수 있는 유일한 행은 1행($u_{11}$)이다. 왜냐하면 나머지 행은 1열에서 0이기 때문이다. 다음으로 2열을 선택한다면 1열에서 1행이 선택되었기 때문에 1행을 제외한 나머지행이 선택되어야 한다. 하지만, 2행($u_{22}$)을 제외하고는 모두 0이므로 2행이 선택되어야 한다. 이런 식으로 계산하면 선택하는 모든 원소는 대각선 원소이다. 또한, 대각선 선택에 대한 순열은 $(1~2 \cdots N)$이기 때문에 항등 순열이 되어 부호 함수는 항상 1이 된다. 따라서 식 (14)가 증명된다.
식 (16)의 하삼각행렬의 경우는 조금 더 생각해야 한다. 1열에서는 모든 행이 선택될 수 있다. (∵ 일반적으로 1열의 모든 행이 0은 아니기 때문에) 하지만, 1행($l_{11}$)을 제외한 다른 행을 선택한다면 다음번 1행 선택시(1열을 제외한 나머지열의 행선택에서) 0이 반드시 선택되기 때문에 식 (4)에 의해 이런 경우는 0이 된다. 따라서, 1열에서는 반드시 1행($l_{11}$)이 선택되어야 한다. 나머지열도 마찬가지이므로 식 (14)가 증명된다.
______________________________

식 (14)는 행렬식을 계산할 수 있는 손쉬운 방법을 알려준다. 기본 행연산(elementary row operations)을 통해 에셜론 형태(echelon form)인 식 (15)나 (16)을 만들면 행렬식은 대각선 원소를 곱함으로써 쉽게 계산된다.
식 (14)를 이용하면 식 (13)의 항등행렬(identity matrix)이나 대각행렬(diagonal matrix)의 행렬식도 쉽게 계산할 수 있다. 대각선 원소만 곱해주면 항등행렬이나 대각행렬의 행렬식이 계산된다.

[전치행렬(transpose)의 행렬식]

                          (17)

[증명]
행렬 $\bf A$의 전치행렬(행번호와 열번호 관점에서 서로 바꾸어 주는 행렬)은 식 (18)로 정의한다.

                       (18)

전치행렬을 고려하여 식 (4)를 다시 쓰면 다음과 같다.

                       (19)

식 (19) 증명에서 중요한 것은 순열 $\sigma, \tau$의 관계이다. 순열 $\sigma, \tau$는 보통 위와 아래 순열을 바꾸어 식 (5)와 (20)처럼 정의한다. 식 (4)의 $\sigma$는 각 열에 대해 적당한 행번호를 택하지만 식 (19)의 $\tau$는 행과 열을 바꾸어 생각해서 각 행에 대해 적당한 열번호를 택한다. 예를 들면 식 (5)는 $\sigma$ 입장에서 기술한 순열이고 식 (20)은 $\tau$ 입장에서 기술하는 순열이 된다.

                       (20)

식 (19)에 있는 $\sigma, \tau$ 관계를 찾아보자. $\sigma$는 식 (5)처럼 위쪽 숫자가 항등 순열이지만 $\tau$는 식 (20)처럼 아래쪽 숫자가 항등 순열이라 가정한다. 그러면 순열 $\sigma$를 연산 $p$를 이용해 서로 교환하여 순열 $\tau$가 되었다고 아래와 같이 생각할 수 있다.

                       (21)

여기서 순열은 윗열과 아랫열로 분해해서 간편하게 생각했다. 연산 $p$를 정의할 때 윗열과 아랫열을 $p'$로 한 의미는 윗열과 아랫열을 동일하게 바꾼다는 것이다. (∵ 당연히 순열을 교환할 때는 윗열과 아랫열을 함께 바꾸어야 한다.)
식 (21)을 통해 $\sigma, \tau$의 부호 함수는 같고 서로 역함수 관계인 것을 알 수 있다. 따라서, 식 (21)을 통해 식 (19)가 증명된다. 좀더 쉽게 생각하기 위해 예를 하나 들자. 식 (5)에 있는 $\sigma_2$ 관점에서 식 (19)를 쓰면 다음과 같다.

                          (22)
______________________________

[한 번 교환(exchange or transposition)된 행렬의 행렬식]

                       (23)

여기서 $A_{ij}$는 서로 다른 $i$행과 $j$행을 교환한 행렬이다.

[증명]
한 번 행을 교환해주면 식 (8)의 교환과 부호 함수 관계에 의해 순열의 부호가 바뀌게 된다. 순열의 부호가 바뀌면 식 (4)에 의해 행렬식의 전체부호가 바뀌게 된다.
또한, 식 (4)의 행렬식 계산에서 선택하는 행렬 원소($a_{ij}$)의 종류는 행을 교환하더라도 바뀌지 않기 때문에 식 (23)이 증명된다.
______________________________

식 (17)과 (23)을 같이 적용하면 서로 다른 열과 열을 교환해도 식 (23)이 성립한다.
다음으로 행렬식 정의의 정수라 할 수 있는 라플라스 전개(Laplace expansion)를 증명해보자. 소행렬식을 이용한 라플라스 전개는 1772년에 라플라스(Pierre-Simon Laplace)가 제안하였다.

[라플라스 전개(Laplace expansion)]

                       (24)

여기서 $C_{ij}$는 행렬 $\bf A$의 여인자(餘因子, cofactor), $M_{ij}$는 원소 $a_{ij}$의 소행렬식(小行列式, minor)이다. 예를 들어 소행렬식 $M_{23}$은 아래와 같이 계산할 수 있다.

                       (25)

즉, $M_{23}$은 2행과 3열 원소 전체를 식 (25)처럼 삭제한 후 계산하는 행렬식이다.

[증명]
일반식 (24)를 증명하기 위해 식 (24)에서 열번호를 고정하여 $j = 1$이라 가정하자. 그러면 식 (4)는 다음으로 표현할 수 있다.

                       (26)

식 (4)에 있는 임의의 순열 $\sigma$는 식 (26)에서 $\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)에 의해 순열의 부호 함수를 아래로 분해할 수 있다.

                       (27)

식 (27)에서 $N_s(i) = i-1$이 되는 것은 자명하다. 이를 이해하기 위해 식 (6)에 있는 순열의 총교환 회수 정의를 상기해보자. $i = 1$이면 1보다 작은 수가 오른편에 있을 수 없다. $i = 2$이면 2보다 작은 수가 반드시 오른쪽에 하나있다. (∵ 2보다 작은 1이 오른편에 있으므로) 이런 식으로 생각하면 식 (27)이 증명된다.
다음으로 $j = 2$라면 $j = 1$열과 교환하여 식 (26)과 동일한 논의를 진행할 수 있다. 열을 교환했으므로 식 (23)에 의해 부호가 바뀌어야 한다. 즉, 식 (26)에 있는 부호 함수를 $(-1)^{i+2}$로 정할 수 있다.
$j = 3$이면 $j = 2$열과 바꾸고 다시 $j = 1$열과 바꾸어야 하므로 2번 교환한 것이 된다. 따라서 식 (26)에 있는 부호 함수를 $(-1)^{i+3}$으로 바꾸어야 한다.
이 과정을 계속 반복하면 식 (24)가 증명된다.
______________________________

식 (17)이 성립하기 때문에 식 (24)에 있는 행(row)에 대한 라플라스 전개는 열(column)에 대한 라플라스 전개와 당연히 같다.

[참고문헌]
[1] A. Dogfrey, 10. PermutationsIntroduction to Group Theory, 1998.

[다음 읽을거리]
1. 행렬식의 기하학적 의미

댓글 49개 :

  1. 덕분에 어려웠던 행렬식잘알아갑니다.ㅎㅎ

    답글삭제
  2. 전치행렬의 행렬식 증명 검색하다가 들르게 되었어요.
    순열을 이용해 행렬식을 정의하니 한줄이면 증명되네요.
    덕분에 도움 많이 되었습니다 ^^

    답글삭제
  3. 방문해주셔서 감사합니다.
    순열개념이 처음에는 좀 어렵기는 해도 행렬식에는 필수적이지요. 순열로 인해 평행인 직선들의 곱이 항상 0이 됩니다.

    답글삭제
  4. 순열로 정의한 행렬식에서 순열을 둘로 나누면서 라플라스 전개가 유도되는게 기가막히네요. 공책에 따라쓰면서 정말 기발하다고 느꼈습니다.

    답글삭제
    답글
    1. 저도 같은 생각입니다.
      행렬이라는 개념은 단순한데 천재들의 열정이 더해지니 행렬이 너무 멋진 것이 되네요.

      삭제
  5. '교환 기반 항등순열로 변환성' 부분은 왜 필요한 내용인가요? N-1번 이하인 것과 무관하게 유한한 것마 보이면 충분하지않나요?

    답글삭제
    답글
    1. 증명의 완결성을 위해 제시한 것입니다. 교환을 통해 항등순열로 바뀌지 않는 순열이 있다면 식 (7)이 의미가 없어집니다.

      N-1번은 큰 의미가 없습니다. 증명의 부산물로 얻어진 것입니다.

      삭제
  6. 공식만 외워 푸는 법만 배우다가 드디어 원리를 알게 됩니다.ㅎㅎ

    답글삭제
    답글
    1. 구글이 있는 현재는 외우는 것이 의미가 별로 없지요. 이해가 훨씬 중요합니다. ^^

      삭제
  7. 식4에 파이같이 생긴 기호 뜻이뭐에여

    답글삭제
    답글
    1. 수열을 곱했다는 뜻입니다. 아래 참고하세요.

      http://ghebook.blogspot.kr/2011/12/infinite-product.html

      삭제
  8. 우와... 완전 기본부터 핵심, 응용까지... 덕분에 잘 배우고 갑니다. 순열때문에 왔는데 기본 지식에 응용지식까지 얻고 가네요 ~

    답글삭제
    답글
    1. 도움이 되었다니 기쁘네요. 과찬... 감사합니다. ^^

      삭제
  9. 여기서 직접 언급된것은 아니지만 궁금한게 있습니다. 행렬식을 시그마로 표현할때 det(A)= ∑sgn(σ) a1σ(1) a2σ(2) ... anσ(n) 과 같이 표현하는 것을 배웠는데 n차 정사각형 행렬에서 a1σ(1) a2σ(2) ... anσ(n) 이부분이 어떻게 전개되는지 모르겠습니다. 혹시 시간이 되시면 글남겨주시면 감사하겠습니다. 뒤늦게 수학에 관심이 생겨 공부중인데 블로거님의 설명이 매우 효과적이라 당분간 여기서 공부좀 해보고자 합니다.

    답글삭제
    답글
    1. 방문 감사합니다. ^^

      말씀하신 부분의 증명은 식 (24) 아래에 있습니다. 식 (24)처럼 직접 계산할 때는 순열 부호를 고려해 행렬의 원소를 차례로 곱해 서로 더해주면 됩니다.

      삭제
  10. 안녕하세요 행렬식 공부하다가 궁금한게 잇어서 다녀갑니다 좋은 자료 잘 봣구요.. 혹시 기호중에 S위아래에 작대기 그어진 기호 의미가 무엇인가요 ㅠㅠ?

    답글삭제
    답글
    1. 어떤 기호인지 확실히 떠오르지는 않네요. 혹시 예 같은 것이 있나요?

      삭제
    2. 그림2 바로 밑에요 2개의 미지수 S(x,y)S를 가진이라고 나와잇는데 여기서 S가 뭔지 궁금하네요..그리고 그 이후에도 SadS 이런식으로 나와잇자나요.. 물론 정확히 S는 아니지만.. ㅠㅠ 이거 뭔지 모르겟네요...

      삭제
    3. 스마트폰으로 보시는 모양이네요. ^^
      PC에서 수식을 표현하는 기호입니다. $(x, y)$ = (x, y)로 이해하시면 됩니다.

      삭제
    4. 아 그렇군요 ㅠㅠ 자꾸 막 SnS차원 이런 말이 나와서 무슨말인가 햇네요 ㅠㅠ 나중에 컴퓨터로 차분히 다시 봐야겟네요 블로그에 너무 좋은 자료가 많아 앞으로 자주 들를것 같아요 ㅎㅎ

      삭제
  11. 많은 도움이 되었습니다. 정말 감사합니다^^ 그런데 항등행렬 행렬식을 구하거나 삼각 행렬 행렬식을 구할 때

    식 (4)의 정의를 이용하면 각 열에 대해 선택할 수 있는 유일한 행은 대각선행이다. (∵ 대각선을 제외한 나머지 원소는 모두 0이다.) 라고 쓰셨는데, 0인 원소를 선택하면 안되는 이유가 무엇인지 알 수 있을까요?

    답글삭제
    답글
    1. 식 (4)의 항은 곱셈이므로 0을 택하면 전체값이 0이 되어 행렬식에 영향을 주지 않습니다.

      삭제
  12. 참! 그리고 식(4)에서 대문자 시그마 기호 밑에 소문자 시그마 기호만 써져있는 것의 의미는 무엇인가요?

    답글삭제
    답글
    1. 식 (4) 정의에서 우리가 다루고 있는 것은 순열이라서 모든 가능한 순열을 표현하기 위해 $\sigma$를 붙인 것입니다. 즉, 모든 가능한 순열을 고려해서 모두를 더하라는 의미입니다.

      삭제
    2. 포스트 감사합니다^^
      그런데, 저기 (21) 식 유도 두번째 줄에서 시그마 행렬과 p행렬을 곱했으니
      2p', 2σ'p'이 되서 2p'=τ'이 되는 것이 아닌지요?

      삭제
    3. 본문에 보면

      순열 $\sigma$를 연산 $p$를 이용해 서로 교환하여 순열 $\tau$가 되었다

      라고 나옵니다. 순열에 대한 연산을 단순히 $p$로 표기한 것이라 2가 들어갈 이유는 없습니다. 2가 들어갈 특별한 이유가 있으면 아래 댓글에 알려주세요.

      삭제
    4. 아, 순열 계산인데 행렬로 잘못 보고 생각했습니다,,
      감사합니다^^

      삭제
  13. 엄청난 포스팅이네요,,,, 대단하십니다. 잘 보고 갑니다!
    마지막 라플라스 변환 증명이 조금 이해가 안되는군요..
    1. 첫번 째 줄에서 sgn(σ)뒤에 위에선 없었던 aσ(1),1이 붙는 연유가 무엇입니까?
    2.그리고 두번 쨰 줄에서 aσ(1),1이 사라지면서 맨 앞에 Σ(i=1~N) ai1 로 바뀌는까닭은 무엇입니까?
    알려 주시면 감사하겠습니다!

    답글삭제
    답글
    1. 질문의 답은 임의의 순열 $\sigma$를 분해해서 $\sigma = (i~\tau)$로 표현했기 때문입니다.

      1. 첫번째 의문을 해결하려면 식 (4)와 식 (26)을 함께 보세요. 식 (4)를 바꾸어 표현한 것이 식 (26)입니다. $j = 1,2,\cdots,N$을 분해해 $j = 1$과 $j = 2,3,\cdots,N$으로 나누었습니다.

      2. 순열 $\sigma$의 첫번째 원소는 $i$라고 정했기 때문에 $a_{\sigma(1), 1} = a_{i1}$이 된 것입니다.

      삭제
  14. 비전공자 프로그래머 입니다. 코딩 경험은 조금 있는 편입니다만, 조금 지나니 '초식' 쌓기에 급급할 뿐, 내공이 부족하다는 것을 실감했어요. 인공지능이나 물리, 그래픽처리할 때 수학의 벽에 부딪히더군요.

    유튜브나 iTunes Study, Khan Academy도 가보고 하면서 수학적으로 부족한 부분들을 채우던 중 이 사이트를 알게 되었습니다. 모국어가 영어가 아닌 것이 한스러울 때가 있었는데, 여기선 모국어가 한국어인 것에 감사하게 되네요. 이렇게 공부할 수 있는 이 세상에 감사할 따름입니다.

    이곳의 포스팅들은 안다고 생각했던 개념도 생소하게 접근하고 있다는 점이 특징인 것 같아요. 대부분 교육과정에서 생략하고 넘어가는 증명 부분에 많이 접근하기 때문이겠죠. 처음엔 훑었을땐 이게 뭔소린가 싶고 뒤로가기 누를까 고민도 많이 하게 합니다....하지만 읽고 또 읽고, 종이에 따라 써보고, 적어보고 하다보니 기가막히게 맞아 떨어지는 것이 짜릿한 쾌감을 주네요..그 후에 남는건 공식만 알았던 개념에 대한 깊은 이해...

    좋은 강좌 정말, 정말, 정말 감사합니다.

    답글삭제
    답글
    1. 김영호님, 진솔한 글과 칭찬 모두 감사드립니다.
      저도 지금과 같은 인터넷 세상에 매우 감사하고 있습니다. 여기에 있는 글은 강좌는 아니며 제가 공부하고 고민한 것을 공개한 것입니다. 거창한 것은 아닙니다. ^^

      삭제
  15. 몰라서 고민하고 있던 걸 여기서 발견하고, 또 이게 어떻게 유도된 걸까 고민하다가 깨달았을 때의 기쁨을 매일 얻고 있습니다. ㅎㅎ 역시 처음에 잘 이해안되는 것도 전파 거북님 말씀대로 (벡터의 발산 게시물에서) 여러번 반복해서 보니 조금씩 안개 걷히듯 보이네요.
    언제나 도움 받고있습니다. ^^ 감사합니다.

    답글삭제
    답글
    1. 과분한 칭찬 감사합니다, 익명님. ^^

      삭제
  16. (3 2 4 1 5)를 항등순열로 바꾸려면 [순열의 총교환 회수]의 공식에 의해서 Ns(3)=2,Ns(2,4)=1,Ns(1,5)=0
    따라서 서로 4번 교환하는 것으로 나오는데요.
    근데 (3 2 4 1 5)에서 처음에 첫번째와 네번째에 있는 3과 1를 교환하면 (1 2 4 3 5) 그다음 세번째와 네번째의 4와 3을 교환하면 (1 2 3 4 5) 로 두번을 교환하면 되는 것 같은데요.
    실제 (3 2 4 1 5)는 오른쪽에서 대상이 되는 수보다 작은 수를 더하기만해서 나오는 순열의 총 교환회수 공식보다 휠씬 더 적은 횟수로 교환 가능한거 같은데 가장 최소의 교환횟수를 구할 수 있는 공식은 있는지 있는지 정말 궁금하네요.있다면 정말 알고 싶습니다.
    그리고
    ax+by=A
    cx+dy=B 에서

    ax+by=A에는 m을
    cx+dy=B에는 n을 곱하면

    max+mby=mA
    ncx+ndy=nB
    서로 빼면

    (ma-nc)x+(mb-ndy)=mA-nB로 나오는데
    그런데 (ma-nc)x+(mb-ndy)=A-B로 쓰신것 같은데요

    수학실력이 떨어져서 (ma-nc)x+(mb-nd)y=A-B가 도대체 어떻게 나오게 되었는지 이해가 가지 않네요.

    이 부분도 알려 주시면 고맙겠네요.

    답글삭제
    답글
    1. 1. 단순하게 보면 정렬을 하는 것이라 고속 정렬 알고리즘을 찾아보시면 됩니다. 병합 정렬(mergesort)이나 신속 정렬(quicksort) 등을 보세요. 방대한 연구가 되어 있습니다.

      2. 오타가 있었네요. 지적 정말 감사합니다, sang-heon.Baik님. ^^ 수정했습니다.

      삭제
    2. (1 2 3 4)가 (1 4 2 3)이 되려면 (2 4)를 바꾸고 다시 (2 3)을 바꾸어야 한다. 고 쓰셨는데

      1 2 3 4
      ∂2=1 4 2 3 =(23)(24) 인데

      그런데(1 2 3 4)에서 (24)을 먼저 바꾸고 (23)를 바꾼다면
      (24)을 바꾸면 1 4 3 2,
      (23)를 바꾸면 1 3 4 2 인데
      (24)을 먼저 바꾸고 (23)를 바꾼다면
      어떻게 하면 1 4 2 3이 나오는지도 알고 싶네요.
      이것에 대해서도 답변 해주신다면 좋겠네요.

      삭제
    3. 아래처럼 생각하세요. ^^

      - (1 2 3 4)에서 (2 4)를 바꾸면 (1 4 3 2)
      - (1 4 3 2)에서 (2 3)을 바꾸면 (1 4 2 3)

      삭제
  17. 안녕하세요~ 전파거북이님!

    정말 지식에 많이 감탄하고 어려운 개념을 이렇게 설명해주시니 감사합니다.

    하지만 제가 이해가 안되는 부분이 있어 이렇게 질문을 드립니다

    식 (10)에서 sign function ( sigma*sigma^-1)이 1이면

    sgn(sigma) = sgn(sigma^-1) 이 되는지 이해가 잘 가지 않습니다.

    감사합니다~

    답글삭제
    답글
    1. 또 이해가 안되는 부분이 있어, 질문드립니다~

      홀수 순열이나 짝수순열을 역으로 바꾼다고 해서 어떻게 항등순열을 만드는지,

      홀수 순열 1 3 2 4 = > 4 2 3 1 역 순열이 되어도 똑같은 홀수순열인데 잘 이해가 가질 않습니다 이부분이 이해가 가지 않아 위의 질문도 이해가 가질 않은것 같습니다 감사합니다!

      삭제
    2. 방문 감사합니다, Hun Dong님. ^^

      1. 순열의 부호 함수는 한 번 교환할 때마다 (-1)을 곱해주는 함수입니다. 그래서, ${\rm sgn}(\sigma \tau) = {\rm sgn}(\sigma) {\rm sgn}(\tau)$가 성립합니다.

      2. 식 (11)을 보면, 최종 결과는 같지만 교환 순서는 서로 다른 순열 $\sigma, \tau$의 특성을 증명하고 있습니다. 또한, $\tau$의 역순열은 $\tau$의 교환 순서와 서로 반대되는 순열로 정의합니다.
      (쉽게 생각해 보면, 카드를 섞을 때 섞은 순서($\tau$)와 반대($\tau^{-1}$)로 하면 원래 카드 순서로 돌아갑니다.)
      따라서, 교환 회수가 같기 때문에 ${\rm sgn}(\tau) = {\rm sgn}(\tau^{-1})$가 성립해야 합니다.

      삭제
  18. "요즘처럼 컴퓨터(computer)가 대중화된 시점에는 알고리즘 연구가 가치가 있지만 수백년 전에 이것을 고안한 수학자들 머리속에는 무엇이 있었을까? 참 상상하기 조차 어려운 천재들이 많다."

    이 문장이 참... 뭐랄까 너무 와닿네요. 이미 연구된 것들을 바라보고 이해하는것만 해도 머리가 지끈지끈 거리는데 말이죠 ㅎㅎ; 전파거북이님 블로그에서 너무 많은 도움을 받고 있습니다. 감사합니다.

    답글삭제
  19. 안녕하세요 행렬식에 대해 이해하려다 들어오게 되었습니다. 제가 글을 다 이해못해서 생긴 의문일수도 있겠습니다만 행렬식을 구할때 각 열에서 뽑은 aij 끼리의 곱을 꼭 항등순열 순서로 바꾸는걸 고려해 플러스 마이너스 값을 매겨 시그마하는지 근본적인 이유가 잘 이해가 안되네요ㅜㅠ

    답글삭제
    답글
    1. 그런 이유 때문에, 행렬식을 기하학적으로 생각합니다. 아래 참고하세요.

      https://ghebook.blogspot.kr/2011/06/geometric-meaning-of-determinant.html

      삭제
    2. 아아아아아아 그 각 행렬식 성분마다 곱해서 다 방향을 고려한 값이 순열이고 그 부피의 총 합이 행렬식의 부피가 된다고 생각하면 될까요??

      삭제
    3. $N$차원 공간의 부피를 정의할 때 순열 기반의 부호 함수가 들어갑니다. 그걸 논증한 것이 위 링크 내용입니다.

      삭제
    4. 감사합니다.. 정말 공돌이 천사님이세요ㅠㅜ

      삭제

욕설이나 스팸글은 삭제될 수 있습니다. [전파거북이]는 선플운동의 아름다운 인터넷을 지지합니다.