Permutation

제 2편: 대칭군의 정의

오늘의 목표:

비아벨군에 대해서 배워봅시다.
순열에 대해서 알아봅시다.
대칭군을 정의하고, 대칭군이 비아벨군임을 보여봅시다.

네, 안녕하세요. 원들대의 원생입니다. 지난 시간에는 군의 정의를 살펴보았고, 또한 가환성이 성립하는 군, 이른바 아벨군의 두 예제를 살펴보았습니다. 바로 덧셈군과 곱셈군을 말이죠. 더 나아가 무한군과 유한군의 예제를 살펴보았습니다. 이번 시간에는 가환성을 만족하지 않는 군에 대해서 알아볼까 합니다. 저번 시간에 집합 $G$ 가 연산자 $*$ 에서 군이 된다면 이를 $(G,*)$ 라고 표기한다고 말씀드렸죠? 만약 이 연산자 $*$ 가 가환성을 만족하지 않는다면, 다시 말해 $G$ 가 $a *b \neq b* a$ 을 만족하는 원소쌍 $a,b$ 가 하나라도 존재한다면 이 $G$ 를 비아벨군(non-abelian group)이라고 부릅니다.

오늘 살펴볼 비아벨군의 예제로는 대칭군(symmetric group)이 있겠습니다. 대칭군은 순열(permutation)으로 이루어진 집합인데, 순열에 가장 대표적인 예로는 사다리타기가 있겠습니다. 아마 여러분들도 술자리나 친구들과 같이 복불복을 즐기면서 사다리타기를 해보신 적이 있을거에요. 사다리타기는 각기 다른 시작점에서 모두 다른 끝점에 도달한다는 흥미로운 성질이 있습니다. 예컨대 4개의 줄이 그려진 사다리 타기를 가정하고, 시작점은 1, 2, 3, 4로 끝점은 a, b, c, d로 번호를 매겨봅시다. 만약 1번 시작점은 c번 끝점으로, 2번 시작점은 b번 끝점으로, 3번 시작점은 d번 끝점으로, 마지막으로 4번 시작점은 a번 끝점으로 간다면, 이는 다음과 같은 함수로 여겨질 수 있습니다.

$f(1) = c, f(2) = b, f(3) = d, f(4)=a$ .

자, 이 함수 $f(x)$ 의 정의역(domain)의 크기, 즉 $x$ 에 들어갈 수 있는 값의 개수는 1,2,3,4로 총 4개입니다. 애초에 사다리가 4개의 줄밖에 없기 때문이죠. 그리고 공역(codomain)의 크기, 그 결과의 값의 개수도 마찬가지로 a, b, c, d로 4개입니다. 이 함수는 두개의 다른 값을 대입했을 때 같은 값이 나오지 않습니다. 즉, $x$ 와 $y$ 가 1과 4 사이의 다른 숫자라면, $f(x)$ 와 $f(y)$ 의 결과는 같지 않습니다. 이를 단사(injectivity; one-to-one)라고 부릅니다. 또한 치역의 모든 원소, 즉 a, b, c, d에 상응하는 정의역의 원소가 존재합니다. 이를 전사(surjectivity; onto)라고 일컫습니다. 이 함수는 전사이며 동시에 단사이므로 이를 전단사(bijectivity)라고 합니다. 순열이란 이런 이런 전단사 함수들을 말합니다.

심화: 함수 $f$ 가 집합 $A, B$ 를 각각 정의역과 공역으로 삼는다면, 이를 $f: A \to B$ 로 표기하곤 합니다. 여기서 $x$ 를 $A$ 의 원소라 할 때, $f(x)$ 로 이루어진 집합, 즉 함수 $f$ 의 출력값의 집합을 치역(range)이라고 부릅니다. 치역이 공역의 부분집합이지만, 간혹 치역이 공역인 경우가 존재합니다. 이 경우 함사를 전사라고 합니다. 이번엔 전사도 단사도 아닌 함수의 예제를 하나 살펴보자면, 실수 $\mathbb{R}$ 를 정의역과 공역으로 삼는 함수 $f: \mathbb{R} \to \mathbb{R}$ 를 다음과 같이 정의해봅시다: $f(x) = x^2$ . 이 함수는 단사는 아닙니다. $x \neq y$ 이지만 $f(x) = f(y)$ 를 만족하는 실수쌍이 존재하기 때문이죠., 예컨대 $x= 1, y = -1$ 이 있겠습니다. 또한 전사도 아닙니다. 실수중엔 제곱해서 음수가 되는 수가 없습니다. 즉 이 함수의 치역은 음수가 아닌 모든 실수이나, 공역은 모든 실수이므로 치역이 공역보다 확실히 작습니다.

위의 사다리의 경우로 다시 돌아가봅시다. 이번에는 a, b, c, d 를 1, 2, 3, 4로 표기했다고 가정해봅시다. 그렇다면 이 사다리타기의 순열은 어떻게 수학적으로 표기하는지 한번 배워봅시다. 자, 1번 시작점은 3번 끝점으로, 2번 시작점은 2번 끝점으로, 3번 시작점은 4번 끝점으로, 마지막 4번 시작점은 1번 끝점으로 갑니다. 이는 다음과 같이 표기합니다: $(134)(2)$ . 이 표기는 왼쪽에서 부터 읽으면 됩니다. 1다음에 오는 숫자는 3이니, 1번 점은 3번 점으로, 3 다음에 오는 숫자가 4니 3번 점은 4번 점으로, 4번에서는 괄호가 끊기는 군요, 그러므로 다시 괄호안의 첫번째 항인 1번 점으로 돌아온다고 봐줄 수 있습니다. 마지막으로 2번 점은 2번으로 오니 2 하나만 들어있는 괄호로 표기가 가능합니다. 이렇게 괄호안에 숫자가 하나만 들어가있는 경우는 종종 생략해주기도 합니다. 여기서 각각의 괄호를 순환(cycle)이라고 부릅니다.

자 그렇다면 숫자가 네개로 이루어진 순열은 얼마나 다양한 원소들이 있을까요? 다음과같이 모두 나열해 볼 수 있겠습니다.

$(1)(2)(3)(4), (12)(3)(4), (13)(2)(4), (14)(2)(3), (1)(23)(4), (1)(24)(3), (1)(34)(2),$

$(123)(4), (132)(4), (124)(3), (142)(3), (134)(2), (143)(2), (1)(234), (1)(243),$

$(12)(34), (13)(24), (14)(23), (1234), (1243), (1324), (1342), (1423), (1432)$

이렇게 총 24개의 원소가 있습니다. 다시 말해, 줄이 4개인 사다리타기는 어떻게 그리든 상관 없이, 위의 24개의 결과 중 하나에 해당한다고 볼 수 있습니다.

문제 1: 그렇다면 줄이 세개인 사다리의 순열은 모두 무엇이 있을까요? 모두 나열해보세요.

문제 2: 위의 제시된 24개의 원소는 필자의 임의대로 모두 첫번째 오는 숫자가 1이 오도록 적었습니다. 사실 첫번째 숫자가 1이 아닌 다른 숫자가 오도록 표기할 수 있습니다. 예컨대 $(12)(34)$ 는 $(43)(12)$ 와 같습니다. $(1324)$ 는 $(3241)$ 과 같으며, $(142)(3)$ 은 $(3)(421)$ 과 같습니다. 위의 모든 원소를 2가 처음오도록 표기해보세요. 꼭 표기법이 하나만 있다는 보장은 없습니다.

자 이번엔 이런 순열에 연산을 취해봅시다. 어떻게 취햐나고요? 사다리타기의 예제로 다시 잠깐 돌아가봅시다. 4개의 줄로 그려진 두개의 사다리타기를 A와 B라고 둡시다. 여기서 B의 첫번째 시작점을 A의 첫번째 끝점에, 마찬가지로 두번째, 세번째, 그리고 네번재 시작점도 마찬가지로 접붙였다고 가정합시다. 이렇게 나온 결과는 기존의 A와 B와는 또 다른 새로운 사다리가 생깁니다. 여기서 주의할 점은 A가 위로 오게 그리느냐, B가 위로 오게 그리느냐에 따라서 그 결과는 다른 사다리가 나올 수 있다는 점입니다. 즉 사다리타기의 경우 이렇게 접붙임을 연산으로 이해해줄 수 있습니다. 이 연산을 순열의 조합(composition)이라고 부릅니다. 이를 자 그렇다면 앞서 소개한 표기법으로 연산은 어떻게 정의될까요?

자 A라는 사다리가 $(132)(4)$ 에 해당하고, B라는 사다리가 $(14)(23)$ 에 해당한다고 가정합시다. 그랬을 때 A가 위에, B가 아래에 오도록 접붙인 사다리는 $(14)(23)(132)(4)$ 라고 표기합니다. 아래에 오는 사다리의 순열을 그대로 적고, 바로 이어서 위에오는 사다리의 순열을 적어주는 것입니다. 하지만 이 꼴은 위에 제시된 24개의 원소와는 사뭇 다른 모양을 띄는 것 처럼 보이지만, 순열의 연산을 취해주면 조금 더 모양이 간단해지게 됩니다. 순열 연산의 규칙은 다음과 같습니다. 처음엔, 숫자 1을 마음속에 두곤, 가장 오른쪽 괄호서부터 살펴봅니다. 만약 괄호 안에 1이 없다면, 그 다음 괄호로 넘어가 1이 들어가 있는지 살핍니다. 반대로 1이 들어가 있다면, 괄호 안에서 1 다음에 뒤따라오는 숫자를 취합니다. 그리고 왼쪽 괄호로 넘어가 이번엔 그 숫자가 있는지 없는지 살피며 같은 규칙을 반복합니다. 가장 왼쪽, 즉 마지막 괄호까지 모두 살펴봤을 때의 그 결과를 모두 기입합니다. 마찬가지로 2,3,4에 대해서도 이 규칙을 실행해줍니다.

조금 말로 설명하려 하니 복잡해보이네요, 한번 실제로 위의 경우를 해볼까요? 자 1의 경우, 가장 오른쪽 괄호 $(4)$ 에는 1이 포함되어있지 않으니 1을 가지고 바로 왼쪽 괄호로 넘어옵니다. 해당 괄호는 $(132)$ 로 1이 들어가 있군요. 그럼 1 다음에 오는 숫자 3을 가지고, 그 다음 괄호로 넘어갑니다. 그 괄호는 $(23)$ 으로, 3을 2로 보내는군요. 그 2를 가지고 가장 왼쪽 괄호로 옵니다. 해당 괄호에는 2가 없군요. 그러므로 전체 순열은 1을 2로 보내준다고 볼 수 있습니다. 자 이번에는 2를 가장 오른쪽에서부터 살펴볼게요. 역시 $(4)$ 에는 2가 없으니 패스, 뒤따라오는 $(132)$ 에는 2가 1로 보내집니다. 그 다음 $(23)$ 에는 1이 없고, 마지막 괄호는 $(14)$ 이므로 1이 4로 보내지는군요. 즉 전체적으로 봤을 때 2는 4로 보내줍니다. 같은 규칙을 적용하면 3은 3으로 , 4는 1로 보내지게 됩니다. 즉, 1은 2, 2는 4, 4는 1, 3은 3이므로, 이를 순열의 표기로 쓰면 $(124)(3)$ 이 됩니다.

자 그렇다면 B가 위에, A가 아래에 오도록 한 사다리는 어떨까요? 이 경우는 표기로 $(132)(4)(14)(23)$ 으로 표기할 수 있겠군요. 마찬가지로 이 경우를 계산해볼까요? 자 마찬가지로 1부터 봅시다. $(23)$ 에는 1이 없으니 넘어갑니다. $(14)$ 로 하여금 1은 4로 보내지는군요. $(4)$ 는 4를 여전히 4로 갖고 있으며, 마지막 괄호에는 4가 없으니, 결과적으로 1은 4로 보내집니다. 나머지 2,3,4를 보면 각각 2, 1, 3으로 보내집니다. 그러므로 이 경우의 결과는 $(143)(2)$ 가 됩니다. 앞서 A가 위에 오도록 그린 사다리와는 전혀 다른 결과를 갖는군요. 네 그렇습니다. 순열의 조합은 교환법칙을 성립하지 않습니다. 즉 비가환(non-commutative)합니다.

자 그렇다면, 이번엔 이 원소들의 집합이 군을 이루는지 살펴볼까요? 일단 군을 이루기 위해서는 순열 연산이 결합법칙을 성립해야 합니다. 다시말해, 위의 24개의 순열 중 임의의 3 순열 $\sigma, \tau, \rho$ 를 가정했을 때, $\sigma (\tau \rho)$ 와 $(\sigma \tau)\rho$ 임을 보이는 것인데, 이 증명은 조금 기술적인 관계로 생략하겠습니다. 이 집합에 항등원에 해당되는 순열은 무엇일까요? 그는 바로 $(1)(2)(3)(4)$ 입니다. 이는 사다리로 그렸을 때에는 수평선줄이 전혀 없는 4개의 줄로 여겨줄 수 있습니다. 이를 임의의 사다리 A에 위나 아래에 접붙여주더라도 기존의 A와 여전히 같은 결과를 내놓기 때문이죠. 숫자가 하나뿐인 괄호는 종종 생략한다고 말씀드렸죠? $(1)(2)(3)(4)$ 의 경우는 모두가 숫자가 하나뿐인 괄호니 모두 생략하면 표기상 의미가 불분명하니, 항등원을 의미하는 $e$ 로 대신 써주곤 합니다.

문제 3: 앞서 언급했듯, 항등원을 제외한 모든 순열의 경우 숫자가 하나뿐인 괄호는 생략해줄 수 있다고 했습니다. 문제 1에서 표기했던 6개의 원소, 그리고 위에 언급했던 24개의 원소를 위와 같은 방법으로 표기해보세요.

문제 4: 순열의 조합은 일반적으로 교환법칙을 만족하지 않지만, 간간히 교환법칙을 만족하는 순열도 존재합니다. 위의 24개의 순열들 중 $(12)\sigma = \sigma(12)$ 를 만족하는 순열들을 모두 나열해보세요.

마지막으로 그러면 각 순열에 대해서 역원은 존재할까요? 이 역시 사다리로 쉽게 파악해줄 수 있습니다. 다시 줄 네 개짜리 사다리를 그려봅시다. 예컨대 1번은 3번, 2번은 4번, 3번은 2번, 4번은 1번으로 향한다고 가정해 볼게요. 이렇게 그린 사다리를 이번엔 뒤집어 봅시다. 사다리를 뒤집어도 여전히 사다리의 모양새를 띄고 있습니다. 이 사다리의 3번 시작점을 보고 천천히 내려와볼까요? 기존 사다리가 1번을 3번으로 보냈으니 뒤집은 사다리는 3번을 1번으로 다시 보낼 겁니다. 마찬가지로 4번은 2번, 2번은 3번, 마지막으로 1번은 4번으로. 이렇게 뒤집은 사다리를 기존의 사다리의 아래 혹은 위에 접붙여주면, 결과적으로 n번 시작점은 n번 끝점으로 보내주는 사다리가 나오게 됩니다. 기존의 사다리는 순열로는 $(1324)$ 의 꼴을 띄고 있었고, 뒤집은 사다리는 $(1423)$ 의 꼴을 띄고 있네요. 이 둘을 취해 $(1324)(1423)$ 을 계산해보면 $e$ 가 나오게 됩니다. 이 외에 임의의 순열의 경우도, 그에 상응하는 사다리가 있고, 그 사다리를 뒤집은 것도 여전히 잘 정의된 사다리이며 이에 해당하는 순열이 존재하니, 각 순열에는 그 역원이 존재한다는 것이 보여집니다. 그러므로 순열의 집합은 군을 이룹니다. 이 경우 총 4개의 숫자들을 뒤섞은 순열들의 집합이므로 이를 $S_4$ 라고 표기합니다. 여기서 알파벳 S는 대칭군을 의미하는 Symmetric Group의 첫글자를 따왔다고 합니다.

문제 5: $S_1, S_2, S_3$ 을 정의하고, 각각의 기수를 구해보세요. $S_4$ 의 기수가 24인 것을 미루어보아 $S_5$ 의 기수는 몇일까요? $S_n$ 의 기수는 일반적으로 몇일까요?

자 오늘은 이렇게 대칭군을 정의해보았습니다. 원래 이번 편에서 대칭군 외에도 소개하고 싶었던 비아벨군이 2개가 더 있었는데, 아무래도 다음 시간으로 미뤄야겠군요. 어떤가요, 대칭군이 조금 흥미롭게 느껴졌나요? 대칭군은 대수학 이외에도 조합론에서도 흥미로운 연구대상으로 손꼽힙니다. 관심이 가신다면 한번 조금 찾아보길 권유해드리고 싶네요. 다음 시간에는 대칭군 말고 또다른 비아벨군의 예제를 몇 개 살펴보도록 할게요.

이번 편은 LA로 향하는 Surfliner 기차 안에서, 노리플라이 – 바라만 봐도 좋은데와 함께 했습니다. 🙂

문제 1: 그렇다면 줄이 세개인 사다리의 순열은 모두 무엇이 있을까요? 모두 나열해보세요.

답) $(1)(2)(3), (12)(3), (13)(2), (23)(1), (123), (132)$ 총 여섯개가 있습니다.

답)

$(2)(1)(3)(4), (21)(3)(4), (2)(13)(4), (2)(14)(3), (23)(1)(4), (24)(1)(3), (2)(34)(1)$

$(213)(4), (231)(4), (241)(3), (214)(3), (2)(134), (2)(143), (234)(1), (243)(1)$

$(21)(34), (24)(13), (23)(14), (2341), (2431), (2413), (2134), (2314), (2143)$

답) $e, (12), (13), (23), (123), (132)$ ,

$e, (12), (13), (14), (23), (24), (34), (123), (132), (124), (142), (134), (143), (234),$

$(243), (12)(34), (13)(24), (14)(23), (1234), (1243), (1324), (1342), (1423), (1432)$

답) 군 $G$ 의 특정한 원소 $x$ 에 대해서 $gx = xg$ 를 만족하는 원소 $g$ 의 집합을 센트럴라이저(Centralizer)라고 부르며, $C_G(x)$ 라고 표기합니다. 이후에 부분군편에서 다룰 예정이지만, 이 집합 역시 군을 이룹니다. 위 문제는 $C_{S_4}(12)$ 를 묻는 것인데, 24개의 원소 중 $e, (12), (34), (12)(34)$ 만이 위 성질을 만족합니다. 첫째로, 항등원 $e$ 는 그 정의에 따라 성질을 만족합니다. $(12)$ 는 자신을 역원으로 삼으니 역시 위 조건을 만족합니다. $(34)$ 는 특별한데, $(12)$ 와 $(34)$ 안에는 공유하고 있는 숫자가 없습니다. 이를 서로소 순환(disjoint cycles)라고 합니다. 대칭군에서 두 서로소 순환은 항상 위의 성질을 만족합니다. 마지막으로, $(12)$ 와 $(34)$ 의 조합 순열인 $(12)(34)$ 도 성질을 만족합니다.

답) $S_1 = \{e\}, S_2 = \{e, (12)\}, S_3 = \{e, (12),(13),(23),(123),(132)\}$ . 그러므로 각각의 기수는 1, 2, 6입니다. 이는 모두 $1!, 2!, 3!$ 에 대응하며 $S_4$ 의 기수인 24 역시 $4!$ 로 이 성질을 만족합니다. 이로 미루어보아, $S_5$ 의 기수는 $5! = 120$ , 그리고 일반적인 $n$ 에 대해서, $S_n$ 의 기수는 $n!$ 로 예상할 수 있습니다. 증명은 다음과 같습니다. 사다리의 관점으로 돌아가, $S_n$ 은 $n$ 개의 시작점을 $n$ 개의 끝점에 대응하는 모든 경우의 수 입니다. 1이 대응될 수로는 총 $n$ 개의 경우의 수가 있고, 2는 $n-1$ , 그렇게 논리를 이어가면, 모든 경우의 수는 $n \cdot (n-1) \cdot \cdots 1 = n!$ 이 됩니다.