2011년 6월 13일 월요일

행렬식(行列式, Determinant)

[경고] 아래 글을 읽지 않고 "행렬식"을 보면 바보로 느껴질 수 있습니다.
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)의 보존이라고 한다. 순열의 패리티는 아래로 정의한다.

                          (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)   

[항등 행렬(identity matrix)]

                          (1.1)

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

[삼각 행렬(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$의 곱으로 분해할 수 있다.

                          (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)

여기서 $a_{ij}$는 행렬 $\bf A$의 원소이다. 가약 행렬(可約行列, reducible matrix)은 다음처럼 적절한 순열 행렬(permutation matrix) $\bf P$를 적용해서 블록 상삼각 행렬(block upper triangular matrix)로 만들 수 있다.

                       (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)

여기서 $|\cdot|$은 행렬식이 아닌 절대값, ${\bf v}_j$는 행렬 $\bf A$의 제$j$번째 열 벡터(column vector), $\| \cdot \|$은 벡터 노름(vector norm) 혹은 유클리드 노름(Euclidean norm)이다. 식 (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)

여기서 $\bf Q$는 직교 행렬(orthogonal matrix)이라서 행렬식의 절대값은 $1$, $r_{ii}$는 $\bf R$의 제$i$번째 대각선 원소이다. 또한 직교 행렬의 성질에 의해 벡터 노름이 보존된다.

                       (2.3)

여기서 ${\bf r}_j$는 $\bf R$의 제$j$번째 열 벡터이다. 식 (2.3)을 식 (2.2)에 대입하면 식 (2.1)이 증명된다. 만약 $\bf A$의 열 벡터 ${\bf v}_j$가 서로 직교하면, $\bf R$은 대각 행렬(diagonal matrix)이 된다. 그래서 $\bf R$의 비대각선 원소는 $0$이라서 식 (2.1)의 등호가 성립한다.

[증명: 양의 정부호 행렬(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)

양의 정부호 행렬의 특성에 의해 고유치는 모두 양수이므로, 일반화 산술–기하 평균 부등식(generalized inequality of arithmetic and geometric means)을 적용한 후 고유치 합을 대각합(trace)으로 바꾼다.

                       (2.6)

그러면 식 (2.4)에 의해 식 (2.1)이 쉽게 증명된다.

                       (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)

식 (1.12)에 있는 라플라스 전개를 이용해 식 (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. 가우스 소거법

댓글 53개 :

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

    답글삭제
  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. 감사합니다.. 정말 공돌이 천사님이세요ㅠㅜ

      삭제
  20. 안녕하세요. 식을 보다가 이해가 잘 안되는 부분이 있어서 질문 드립니다. (20)에서 연산 p를 (p' p')으로 정의하였는데 이렇게 되면 이 연산은 항등순열이 되는 것 아닌가요?

    답글삭제
    답글
    1. $p'$가 $\sigma'$에 아무런 영향을 주지 못하면 항등 순열($\epsilon$)이 되겠지만, 식 (19)에서는 $\sigma' p' = \epsilon$이 되는 $p'$라고 가정했습니다.

      삭제
  21. [교환과 부호 함수 관계식]에서 예를 들어 인 경우 교환이 발생함에 따라 보다 큰 Ns(k)가 오른쪽에 오기 때문에
    가 1만큼 작아지게 된다. <- 이렇게 적혀잇는데 Ns(k)가 아니고 Ns(l)아닌가요??

    답글삭제
    답글
    1. 지적 정말 감사합니다, Ajajwnd님 으TL
      설명이 틀렸었네요. 다시 수정했어요.

      삭제

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