Symmetric Group의 개념은 Group 챕터에서 자주 등장한다. 볼때마다 계속 잊어먹고 있는데 잘 숙지해 둬야겠다.

Permutations

permutation of T란 어떤 집합 S = Maps(T,T) - 집합 T를 입력으로 받고 T를 출력으로 내놓는 매핑 함수들의 집합 - 안의 어떤 함수 map f: T ↝ T 가 inverse를 갖고 이것이 일대일 매핑(bijective)할 경우 이 map 함수를 permutation of T 라고 부른다. 이런 permutation들을 집합으로 모아 놓으면 (신기하게도!) group을 형성한다. 예를 들어 identity와 transposition을 나타내는 매핑 i와 𝜏 역시 group을 형성한다. 두 개의 엘리먼트들이 집합 {a,b} 의 permutation인 것이다.

Symmertric Group

정수 1부터 n까지의 집합 {1,2,...,n} 의 permutation 들로 형성된 group을 symmertric group 이라고 부르고 S_n으로 표기한다.

n개의 엘리먼트들의 집합에서 permutation의 갯수는 n!이 된다. 순서가 있는 순열을 생각하면 처음에는 n개의 선택권이, 그 다음에는 (n-1)개, ... 이렇게 해서 총 n!개의 경우의 수가 생긴다. 따라서 symmetric group의 엘리먼트의 개수는 n! 개가 된다. 여기서 이걸 order라고 부른다. 즉, symmetric group의 엘리먼트의 개수는 order 인 것이다.

엘리먼트가 2개로 이루어진 symmetric group S₂는 { i, 𝜏 } 이다. 여기서 𝜏𝜏  = 𝜏² = i 인것을 생각하면, 각 엘리먼트들은 자기자신을 inverse로 갖게 되며, commutative한 abelian group이다.

S₃

엘리먼트가 3개로 이루어진 symmetric group S₃는 order가 6, 즉 엘리먼트를 6개 가지고 있다. symmetric group에서 n이 커지면 커질수록 order는 지수승으로 늘어나기 때문에 매우 복잡해지는데, S₃은 commutative 하지 않은 symmetric group들 가운데 order가 가장 작은 group 이기 때문에 주목할 필요가 있다.

S₃의 모든 엘리먼트들은 (놀랍게도!) 2개의 permutation으로 표현할 수 있다. 이들을 x,y라고 이름짓고, x를 cyclic permutation으로, y를 1,2를 서로 바꾸면서 3을 고정하는 permutation으로 정의해보자.

그러면 집합 {1, 2, 3} 의 permutation 6개는 아래와 같이 x,y 만으로 표현할 수 있다.

1은 identity permutation을 의미한다.

여기서 x³ = 1, y², yx = x²y 이기 때문에 각종 composition들이 group에 닫혀있는지에 대해서나 inverse를 만들어 낼 수 있는지에 대해서도 확인할 수 있다.

Abelian group은 law of composition이 commutative한 group 들을 일컫는다. 아래 예시들은 모두 abelian group이다.

• ℤ⁺: the integers, with addition
• ℝ⁺: the real numbers, with addtion
• ℝ^×: the nonzero real numbers, with multiplication
• ℂ⁺, ℂ^×: the analoguous groups, where the set ℂ of complex numbers replaces the real numbers ℝ

어떤 집합 S의 law of composition을 다음과 같이 정의해보자. 일단 집합 S에서 두 원소 a,b를 뽑는다. 그다음 그 둘을 조합해서 집합 S내의 다른 원소 p로 만든다고 하자.

위의 law of composition을 함수로 생각해보면, 이 함수는 S의 원소 두개를 인자로 받아서 S의 원소 하나로 출력한다. 일종의 map 과 같은 것이다.

여기서 S × S 는 집합 S내의 원소 pair (a, b)의 product를 의미한다.

p = f(a, b)와 같은 functional notiation 은 불편해서 잘 쓰이지 않는다. 대신 law of composition의 종류 혹은 성질에 따라 아래와 같이 덧셈이나 곱셈 등의 많이 쓰인다.

그리고 a와 b를 composition 한 것이 곱셈의 성질을 갖는다면 이걸 product 라고 부를 것이고, 덧셈의 성질을 가질 경우 sum 이라고 부를 것이다.

그러면 n × n matrix 들의 집합에서 law of composition이 matrix multiplication 인 Group을 예로 들어 자세히 살펴보자.

Group에서 중요한 사실 중 하나는 S의 두 원소 a와 b를 composition한 결과인 ab가 역시 S의 원소라는 점이다. 예를 들어 a =  

law of composition에는 associative 와 commutative 라는 특성이 있을 수 있다. associative는 아래와 같은 결합법칙을 의미한다.

그리고 commutative는 아래와 같이 교환법칙을 말한다.

matrix multiplication이 law of composition인 경우에는 associative 하지만 commutative 하지는 않다. 반면, 정수집합에서 덧셈이 law of composition인 경우에는(ℤ⁺) commutative 까지 가능하다. 때문에 보통 associative 한 Group에서 composition을 표기할 경우 곱셈 방식으로 표기하고(commutative 여부는 관심없음), commutative 까지 한 경우는 덧셈 방식으로 표기한다.

일반적으로 associative 한지 여부가 commutative 한지 여부보다 더 근본적으로 중요하게 여겨진다. 그 근거 중에 하나는 composition이 여러개의 함수들인 경우 이들 함수들을 조합하여 하나의 함수로 나타낼 수 있기 때문이다.

예를 들어 집합 T가 있고 T에서 T로 가는(T를 입력으로 받고 T를 내놓는) 함수 g와 f가 있다고 하자. 그리고 g ◦ f 를 조합된 map, t ↝ g(f(t)) 를 나타낸다고 하자. 그리고 S를 T에서 T로 가는 매핑들의 집합이라고 한다면(S = Maps(T,T)), 하나로 조합된 g ◦ f 이 모든 S의 경우에 대해서 law of composition이 될 수가 있다. 함수 레벨에서 하나로 합쳐써도 된다는 이야기다.

다시 단순한 예를 들어보자. 집합 T가 두 원소 a와 b를 가질 때 T에서 T로 가는 매핑의 종류는 모두 네 가지가 된다.

• i: the identity map defined by i(a) = a, i(b) = b;
• 𝜏: the transposition, defined by 𝜏(a) = b, 𝜏(b) = a;
• α: the constant function α(a) = α(b) = a;
• β: the constant function β(a) = β(b) = b.

이들 중 두개를 조합하여 하나의 law of composition을 만든다고 해 보면 그 경우들은 아래와 같이 multiplication table로 나타낼 수 있다.

그리고 이들 중 임의의 2개의 조합의 결과는 아래와 같이 보면 된다.

여기서 𝜏 ◦ α = β 인데 순서를 뒤바꾼 α ◦ 𝜏 = α 이다. 이걸 보면 함수들의 composition은 commutative 하지 않음을 알 수 있다.

방금전 살펴본 2개 함수 조합의 associative를 보다 일반적인 n개를 조합하는 경우로 확장하여 생각해보자.

이들을 어떻게 조합하여 하나의 연산으로 만들 수 있을까? 우선 익숙한 방법인 왼쪽부터 두 개씩 짝을지어 차근차근 조합해 나가는 경우가 있을 수 있다.

만일 n=4 라면 위와 같은 경우를 포함해서 4가지 조합 방법이 있을 수 있다. 예를 들면 (a₁a₂)(a₃a₄) 같은. 그런데 만일 composition 연산이 associative 하다면 이 모든 경우의 함수 조합이 결과적으로는 동일하게 된다(induction으로 증명할 수 있는데 생략한다).

정리를 안하니 계속 잊어먹게 된다. Artin Algebra에서 설명하는 Group 에 대해서 정리해본다.

Group을 한마디로 정의하면, 'law of composition 이 정의되어 있고 각 엘리먼트들은 그 안에서 inverse를 갖는 집합'이다. 책에서 사용하는 정의는 아래와 같다.

Definition. A group is a set G together with a law of composition which is associative and has an identityt element, and such that every element of G has an inverse.

예를 들어 0이 아닌 실수의 집합을 생각해보자. 이 집합의 law of composition을 곱셈이라고 정의하면, 각 원소 k의 inverse는 1/k가 된다. 따라서 이 집합과 law of composition은 Group이 될 수 있으며 수학책에서 보통 ℝ^× 로 표기한다.

다른 예를 들면, 모든 실수의 집합에서 law of composition을 덧셈으로 정의해도 Group으로 만들 수 있다. 이 경우 각 원소 k의 inverse는 -k가 된다. 그리고 이 Group은 ℝ⁺ 으로 표기한다.

책에서 특히 중요하다고 소개하는 Group이 있는데, invertible 한 n × n matrix들의 집합으로서 law of composition이 matrix multiplication인 'General Linear Group' ‐ GL_n 이다. 따라서 GL_n은 아래와 같이 표기할 수 있다.

Artin Algebra 에서 설명하는 Crammer's Rule 을 정리해 보았다. 중간에 나온 Theorem의 증명은 생략했다.

Crammer's Rule 은 연립일차방정식(systems of linear equations)의 해를 행렬식(determinant)으로 구하는 방법이다. 이를 유도하기 위해 우선 아래와 같이 행렬 A의 행렬식을 j번째 column에 대한 expansion by minors 로 정리해보자.

(식1)... det A = (-1)^j+1a_1jdet A_1j + (-1)^j+2a_2jdet A_2j + ... + (-1)^j+na_njdet A_nj.

여기서 A_ij는 행렬 A에서 i번째 row와 j번째 column을 제거한(crossing out) 행렬이다. 위 식에 α_ij = (-1)^i+j det A_ij 를 넣어서 단순화 시켜보자.

(식2)... det A = a_1j α_1j + a_2j α_2j + ... + a_nj α_nj.

(식2)를 잘 기억해 두고, 다음에는 adjoint 를 정의해 보자. 행렬 A의 adjoint 란 n × n 행렬로 (i,j)의 entry인 (adj)_ij 가 (-1)^i+j det A_ji 인 행렬이다. 즉, α_ji 이며, 아래와 같이 transpose의 형태로도 표현할 수 있다.

(adj A) = (α_ij)^t

adjoint 의 예를 몇개 더 들어보자. 아래는 2 × 2 행렬의 adjoint 이다.

그리고 아래의 3 × 3 행렬의 경우이다.

이번에는 아래 Theorem 과 Corollary 를 살펴보자.

Theorem. δ = det A 라고 하자. 그러면,

(adj A) ⋅ A = δ I, and A ⋅ (adj A) = δ I.

Corollary. 행렬A의 행렬식 δ 가 0이 아니라면,

위의 Corollary 를 사용하여 고등학교때 외웠던 2 × 2 행렬의 행렬식을 유도해낼 수 있다. 즉,

그리고 앞서 나왔던 3 × 3 행렬의 determinant는 1인데, 해당 행렬과 adjoint 행렬을 곱해보면 3 × 3 의 identity matrix가 나온다.

이어서 연립방정식의 해를 행렬로 구하는 경우를 생각해보자. AX = B 의 형태의 식을 떠올릴 수 있고 양변에 행렬 A의 역행렬을 곱해주고 위의 Corollary를 가져온다고 했을 때,

위와 같은 형태가 된다. 그리고 우변의 식은 B가 column vector 이기에 j번째 (row의) 변수 x_j를 아래와 같이 풀어쓸 수 있다.

(식3)의 괄호안 (b₁α_1j + ... + b_nα_nj) 을 살펴보면 (식2) 와 무척 닮았음을 알 수 있다. 즉, (식2) 에서 a_ij 을 b_i 로 바꾸면 똑같게 되는 것이다. 여기서 발견한 내용을 사용해보자.

행렬 A의 j번째 column을 column vector B로 치환한 행렬을 M_j 라고 하자. M_j 의 determinant를 expansion by minors 로 표현하면 아래와 같다.

(식4)... det M_j = (b₁α_1j + ... + b_nα_nj)

이 식이 왜 말이 되는지는 α 의 정의와 아래 그림이 참고가 되면 좋겠다.

(식3)과 (식4)를 조합하면, 아래와 같이 j번째 X를 구할 수 있고, 이게 Crammer's Rule 이 되겠다.

끝으로 이걸 구체적으로 어떻게 응용하는지는 아래 링크에서 참고하면 되겠다.

http://egloos.zum.com/eyestorys/v/3544617

Abstract Algebra 책에 증명 관련 용어들을 정리해 놓은 챕터가 있어서 한글로 정리해 본다.

이론 수학에서는 axiomatic approach 라는 방식을 사용한다. 이는 어떤 오브젝트들을 모아 놓고 이것을 S라고 한다음 이들에 대한 룰(rule)을 가정하는 것이다. 여기서 말하는 룰들을 axioms(공리) 라고 한다. S에 대한 axiom 들과 논리적인 방식들을 가지고 S에서 또다른 정보들을 추출해낼 수 있다. axiom 들은 또한 일관성이 있어야 한다. 즉, axiom 들은 서로를 부정해서는 안된다. 어떤 시스템에서 axiom 들이 지나치게 제한적이라면 이 시스템으로부터 나올 수 있는 수학적인 예문(examples of the methematical structure)이 별로 없을 것이다.

논리학이나 수학에서 statement(명제) 란 참이나 거짓을 판별할 수 있는 문장을 말한다. 아래 예제를 살펴보자.

• 3 + 56 - 13 + 8/2.
• All cats are black.
• 2 + 3 = 5.
• 2x = 6 exactly when x = 4.
• If ax² + bx + c = 0 and a ≠ 0, then
  x =
  -b ± √b² - 4ac / 2a
• x³ - 4x² + 5x - 6.

위에서 첫번째와 마지막을 빼놓고는 모두 참이나 거짓이 되는 statement이다.

수학적인 증명이란 어떤 statement의 참/거짓에 대하여 확인하는 작업(argument)일 뿐이다. 이러한 작업은 독자(audience)가 이해할 수 있도록 부연설명이 충분해야 한다.

"10/5 = 2" 라는 간단한 statement가 있다. 그런데 수학자들은 보다 복잡한 statement에 관심을 갖는다. 예를 들어 "p이면 q이다" 이런 것들이다(p와 q는 statement). 만일 어떤 statement가 참인 것으로 알려졌거나 그렇게 가정할 수 있을 경우, 이와 관련된 다른 statement들은 참인지 거짓인지에 대해서도 알고 싶을 것이다. 여기서 p를 hypothesis(가설) 라고 부르고 q를 conclusion(결론) 이라고 부른다. 다음 statement를 살펴보자: If ax² + bx + c = 0 and a ≠ 0, then

여기서 hypothesis는 ax² + bx + c = 0 and a ≠ 0 이고, conclusion은 아래와 같다.

위의 전체 statement(즉, "p이면 q이다"의 형태의 큰 statement)를 가지고는 hypothesis가 참인지 거짓인지에 대해서 알 수 없다. 하지만 전체 statement가 참이고 hypothesis인 ax² + bx + c = 0 and a ≠ 0 가 참임을 보여줄 수 있다면 conclusion은 무조건 참이다. 이 statement는 아래와 같이 몇 개의 방정식으로 증명할 수 있다:

어떤 statement가 참인것을 증명하면, 그 statement를 proposition(참인 명제) 라고 부른다. proposition 중에서도 아주 중요한 것을 theorem(정리) 라고 한다. 때로는 theorem이나 proposition을 한번에 증명하기보다는 여러 모듈로 나누어서 진행한다. 즉, 여러개의 작은 proposition들을 증명하는 것인데, 이것들을 lemma(보조정리) 라고 한다. lemma들을 이용해서 전체 증명을 하는 것이다. 그리고 또 가끔씩 proposition이나 theorem을 증명하다가 연관된 다른 proposition들을 내놓기도 하는데 이들을 corollary(따름정리) 라고 한다.

용어 한글 번역

• axiom: 공리
• statement: 명제
• hypothesis: 가정
• conclusion: 결론
• proposition: 참인 명제(한글책에서는 그냥 명제라고함)
• theorem: 정리
• lemma: 보조정리
• corollary: 따름정리, 추론

참고

• Abstract Algebra: Theory and Applications(Thomas W. Judson, 2016)
• 수학적 정리를 의미하는 용어: proposition, axiom, theorem, lemma, corollary
• 명제