[Linear Algebra] 순열(permutation)과 행렬식(determinant)의 정의 및 계산

---

순열 (Permutation)

 

자연수의 집합 $ S = \{ 1, 2, \cdots, n \} $ $ (n \geq 2) $ 에서 $ S $ 로의 전단사 함수 $ \sigma $ 를 순열 혹은 치환이라 하며 다음과 같이 나타낸다.

$$ \sigma =  \begin{pmatrix} 1 & 2 & \cdots & k & \cdots & n \\ i_1 & i_2 & \cdots & i_k & \cdots & i_n \end{pmatrix} $$

또한 이를 다음과 같이 나타낸다.

$$ \begin{pmatrix} i_1 & i_2 & \cdots & i_n \end{pmatrix} $$

즉 다음과 같다.

$$ \sigma(1) = i_1, \cdots , \sigma(k) = i_k , \cdots , \sigma(n) = i_n $$

이때 $ n $ 개를 배열하는 방법은 $ n! $ 가지 이므로 $ S $ 의 순열은 $ n! $ 개이고, 이 $ S $ 의 모든 순열의 집합을 $ S_n $ 으로 나타낸다.

 

---

반전 (Inversion)

 

$ S = \{1, 2, \cdots , n \} $ 의 순열 $ \begin{pmatrix} i_1 & i_2 & \cdots & i_n \end{pmatrix} $ 에서 큰 수가 작은 수보다 앞에 있다면 이 순열은 반전을 가졌다, 혹은 뒤집힘을 가졌다고 한다. 예를 들어 $ S_2 =\{(1, 2), (2, 1)\} $ 에서 $ (1, 2) $ 는 반전이 없고, $ (2, 1) $ 은 반전이 하나 있다.

순열의 $ i_k $ 에서 반전이 일어난 경우 $ k + 1 $ 번째 이후로 나타난 수 중 $ i_k $ 보다 작은 수의 개수를 $ i_k $ 에서의 반전수라 한다.

반전의 개수가 짝수이면 짝순열(even permutation), 홀수이면 홀순열(odd permutation)이라 한다.

항등함수가 $ f(i) = i $ 라는 것을 생각하고, 순열의 반전을 생각해본다면, 항등함수를 만들기 위해 순열에서 필요한 교환 횟수로 반전을 생각해볼 수도 있다. 예를 들어 $ (1, 3, 4, 2) $ 라는 순열이 있다고 하면, 반전은 $ (3, 2) $ 와 $ (4, 2) $ 가 존재하기 때문에 반전의 개수는 2 이다. 이때 3 과 2 를 교환하고, 4 와 3 을 교환하면, 즉 두 번의 교환이 있다면 순열을 항등함수로 만들 수 있다.

 

---

부호화 함수 (Signature Function)

 

부호화 함수라고 하기도 하고, 그냥 부호를 정의한다고 하기도 한다. 순열 $ \sigma $ 의 부호는 다음과 같이 정의된다.

$$ \operatorname{sgn}(\sigma) = \begin{cases} +1, & \sigma : \text{even permutation} \\ -1, & \sigma : \text{odd permutation} \end{cases} $$

만약 순열 $ \sigma $ 의 두 수를 바꾼 순열을 $ \tau $ 라 한다면 $ \operatorname{sgn}(\tau) = - \operatorname{sgn}(\sigma) $ 이다.

어떤 순열에서 두 수의 위치를 바꾼다면, 예를 들어 $ s $ 번째 수와 $ t $ 번째 수를 교환한다고 생각해보자.

그렇다면 $ s $ 보다 앞에 있는 수들의 반전수는 변화가 없을 것이다. 마찬가지로 $ t $ 보다 뒤에 있는 수들의 반전수도 변화가 없을 것이다. 즉 변화 가능성이 있는 것은 $ s $ 와 $ t $ 번째 사이의 수들이다.

만약 $ s $ 와 $ t $ 사이 수가 $ k $ 개라면 $ i_s $ 에서의 반전수에 변화가 일어나고, 이때 반전 개수는 $ k $ 번의 변화가 일어날 것이다. 마찬가지로 $ i_t $ 에서의 반전수에도 변화가 일어나고 마찬가지로 반전 개수는 $ k $ 번이다. 즉 $ 2k $ 번의 반전 변화가 일어났다.

그런데 $ i_s $ 와 $ i_t $ 의 교환 때문에 생기는 반전의 변화가 있고, 이는 1 이다. 즉 두 수의 위치 교환으로 일어나는 반전의 변화는 $ 2k + 1 $ 번이다.

따라서 원래의 순열과 두 수의 위치를 바꾼 순열간 반전 개수 차이는 홀수 개가 되고, 다음이 성립한다.

$ \operatorname{sgn}(\tau) = - \operatorname{sgn}(\sigma) $

 

---

행렬식 (Determinant)

 

$ n $ 차 정사각행렬 $ A $ 의 행렬식을 다음과 같이 정의하고, 이를 $ \det{(A)} $ 혹은 $ |A| $ 로 나타낸다.

$$ \det{(A)} = \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) \prod^n_{i=1} a_{i\sigma(i)} $$

 

---

행렬식 계산

 

기본적으로 행렬식의 정의를 그대로 이용해서 행렬식을 계산하기란 어렵다. 주로 사용되는 행렬인 $ 2 \times 2 $ 행렬과 $ 3 \times 3 $ 행렬에 대한 쉬운 계산 방식이 존재하고, 이를 활용하는 편이 효율적이다.

 

• 2×2 행렬의 행렬식 계산

$$ A = \begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{bmatrix} $$

$$ \det{(A)} = a_{11} a_{22} - a_{12} a_{21} $$

 

• 3×3 행렬의 행렬식 계산 | Sarrus's Rule

$$ A = \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix} $$

원래 행렬을 변형하여 아래와 같이 만든다. 1열과 2열을 차례대로 3열 옆에 쓰면 된다.

$$ A = \begin{bmatrix} a_{11} & a_{12} & a_{13} & a_{11} & a_{12} \\ a_{21} & a_{22} & a_{23} & a_{21} & a_{22} \\ a_{31} & a_{32} & a_{33} & a_{31} & a_{32} \end{bmatrix} $$

대각선에 위치한 성분끼리 곱해준다. 우하단으로 향하는 $ \searrow $ 대각선은 곱한 후 더해주고, 좌하단으로 향하는 $ \swarrow $ 대각선은 곱한 후 빼준다. 그러면 행렬식이 된다. 즉 다음이 성립한다.

$$ \det{(A)} = a_{11}a_{22}a_{33} + a_{12}a_{23}a_{31} + a_{12} a_{21}a_{32} - a_{13}a_{22}a_{31} - a_{11}a_{23}a_{32} - a_{12}a_{21}a_{33} $$

 

---

행렬식의 성질

 

행렬 $ A $ 와 행렬 $ B $ 가 $ n $ 차 정사각행렬이라 가정하면 다음이 성립한다.

 

• 기본 행 연산

$ A $ 에 $ R_i \leftrightarrow R_j $ 연산을 하여 행렬 $ C $ 를 만든다면 $ | C | = - | A | $ 이다.

$ A = \left[ a_{ij} \right] $ 에서 $ s $ 행과 $ t $ 행을 바꿔 행렬 $ C = \left[ c_{ij} \right] $ 를 만들었다고 하자.

$ s < t $ 라면 $ c_{sj} = a_{tj} $ 이고 $ i \neq s, i \neq t $ 일 때 $ c_{ij} = a_{ij} $ 이다.

따라서

$ | C | = \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) c_{1 \sigma(1)} c_{2 \sigma(2)} \cdots c_{s \sigma(s)} \cdots c_{t \sigma(t)} \cdots c_{n \sigma(n)} $

$ = \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) a_{1 \sigma(1)} a_{2 \sigma(2)} \cdots a_{t \sigma(s)} \cdots a_{s \sigma(t)} \cdots a_{n \sigma(n)} $

$ = \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) a_{1 \sigma(1)} a_{2 \sigma(2)} \cdots a_{s \sigma(t)} \cdots a_{t \sigma(s)} \cdots a_{n \sigma(n)} $

이다. 이는 앞서 부호화 함수 부분을 참고하면 다음과 같다.

$ | C | = - \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) a_{1 \sigma(1)} a_{2 \sigma(2)} \cdots a_{s \sigma(s)} \cdots a_{t \sigma(t)} \cdots a_{n \sigma(n)} = - |A| $

$ A $ 에 $ kR_i $ 연산을 하여 행렬 $ C $ 를 만든다면 $ | C | = k | A | $ 이다.

$ A = \left[ a_{ij} \right] $ 에서 $ s $ 행에 $ k $ 배하여 행렬 $ C = \left[ c_{ij} \right] $ 를 만들었다고 하자.

$ c_{sj} = k a_{sj} $ 이고, $ i \neq s $ 일 때 $ c_{ij} = a_{ij} $ 이다.

따라서

$ | C | = \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) c_{1 \sigma(1)} c_{2 \sigma(2)} \cdots c_{s \sigma(s)} \cdots c_{n \sigma(n)} $

$ = \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) a_{1 \sigma(1)} a_{2 \sigma(2)} \cdots \left( k a_{s \sigma(s)} \right) \cdots a_{n \sigma(n)} $

$ = k \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) a_{1 \sigma(1)} a_{2 \sigma(2)} \cdots a_{s \sigma(s)} \cdots ca_{n \sigma(n)} $

$ = k | A | $

$ A $ 에 $ kR_i + R_j $ 연산을 하여 행렬 $ C $ 를 만든다면 $ | C | = | A | $ 이다.

$ A = \left[ a_{ij} \right] $ 에서 $ s $ 행에 $ k $ 배하여 $ t $ 행에 더하여 행렬 $ C = \left[ c_{ij} \right ] $ 를 만들었다고 하자.

$ c_{ij} = a_{ij} + k a_{sj} $ 이고, $ i \neq t $ 일 때 $ b_{ij} = a_{ij} $ 이다.

따라서

$ | C | = \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) c_{1 \sigma(1)} c_{2 \sigma(2)} \cdots c_{s \sigma(s)} \cdots c_{t \sigma(t)} \cdots c_{n \sigma(n)} $

$ = \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) a_{1 \sigma(1)} a_{2 \sigma(2)} \cdots a_{s \sigma(s)} \cdots \left( a_{t \sigma(t)} + k a_{s \sigma(s)} \right) \cdots a_{n \sigma(n)} $

$ = \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) a_{1 \sigma(1)} a_{2 \sigma(2)} \cdots a_{s \sigma(s)} \cdots a_{t \sigma(t)} \cdots a_{n \sigma(n)} + k \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) a_{1 \sigma(1)} a_{2 \sigma(2)} \cdots a_{s \sigma(s)} \cdots a_{s \sigma(s)} \cdots a_{n \sigma(n)} $

$ k \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) a_{1 \sigma(1)} a_{2 \sigma(2)} \cdots a_{s \sigma(s)} \cdots a_{s \sigma(s)} \cdots a_{n \sigma(n)} $ 은 $ s $ 와 $ t $ 행이 같으므로 $ 0 $ 이다.

따라서 $ | C | = |A| $ 이다.

행렬 $ E $ 가 기본행렬이면 $ |EA| = |E||A| $ 이다.

 

• 행렬식이 $ 0 $ 인 경우

$ A $ 의 두 행이 같으면 $ |A| = 0 $ 이다.

$ A $ 에서 같은 두 행을 바꾸어 행렬 $ C $ 를 만들었다고 하자.

즉 $ R_i \leftrightarrow R_j $ 를 한 것이고, 따라서 $ | C | = - | A | $ 이다.

그런데 $ | A | = | C | $ 이므로, $ | A | = 0 $ 이다.

$ A $ 의 한 행이 모두 $ 0 $ 이면 $ | A | = 0 $ 이다.

$ A $ 의 한 행이 다른 행의 상수 배이면 $ | A | = 0 $ 이다.

한 행의 상수배한 행렬의 행렬식은 원래 행렬식의 $ k $ 배인데, 어느 한 행이 다른 행의 $ k $ 배라면 그 행에 $ \frac{1}{k} $ 를 곱해 같은 행으로 만들 수 있고, 같은 행이 존재하는 행렬의 행렬식은 $ 0 $ 이다.

 

• 전치행렬

$ A $ 에 대하여 $ | A^T | = |A| $ 이다.

 

• 역행렬

$ A $ 가 가역일 필요충분조건은 $ | A | \neq 0 $ 이다.

$ A $ 가 가역이면 $ | A^{-1} | = \dfrac{1}{|A|} $ 이다.

 

• 삼각행렬

$ A = \left[ a_{ij} \right] $ 가 삼각행렬이라면 $ |A| = a_{11} a_{22} \cdots a_{nn} $ 이다.

이를 통해서 역행렬을 구할 때 처럼 행렬에 기본행 연산을 하여 삼각행렬로 변형시킨다면 행렬식을 구할 수 있다.

 

• 곱

$ |AB| = |A||B| $ 이다.