[3-8] Inverting Matrices Mod n

• 분수를 처리하기 위해 Section 3.3에서 주어진 규칙을 적용하는 한 행렬 (mod n)의 역행렬은 행렬을 반전시키는 일반적인 방법으로 찾을 수 있다. 기본적인 사실은 정방 행렬의 경우 행렬식과 n이 서로소인 경우에만 mod n에 대해 가역적이다.

+가역적이라는 것은?

-역 함수, 역 행렬, 역원이 유일하게 존재하여 입출력 또는 곱셈 순서를 뒤바꿔도 원하는 유일한 것을 얻게됨을 말한다.

-가역 행렬: 행렬 A이 invertible이라면, 그 역행렬 A^-1이 유일하게 존재한다. (가역 행렬 = 역 행렬이 존재하는 정방 행렬)

 

• 정수 행렬의 역행렬은 원래 행렬의 결정 인자로(determinant)로 나눈 또 다른 정수 행렬로 쓸 수 있다.
• 행렬식과 n이 서로소라고 가정하기 때문에 섹션 3.3에서와 같이 행렬식을 도치시킬 수 있다. (invert를 도치로 해석)

2x2 행렬의 공식은

이다. 그래서 우리는 mod n에 대해서 계산하기 위해 ad-bc의 mod n에 대한 역원을 구해야 할 필요가 있다.

 

 

행렬식과 n이 서로소가 되어야하는 이유는 MN = I (mod n)이라고 가정하기 때문이다. (I는 단위 행렬임)

det(M)이 역행렬 mod n을 가지고, 이는 det(M)과 n이 서로소여야 함을 의미한다.