Play

버튜버 연떠 님의 현대 대수학 강의

대칭다항식

변수 $x_1, x_2, \dots, x_n$ 에 대한 다항식 $f(x_1, \dots, x_n)$ 이 모든 치환 $\sigma \in S_n$ 에 대해

$$f(x_1, x_2, \dots, x_n) = f\bigl(x_{\sigma(1)}, x_{\sigma(2)}, \dots, x_{\sigma(n)}\bigr)$$

을 만족할 때, $f$ 를 대칭다항식(symmetric polynomial) 이라고 한다.

예를 들어 다음 다항식들은 $x, y, z$ 에 대한 대칭다항식이다.

• $x + y + z$
• $xy + yz + zx$
• $x^2 + y^2 + z^2$

반면 $x^2 + xy$ 와 같은 다항식은 $x$ 와 $y$ 를 바꾸면 값이 달라지므로 대칭다항식이 아니다.

기본대칭다항식

변수 $x_1, \dots, x_n$ 에 대해 기본대칭다항식(elementary symmetric polynomials) $e_k$ ($k = 1, \dots, n$)는 다음과 같이 정의된다.

• $e_1 = x_1 + x_2 + \cdots + x_n$
• $e_2 = \displaystyle\sum_{1 \le i < j \le n} x_i x_j$
• $e_3 = \displaystyle\sum_{1 \le i < j < k \le n} x_i x_j x_k$
• $\dots$
• $e_n = x_1 x_2 \cdots x_n$

즉, $e_k$ 는 서로 다른 $k$개의 변수 곱을 모두 더한 다항식이다. 예를 들어 $n = 3$ 인 경우 기본대칭다항식은 아래와 같다.

$$e_1 = x + y + z, \quad e_2 = xy + yz + zx, \quad e_3 = xyz$$

$x + y + z$ 는 기본대칭다항식이지만 $x^2 + y^2 + z^2$는 기본이 아닌 대칭다항식이다.

대칭다항식의 기본정리

임의의 대칭다항식 $f(x_1, \dots, x_n)$ 은 기본대칭다항식들 $e_1, \dots, e_n$ 을 변수로 하는 다항식 $g$ 가 존재하여

$$f(x_1, x_2, \dots, x_n) = g\bigl(e_1, e_2, \dots, e_n\bigr)$$

와 같이 쓸 수 있다.

• 모든 대칭다항식은 $e_1, \dots, e_n$ 의 다항식으로 표현할 수 있다는 의미에서, $e_1, \dots, e_n$ 은 대칭다항식들의 기본 생성자 역할을 한다. 즉, 대칭다항식은 기본대칭다항식의 조합으로 표현할 수 있다.
• 대칭다항식의 기본정리와 비에트 정리에 의해 변수가 n개인 임의의 대칭다항식에 n차 방정식의 모든 근을 대입한 식의 값은 방정식의 계수의 사칙연산으로 표현할 수 있다.

e.g.

$x, y$ 에 대한 대칭다항식

$$f(x, y) = x^2 + y^2$$

은 다음과 같이 기본대칭다항식의 조합으로 나타낼 수 있다.

$$(x + y)^2 = x^2 + 2xy + y^2$$ $$x^2 + y^2 = (x + y)^2 - 2xy = e_1^2 - 2 e_2$$ $$f(x, y) = x^2 + y^2 = e_1^2 - 2 e_2$$

같은 방식으로 $x^3 + y^3$, $x^2y^2 + y^2z^2 + z^2x^2$ 등 다양한 대칭다항식들을 $e_1, e_2, \dots$ 의 식으로 변환할 수 있다.

위의 정리를 통해서 근의 사칙연산으로 계수를 정의할 수 있게 되었으니 다시 이를 통해 방정식의 근을 사칙연산으로 풀 수 있지 않은가? 하는 생각을 하게 됨.

치환의 성질

• 합성: $\sigma, \tau \in S_n$ 에 대해 $(\sigma \circ \tau)(i) = \sigma(\tau(i))$ 로 정의한다.
• 단위원: 모든 원소를 그대로 두는 항등 치환 $\mathrm{id}$ 가 존재한다.
• 역원: 각 치환 $\sigma$ 에 대해 $\sigma(i) = j$ 이면 $\sigma^{-1}(j) = i$ 인 역치환이 존재한다.
• 연산의 비가환성: 일반적으로 $\sigma \circ \tau \ne \tau \circ \sigma$ 이다.

순환치환(Cycle permutation)

$\{1,\dots,n\}$ 의 서로 다른 원소 $a_1, a_2, \dots, a_k$ 에 대해

• $a_1 \mapsto a_2,\ a_2 \mapsto a_3,\ \dots,\ a_{k-1} \mapsto a_k,\ a_k \mapsto a_1$ 로 보내고
• 그 밖의 모든 원소는 자기 자신으로 보내는 치환

을 길이 $k$ 의 순환치환(cycle) 이라 하고, $(a_1\ a_2\ \dots\ a_k)$ 와 같이 쓴다.

e.g.

• $\sigma = (1\ 3\ 4)$ 는 $1 \mapsto 3,\ 3 \mapsto 4,\ 4 \mapsto 1$.
• 길이 $2$ 의 순환치환 $(a\ b)$ 를 특히 호환(transposition) 라고 부른다.
• 임의의 순환 치환은 호환의 합성으로 나타낼 수 있다. -> 중요

서로소 순환들의 곱

두 순환치환의 원소가 서로 겹치지 않으면, 이 둘을 서로소(disjoint) 라고 한다.
예를 들어 $(1\ 3\ 4)$ 와 $(2\ 5)$ 는 서로소이다.

서로소 순환들은 작용하는 원소가 다르므로, 합성 순서에 상관없이 같은 결과를 낸다.

• $(1\ 3\ 4)\,(2\ 5) = (2\ 5)\,(1\ 3\ 4)$

이런 이유로 치환을 여러 개의 서로소 순환들의 곱으로 쓰면, 그 표현이 구조적으로 안정적이고 해석이 쉬워진다.

순환분해정리

어떤 치환 $\sigma \in S_n$ 이든지, $\sigma$ 를 유한 개의 서로소 순환치환의 합성으로 나타낼 수 있고, 이 표현은 순환들의 순서를 제외하면 유일하다.

• 존재: 집합의 한 원소에서 시작해 $\sigma$ 를 계속 적용하면, 유한 집합이므로 언젠가 되돌아오고, 그때까지의 궤적이 하나의 순환을 이룬다. 이 과정을 아직 방문하지 않은 원소들에 대해 반복하면, 전체가 순환들의 곱으로 쪼개진다.
• 유일성: 서로소 순환들의 각 지지 집합은 치환의 궤적에 의해 결정되므로, 어떤 순환분해를 하든 같은 궤적끼리 하나의 순환을 이루게 된다. 순환의 표기에서 시작점만 바꾸는 $(1\ 3\ 4)$ 와 $(3\ 4\ 1)$ 같은 차이는 본질적으로 같은 순환이다.

e.g.

$S_7$ 에서 치환 $\sigma$ 가

• $1 \mapsto 3,\ 3 \mapsto 5,\ 5 \mapsto 1$
• $2 \mapsto 4,\ 4 \mapsto 2$
• $6 \mapsto 7,\ 7 \mapsto 6$

을 만족한다면, 순환분해는

$$\sigma = (1\ 3\ 5)\,(2\ 4)\,(6\ 7)$$

로 쓸 수 있다.

여기서 $(1\ 3\ 5)$, $(2\ 4)$, $(6\ 7)$ 은 서로소 순환들이므로, 곱의 순서를 바꾸어도 같은 치환을 나타낸다.

치환의 부호

한 치환 $\sigma$ 를 호환의 곱으로

$$\sigma = \tau_1 \tau_2 \cdots \tau_k$$

와 같이 썼을 때, 호환의 개수 $k$ 의 홀짝성(짝수/홀수)은 항상 같다. 이 홀짝성을 이용해서 치환의 부호를 정의한다.

• $\sigma$ 가 호환의 짝수 개 곱으로 표현되면 짝치환(even permutation) 이라고 한다.
• $\sigma$ 가 호환의 홀수 개 곱으로 표현되면 홀치환(odd permutation) 이라고 한다.
• 치환의 부호(sign)를 $$\operatorname{sgn}(\sigma) = \begin{cases} +1 & \text{if } \sigma \text{ is even}, \\ -1 & \text{if } \sigma \text{ is odd} \end{cases}$$ 로 정의한다.

짝치환/홀치환의 연산 성질

치환 $\sigma, \tau \in S_n$ 에 대해 다음이 성립한다.

• 부호는 곱셈에 대해 $$\operatorname{sgn}(\sigma \tau) = \operatorname{sgn}(\sigma)\, \operatorname{sgn}(\tau)$$ 를 만족한다.
• 짝치환의 곱은 항상 짝치환이다.
• 홀치환 두 개의 곱도 짝치환이다.
• 짝치환과 홀치환의 곱은 홀치환이다.

e.g.

$S_3$ 의 치환들을 순환표기와 함께 살펴보면,

• 항등 치환 $\mathrm{id}$ : 호환를 하나도 쓰지 않으므로 짝치환이다.
• $(1\ 2)$, $(1\ 3)$, $(2\ 3)$ : 호환 자체이므로 각각 홀치환이다.
• $(1\ 2\ 3)$, $(1\ 3\ 2)$ 는 호환 두 개의 곱으로 표현되므로 짝치환이다. $(1\ 2\ 3) = (1\ 3)(1\ 2)$

치환행렬

집합 $\{1, 2, \dots, n\}$ 의 치환 $\sigma$ 에 대해, 이에 대응하는 $n \times n$ 행렬 $P$ 를 다음과 같이 정의한다.

• $P$ 의 각 행과 각 열에는 정확히 하나의 원소가 $1$ 이고 나머지는 모두 $0$ 이다.
• $P$ 의 $(i, j)$ 성분을 $P_{ij}$ 라고 할 때, $$P_{ij} = \begin{cases} 1 & \text{if } j = \sigma(i), \\ 0 & \text{otherwise.} \end{cases}$$

이때 $P$ 를 치환 $\sigma$ 에 대응하는 치환행렬(permutation matrix) 이라고 한다.

벡터에 작용하는 의미

열벡터 $x = (x_1, \dots, x_n)^T$ 에 치환행렬 $P$ 를 곱하면,

$$Px = y$$

에서

$$y_i = x_{\sigma(i)}$$

가 된다.

• 즉, $Px$ 는 $x$ 의 성분들을 치환 $\sigma$ 에 따라 재배열한 벡터이다.
• 치환을 함수로 볼 때, 치환행렬은 벡터의 좌표를 섞는 연산을 표현한 것이다.

예를 들어 $n=3$, $\sigma(1)=2,\ \sigma(2)=3,\ \sigma(3)=1$ 이라면

$$P = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}, \quad x = \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} \Rightarrow Px = \begin{pmatrix} x_2 \\ x_3 \\ x_1 \end{pmatrix}.$$

치환행렬의 성질

• 각 행과 각 열에 정확히 하나의 $1$만 있고 나머지는 $0$ 이다.
• 항상 정사각행렬이며, 역행렬이 존재한다. 역행렬은 대응되는 역치환 $\sigma^{-1}$ 의 치환행렬이다.
• 직교행렬이다. $$P^{-1} = P^T$$ 이 성립하므로, 치환행렬의 열벡터(또는 행벡터)는 서로 직교하고 길이가 $1$ 인 표준기저의 치환이다.
• 행렬 곱셈은 치환의 합성에 해당한다. 치환 $\sigma, \tau$ 에 대응하는 치환행렬을 각각 $P_\sigma, P_\tau$ 라고 하면 $$P_\sigma P_\tau = P_{\sigma \circ \tau}$$ 가 된다.

표준기저의 관점

$\mathbb{R}^n$ 의 표준기저를 $e_1, \dots, e_n$ 이라 하자.
치환행렬 $P$ 는

$$P e_i = e_{\sigma(i)}$$

를 만족한다.

즉, 치환행렬은 표준기저를 서로 섞는(permute 하는) 선형사상이다.

그래픽스에서 행렬 연산 등의 수학 함수들을 구현할 때 별 생각없이 전치행렬를 구현했었는데, 치환의 정의에서부터 시작하여 호환의 개념, 케일리 표기와 행렬의 형태의 유사성으로부터 치환행렬을 정의하는 부분에 대한 설명을 듣고, 다양한 관점에서의 해석을 보게 되니 신선하게 느껴졌다.