행렬식(Determinant) - 라이프니츠 공식

행렬식의 정의와 라이프니츠 공식

---

 

  행렬식은 정방행렬에서만 정의할 수 있으며, 행렬이 역행렬을 취할 수 있는지(가역성) 여부를 파악해주는 역할을 한다.

일반적으로 n차 정방행렬 A의 행렬식은 $det(A)$ 또는 $|A|$와 같이 정의한다.

 

 

$A$가 2차 정방행렬이고

$A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$

 

와 같이 정의되었을 때,

$det(A) = ad - bc$임은 잘 알려져 있지만, 3차 이상의 행렬에서 행렬식을 구하는 것은 2차 행렬만큼 간단하지는 않다.

 

 

  행렬식의 일반적인 정의(치환을 사용한 정의)는 다음과 같다.

 

$det(A) = |A| = \displaystyle \sum_{\sigma \in S_{n}}^{} sgn(\sigma)\prod_{i=1}^{n}a_{i\sigma(i)}$

 

  이를 라이프니츠 공식(Leibniz formula)라고 한다. 실제로는 라플라스 전개를 사용하여 행렬식을 더 쉽게 구할 수 있는는데, 라플라스 전개에 대한 내용은 다음 포스트에서 작성할 것이다.

행렬식의 정의는 $\sum, sgn(\sigma), \prod$의 연산이 수행되는 부분을 나누어 설명할 수 있다.

 

 

 

 

 

1. $\displaystyle \sum_{\sigma \in S_{n}}^{}$

    $S_{n}$은 ${1,...,n}$의 치환(Permutation), 즉 1부터 $n$까지 모든 자연수를 (중복을 허용하지 않고) 배열한 결과들의 집합이다., $_{n}P_{n}$ = $n!$가지의 배열 결과가 반환되고, 이것들을 각가 $\sigma$에 대입한 결과를 모두 더한 것이 행렬식의 결과가 됨을 의미한다.

2. $sgn(\sigma)$
  $sgn$ 함수는 부호함수인데, 여기서는 개별 치환 $\sigma$의 호환 횟수(순서대로 배열된 처음 상태에서 두 개의 원소의 자리가 서로 뒤바뀐 횟수 )를 검증한다.  홀치환이면 -1 / 짝치환이면 1을 부여하여 앞의 $\sum$ 연산에서의 가감을 결정하는 과정이다(치환에 관한 개념 또한 설명이 길어지기 때문에 짧게만 작성함).

  각 치환의 호환 횟수를 식별하기 위해서, 초기 상태의 $\sigma$는 작은 원소부터 순차적으로 정렬되어 있음을 이용한다. 원소의 중복으로 허용하지 않은 상태이므로, 특정 원소$k_{1}, k_{2}$ 간의의 호환이 1회 발생($k_{1} < k_{2}$)하면, $k_{2}$는 $k_{1}$ 앞으로 이동하게 되고, 초기 상태와는 달리 자신보다 작은 원소(=$k_{1}$) 1개가 자신의 뒤에 위치하게 된다. 이런 식으로, 두 원소의 호환이 발생할 때마다 더 큰 원소의 뒤에 놓이는 자신보다 작은 원소의 수가 1씩 증가하게 되고, 이것의 합이 호환의 총합이 된다. 이 과정은 파이썬 코드로 구현하여 첨부하였다.

 

3. $\prod_{i=1}^{n}a_{i\sigma(i)}$
  ${1,...,n}$의 원소들을 순차적으로 행 번호, 1에서 구한 치환 $\sigma$의 개별 원소들을 열 번호로 하여 행렬 $A$의 각 원소를 꺼내고, 이를 모두 곱하는($\prod$) 연산이다. 이때, $\sigma$는 원소가 중복되지 않았기 때문에 곱 연산에 같은 열의 원소가 두 개 이상 사용되는 경우는 없다. 마찬가지로 1~n행을 순차적으로 선택하므로 같은 행 원소도 선택하지 않는다. 이것은 여인수 전개(=라플라스 전개 : 추후 포스팅)의 원리가 된다.

  2x2 행렬의 행렬식이 $det(A) = ad-bc$인 것도 집합 ${1,2}$에서 순서대로 원소를 꺼내어 행을 선택하고, 집합 ${1,2}$로 만들 수 있는 치환$({1,2},{2,1})$에서 열을 선택하여 $a_{11}\cdot a_{22} - a_{12}\cdot a_{21}$라는 행렬식을 구성한 결과인 것이다.

 

 

 

라이프니츠 공식의 파이썬 구현

---

*전체 코드는 Github 참조

 

라이프니츠 공식을 구현하기 위해서는 1. 치환 함수를 정의하여 집합 $N = {1,2,...,n}$의 치환을 구하고, 2. 치환 $\sigma \in S_{n}$을 각각 대입하여 행렬식을 구성하는 과정이 필요하다. 치환 함수의 경우 itertools 라이브러리의 permutations(from itertools import permutation) 메서드를 사용하여 쉽게 구할 수도 있으므로, 2의 과정에 대해서만 설명할 것이다.

 

라이프니츠 공식에 의한 행렬식의 계산 과정을 구현한 코드는 다음과 같다.

def determinant(matrix):
    #행렬식 추출하기
    dim = len(matrix)
 
    det = 0 
 
    for sigma_i in permutation(list(range(dim)),dim): #순열 가짓수만큼 시행
 
        sgn_sigma, fact, cnt = 1, 1,0 #sgn_sigma : 홀치환/짝치환 결과, fact : 각 원소들의 계승, cnt :각 순열의 치환 횟수을 집계
        for ai in range(dim): #1열부터 sigma 함수 적용
            cnt += sum([sigma_i[ai] > sigma_i[num] for num in range(ai, dim)]) #각 원소의 치환 횟수를 집계
            fact *= matrix[ai][sigma_i[ai]] #원소끼리 곱셈(계승)
 
        sgn_sigma *= (-1)**cnt #홀치환이면 음수, 짝치환이면 양수 부여
 
 
        det += fact *sgn_sigma #행렬식 계산
        
    return det

 

  사전에 정의한 puermutation 함수를 사용하여 각각의 치환에 해당하는 sigma_i를 하나씩 사용하여 열을 선택하고, (행은 순차적으로 선택한 뒤) 원소를 꺼내어 곱해준다. 이때, for 문이 중첩되어 있지만, 앞의 for 문은 치환(=원소의 집합)을 하나씩 꺼내는 역할만 하고, 두 번째 반복문에서 $\prod_{i=1}^{n}a_{i\sigma(i)}$의 연산이 이루어지게 된다. 원소들의 계승은 fact에 곱하여 저장되고, cnt 객체에는 for문으로 (위에서 설명한 짝치환/홀치환의 구분을 위해) 개별 원소의 뒤에 위치한 자신보다 작은 원소의 갯수를 구하여 모두 더한다. 

  마지막으로 구해진 각각의 부분곱을 det에 연속하여 더하면 행렬식의 결과가 반환된다.

 

 

위 함수를 통해 구한 3차 정방행렬 $B$의 행렬식은 다음과 같다(행렬식 출력을 위해 코드를 일부 추가).

 

$B = \begin{pmatrix} 9 & 7 & 5 \\ 3 & 9 & 6 \\ 7 & 8 & 8 \end{pmatrix}$

 

 

넘파이의 np.linalg.det(matrix) 메서드를 사용하면 행렬식을 간단하게 구할 수 있다. 계산 결과 직접 구현한 함수와 동일한 결과를 반환한다.

 

 

 

 

참고자료

1. 프로그래머를 위한 선형대수(히라오카 카즈유키 저, 이창신 옮김) - 길벗(2017)

2. [Youtube] 쑤튜브 : 10분 선형대수 강의 모음(youtu.be/x-Ewz1ukXEA)

3. 네이버 블로그(m.blog.naver.com/lcuh11/220755451414)

4. Medium : 치환 함수 구현(medium.com/@dltkddud4403/python-%EC%88%9C%EC%97%B4-%EC%A1%B0%ED%95%A9-%EA%B5%AC%ED%98%84-5e496e74621c)