이번 시간부터는 행렬식에 대해 다룹니다. 다음 글에서 행렬식에 대해 본격적으로 다루기 앞서 이번 시간에는 치환이라는 함수에 대해 배워보겠습니다.
자연수 $n$에 대하여 집합 $N_n=\left\{ 1, 2, \cdots, n \right\}$에서 $N_n$으로 가는 일대일대응(전단사함수)을 치환, 좀 더 정확히는 $n-$치환이라고 한다. 치환은 $\sigma$라는 기호로 표기하며, $n-$치환은 다음과 같이 나타낸다.
$$\begin{pmatrix} 1 & 2 & \cdots &n \\ \sigma(1) & \sigma(2) & \cdots & \sigma(n) \end{pmatrix}$$
항등치환 $\mathrm{id}_n(k)=k(1 \leq k \leq n)$는 당연히 치환입니다.
또한 다음 함수는 치환이지만,
$$\begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 2 & 1 & 3 \end{pmatrix}$$
다음 함수는 치환이 아닙니다.
$$\begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 1 & 1 & 3 \end{pmatrix}$$
두 $n-$치환 $\sigma_1$, $\sigma_2$에 대하여
- $\sigma_1 \circ \sigma_2$를 $n-$치환의 곱, 또는 함성이라고 부르고, $\sigma_1 \sigma_2$로 쓴다.
- $\sigma_1 \sigma_2 = \sigma_2 \sigma_1 = \mathrm{id}_n$이면 $\sigma_2 = \sigma_1^{-1}$이고, 역치환이라고 부른다.
다음은 치환의 합성이 계산되는 예시입니다.
$$\begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix}$$
한편
$$\begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix}$$
$$\begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix}$$
이므로 $ \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix}$의 역치환은 $\begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}$입니다.
$N_n = \left\{ 1, 2, \cdots, n \right\}$에 대하여 집합 $\left\{ (i, j) \in N_n \times N_n | i < j, \sigma(i) > \sigma(j) \right\}$의 원소의 개수를 치환 $\sigma$의 전도의 수라고 정의하고 $N(\sigma)$라고 표기한다.
정의가 좀 어렵죠? 조금 더 쉽게 표현하면
$\sigma(2)$, $\sigma(3)$, $\cdots$, $\sigma(n)$중에서 $\sigma(1)$보다 작은 것의 개수
$\sigma(3)$, $\sigma(4)$, $\cdots$, $\sigma(n)$중에서 $\sigma(2)$보다 작은 것의 개수
$\vdots$
$\sigma(n)$중에서 $\sigma(n-1)$보다 작은 것의 개수
를 모두 더한 값입니다.
예를 들어서 치환
$$ \sigma = \begin{pmatrix}1 & 2 & 3 & 4 \\4 & 3 & 1 & 2 \\\end{pmatrix} $$
에서 $N(\sigma) = 3 + 2 + 0 = 5$입니다.
이번에는 치환의 독특한 경우인 호환에 대해 살펴봅시다.
치환 중에서 두 원소만 바꾸고 나머지 원소는 바꾸지 않는 것을 호환이라고 부른다. 즉, 다음과 같은 $n-$치환을 호환이라고 부르며, $(i ~~ j)$ 또는 $(j ~~ i)$라고 나타낸다.
$$\sigma(k) = \left\{ \begin{array}{ll} j & (k = i) \\ i & (k=j) \\ k & (k \neq i, k \neq j) \end{array} \right.$$
호환의 기호는 $\tau$이다.
호환에는 다음과 같은 중요한 성질이 있습니다.
모든 $n-$치환은 호환의 곱으로 나타내어진다. ($n \geq 2$)
$n$에 대한 수학적 귀납법으로 증명할 수 있습니다. 먼저 $n=2$일 때는 자명합니다.
다음으로 $n \geq 3$일 때를 살펴봅시다.
$\sigma(n)=n$이라면 이 $n-$치환은 $(n-1)-$치환이라고 볼 수 있으므로 귀납 가정에 의해 참입니다.
$\sigma(n)=k \neq n$이라면 호환 $(n ~~ k)$와 합성하여 $(n-1)-$치환 $(n ~~ k) \sigma$를 얻습니다. 귀납가정에 의해
$$(n ~~ k) \sigma = \tau_p \cdots \tau_2 \tau_1$$
인 호환 $\tau_1$, $\tau_2$, $\cdots$, $\tau_p$가 존재하므로
$$\sigma = (n ~~ k) \tau_p \cdots \tau_2 \tau_1$$
입니다.
$N(\sigma \tau)$와 $N(\sigma)$의 홀짝은 다르다.
먼저 $\tau$가 인접호환 $(k ~~ k+1)$인 경우를 살펴보면
$\sigma(i)$, $\sigma(i+1)$, $\cdots$, $\sigma(n)$중에서 $\sigma(i)$보다 작은 것의 개수 $N_i(\sigma)$
와
$\sigma \tau(i)$, $\sigma \tau(i+1)$, $\cdots$, $\sigma \tau(n)$중에서 $\sigma \tau(i)$보다 작은 것의 개수 $N_i(\sigma\tau)$
는 $2 \leq i \leq k-1$ 또는 $k+2 \leq i \leq n$일 때 같으므로 $i = k$, $i = k+1$일 때만 살펴보면 됩니다.
$\sigma \tau (k) = \sigma(k+1)$, $\sigma \tau (k+1) = \sigma(k)$이므로
- $\sigma(k+1) > \sigma(k)$일 때 $N_k(\sigma\tau) = N_k(\sigma) + 1$, $N_{k+1}(\sigma\tau) = N_{k+1}(\sigma)$입니다. 따라서 $N(\sigma \tau) = N(\sigma) + 1$이므로 $N(\sigma \tau)$와 $N(\sigma)$의 홀짝은 다릅니다.
- $\sigma(k+1) < \sigma(k)$일 때 $N_k(\sigma\tau) = N_k(\sigma) - 1$, $N_{k+1}(\sigma\tau) = N_{k+1}(\sigma)$입니다. 따라서 $N(\sigma \tau) = N(\sigma) - 1$이므로 $N(\sigma \tau)$와 $N(\sigma)$의 홀짝은 다릅니다.
따라서 $N(\sigma \tau)$와 $N(\sigma)$의 홀짝은 다릅니다.
이제 일반적인 호환에 대해서 살펴봅시다. 일반적인 호환은 다음과 같이 홀수 번($j^2-j+1$)의 인접호환의 곱으로 표현가능합니다.
$$(i ~~ i+j)= \sigma^{n-1} \circ (i+j-1 ~~ i+j) \circ \sigma$$
$$\left( \sigma = (i+j-2 ~~ i+j-1)\cdots(i+1 ~~ i+2)(i ~~ i+1) \right)$$
따라서 $N(\sigma \tau)$와 $N(\sigma)$의 홀짝은 다릅니다.
전도의 수의 짝수와 홀수를 왜 따지는지, 호환의 개념은 왜 등장하는지 궁금하셨을 것 같습니다. 이는 홀치환과 짝치환이라는 개념을 도입하기 위함이었습니다.
홀수개의 호환의 곱으로 나타내어지는 치환을 홀치환, 짝수개의 호환의 곱으로 나타내어지는 치환을 짝치환이라고 한다.
치환에는 부호수가 있어서 홀치환의 부호수는 $\mathrm{sgn}(\sigma) = -1$이고, 짝치환의 부호수는 $\mathrm{sgn}(\sigma) = 1$이다.
홀치환이 바르게 정의되기 위해서는 어떤 치환이 홀수개의 호환의 곱으로 나타내어졌다면, 다른 임의의 방법으로 나타내더라도 홀수개의 호환의 곱으로 나타내어져야 합니다. 짝치환에 대해서도 마찬가지입니다.
- 항등치환은 짝치환이다. ($\mathrm{sgn}(\mathrm{id}) = 1$)
- $\tau_k \cdots \tau_2 \tau_1 = \tau_{k'}' \cdots \tau_2' \tau_1'$이면 $k$와 $k'$의 홀짝성은 같다.
- $\mathrm{sgn}(\sigma) = \mathrm{sgn}(\sigma^{-1})$
- 치환의 홀짝성은 치환의 전도의 수의 홀짝성과 같다.
1번을 보이면 2, 3번이 참임은 쉽게 알 수 있으니 여기서는 1번과 4번만만 증명하겠습니다. $N(\mathrm{id}) = 0$입니다. 한편 $\mathrm{id} = \tau_l \cdots \tau_2 \tau_1$이라면 (1-39)에 의해 $\mathrm{id}$의 전도의 수는 $l$과 홀짝성이 같습니다. 따라서 $l$은 짝수이고, 항등치환은 짝치환입니다.
다음으로 4번을 증명하겠습니다. 호환의 전도의 수가 홀수임을 보이면 (1-39)에 의해 참임을 쉽게 알 수 있습니다. $i>j$일 때, 호환 $(i ~~ j)$에 대하여
$\tau(j+1)$, $\tau(j+2)$, $\cdots$, $\tau(n)$ 중에서 $\tau(j) = i$보다 작은 것의 개수는 $j-i$
$\tau(j+2)$, $\tau(j+3)$, $\cdots$, $\tau(n)$ 중에서 $\tau(j+1) = j+1$보다 작은 것의 개수는 $1$
$\vdots$
$\tau(i)$, $\tau(i+1)$, $\cdots$, $\tau(n)$ 중에서 $\tau(i-1) = i-1$보다 작은 것의 개수는 $1$
이므로 호환 $(i ~~ j)$의 전도의 수는 $2(i-j)-1$입니다. 따라서 호환의 전도의 수는 홀수입니다.
2번에 의해서 홀치환과 짝치환이 잘 정의되는 개념임을 알 수 있습니다.
치환의 부호(수)라는 개념은 다음시간에 행렬식을 정의할 때 사용되므로 알아두면 좋을 것입니다.
※ 이 글은 "미적분학 1+-김홍종-서울대학교 출판문화원-2016"을 참고하여 썼습니다.
'교양(학문의 기초) > 공학수학' 카테고리의 다른 글
1. 선형대수학의 기초_(16) 행렬식의 성질 (0) | 2022.08.13 |
---|---|
1. 선형대수학의 기초_(15) 행렬식 (0) | 2022.08.09 |
1. 선형대수학의 기초_(13) 연립일차방정식 (0) | 2022.08.07 |
1. 선형대수학의 기초_(12) 역행렬 (0) | 2022.07.31 |
1. 선형대수학의 기초_(11) 기본행렬과 행렬의 랭크 (0) | 2022.07.31 |