행렬과 유한체

https://en.wikipedia.org/wiki/Matrix_(mathematics)

영문 위키피디아에 따르면 행렬이란 수, 기호, 표현식 등을 직사각형 형태로 배열한 배열이다. 다음과 같은 것 역시 행렬이라는 것을 쉽게 알 수 있다.

$$\left[\begin{array}{cc}{e}^x& -3.5\\ 3& 8\end{array}\right]$$

선형대수학은 행렬, 벡터 등 선형성과 관련된 것을 연구하는 학문으로써, 그 연구결과가 다양한 방식으로 활용되고 있다. 대표적인 예시로는 연립방정식의 해의 존재성, 유일성 등에 관한 증명, 혹은 실질적인 해의 계산 정도가 여러분에게 친숙할 것이다.

다만 프로그래머에게 행렬은 일반적으로 실수 내지는 복소수 상에서 정의되는 행렬만을 다루기에 나머지 연산이 접목된 연립 방정식의 풀이 등에서는 이를 행렬과 연관짓는 사고가 쉽게 가능하지는 않은 듯 하다. 따라서 본 글의 취지는 체란 무엇이며, 실수체가 아닌 체, 특히 갈루아체에서도 가우스-조던 소거를 통한 역행렬 계산이 가능함을 설명하는 것이다.

---

우선 '체(Field)'란 무엇인지에 대해 얘기해보자. 특별한 것은 아니고, 추상대수학에서 연산의 본질에 대해 탐구하기 위해 분류하는 것의 일종이다. 흔히 군, 환, 체라는 용어를 얼핏 들어본 적이 있을텐데, 각각의 정의를 살펴보자.

 

집합 $G$, 연산 $\circ$, 항등원 $e\in G$가 다음 조건을 만족하면 $(G,\circ ,e)$를 군이라 부른다.

• 결합 법칙: $\mathrm{\forall }a,b,c\in G,(a\circ b)\circ c=a\circ (b\circ c)$
• 항등원: $\mathrm{\forall }a\in G,\mathrm{\exists }e\in G:a\circ e=e\circ a=a$
• 역원: $\mathrm{\forall }a\in G,\mathrm{\exists }b\in G:a\circ b=b\circ a=e$

집합 $R$, 연산 $+,\circ$, 덧셈의 항등원 $0$에 대해 $(R,+,0)$이 군이고 아래 조건이 성립하면 $(R,+,\circ ,0)$을 환이라 부른다.

• 덧셈의 교환 법칙: $\mathrm{\forall }a,b\in R,a+b=b+a$
• 곱셈의 결합 법칙: $(a\circ b)\circ c=a\circ (b\circ c)$
• 덧셈에 대한 곱셈의 분배 법칙: $(a+b)\circ c=a\circ c+b\circ c$, $a\circ (b+c)=a\circ b+a\circ c$
  • 곱셈에 대한 교환 법칙이 성립하는지에 대한 조건이 없으므로 각 경우를 따로 정의함
  • 곱셈에 대한 교환 법칙이 성립하는 환을 가환환이라고 함

또한, 곱셈에 대한 항등원 1이 존재하며 0이 아닌 원소가 곱셈에 대한 역원을 가지면 해당 환을 나눗셈환이라고 한다.

마지막으로, 체는 가환환이며 나눗셈환인 $(F,+,\circ ,0,1)$을 체라고 부른다.

실수 집합인 $\mathbb{R}$가 위의 조건을 모두 만족한다는 것은 쉽게 확인 가능하다.

체를 간단하게 말하자면, 사칙연산이 실수에서와 비슷하게 잘 정의되는 집합과 연산을 체라고 부르는 것이다.

 

유한체, 또는 갈루아 체는 유한한 개수의 원소를 갖는 체이다. 대표적으로 $p$로 나눈 나머지의 집합이 있으며, 이는 $\mathbb{Z}/p\mathbb{Z}$로도 표기한다. 유한체에 대한 자세한 내용은 위키백과 - 유한체에서 확인 가능하나, 본 글에서는 간단하게 $p$로 나눈 나머지의 집합에 대해서만 이야기할 예정이다.

 

중요한 점은 $\mathbb{Z}/p\mathbb{Z}$가 과연 체냐는 것이다. 다른 것들은 일반적인 사칙 연산과 비슷하나, 나눗셈의 경우는 잘 정의된다는 것이 다소 비직관적이다. 예를 들어, 정수 집합 $\mathbb{Z}$는 $1\in \mathbb{Z}$, $2\in \mathbb{Z}$에 대해 $1/2$가 정의되지 않지 않은가.

 

$\mathbb{Z}/p\mathbb{Z}$에서 곱셈의 역원, 즉 나눗셈은 잉여역수를 이용하여 정의된다. $a$의 잉여역수는 다음을 만족하는 정수 $b$이다.

$$ab\equiv ba\equiv 1(\text{mod }p)$$

위 식은 $ab=kp+1$인 정수 $k$가 존재함과 동치이다. 즉 $ab-pk=1$을 만족하는 정수 $b,k$의 존재성을 증명하면 $\mathbb{Z}/p\mathbb{Z}$가 체임을 알 수 있으며, 이는 디오판토스 방정식 $ax+by=gcd(a,b)$가 정수해를 갖는다는 사실로부터 쉽게 알 수 있다.($\because \mathrm{\forall }x:1\le x<p,gcd(x,p)=1$)

따라서 $\mathbb{Z}/p\mathbb{Z}$는 체이다.

---

가우스-조던 소거는 다음의 행 기본 연산을 이용하여 진행된다.

• $i$행을 0이 아닌 상수 $c$에 대해 $c$배 하여 $j$행에 더한다. $E(i,j;c)$
• $i,j$행을 교환한다. $E(i,j)$
• $i$행을 0이 아닌 상수 $c$에 대해 $c$배한다. $E(i;c)$

위 세 연산이 잘 정의된다면 가우스-조던 소거가 잘 정의된다고 볼 수 있으며, 위 연산들은 모두 체인 $\mathbb{Z}/p\mathbb{Z}$에서 잘 정의된다. 따라서 실수체에서와 마찬가지로 augmented matrix $[A|I]$를 가우스-조던 소거하면 $[I|A^{-1}]$를 얻을 수 있다.

 

이는, 실수에서와 마찬가지로 행렬을 이용해 $\mathbb{Z}/p\mathbb{Z}$에서 정의되는 연립방정식을 풀 수 있음을 의미한다.

 

일반적으로, 모듈로 연산의 법이 소수가 아닌 경우도 많이 마주할 수 있다. 이러한 경우 법을 소인수분해하여 $\prod {p_i}^{e_i}$ 꼴로 표현한 후 각 ${p_i}^{e_i}$에 대해 연립방정식을 푼 결과를 Chinese Remainder Theorem을 이용하여 통합해줌으로써 해결할 수 있다.