행렬식(Determinant) - 여인수 전개와 가우스 소거법을 이용한 방법

여인수 전개(Cofactor Expansion)

---

 

 

  이전 포스팅에서 다룬 라이프니츠 공식은 행렬식의 정의를 바탕으로 계산하는 방법이지만, 행렬의 크기가 커질수록  연산시간이 크게 증가한다는 단점이 있다. 

 

  여인수 전개는 행렬식의 정의의 패턴을 이용하여 계산 과정을 보다 단순하게 정리한 방법 중 하나이다. 여인수란 특정 원소가 속한 행/열을 제외한 부분행렬의 행렬식을 구하고, 제외된 행/열의 번호에 따라 부호(행 번호 + 열 번호가 홀수이면 음수/짝수이면 양수)를 부여한 것이다. 행렬 $A$의 원소 $a_{i}$에 대응하는 여인수는 $C_{ij} = (-1)^{i+j} \times M_{ij}$로 정의되며, 이때 $M_{ij}$는 행렬 A에서 $i$행과 $j$열을 제외한 $(n-1)$차 정방행렬의 행렬식을 의미한다.  

 

 

  여인수 전개는 보편적으로 1행 또는 1열의 원소들과, 그에 대응하는 여인수의 곱들의 합으로 표현되며, 1행/1열의 원소를 이용할 경우를 각각 1행 전개와 1열 전개라고 한다. 계산의 방향만 다를 뿐, 전체적인 전개 방식이나 결과값은 동일하다.

 

1행 전개를 사용한 여인수 전개는 다음과 같이 표현할 수 있다.

$det(A) = \displaystyle \sum_{j=1}^{n}a_{1j}\cdot C_{1j}$

 

$A = \begin{vmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{vmatrix}$ 일 경우,  $det(A) = a_{11}\cdot C_{11} + a_{12}\cdot C_{12} + a_{13}\cdot C_{13} = a_{11}\cdot M_{11} - a_{12}\cdot M_{12} + a_{13}\cdot M_{13}$이다.

행렬 $A$와 같은 3차 정방행렬의 경우 2차 행렬에 대한 행렬식을 바로 계산할 수 있지만, 4차 이상의 행렬을 처리할 경우 소행렬식의 결과는 재귀 형태로 계산할 수 있다. 아래의 파이썬 코드도 det_cofactor() 함수를 재귀 함수의 형태로 구현한 것이다.

 

 

 

여인수 전개에 의한 행렬식의 계산 과정을 구현한 코드는 다음과 같다(Github).

def det_cofactor(matrix): #1행전개로 구현
    
    det = 0 #결과를 담을 객체
    dim = len(matrix)
    
    if dim == 2: #2차 행렬일 때는 ad-bc 수행
        
        det = matrix[0][0]*matrix[1][1] - matrix[1][0]*matrix[0][1] 
        return det
    
    else : 
        
        for col in range(dim):
            #원소 a 추출
            a = matrix[0][col]
 
            #소행렬식 M 추출
            partial = np.delete(matrix,0,axis=0) #1행전개
            partial = np.delete(partial,col,axis=1)
            
            M = det_cofactor(partial) #재귀함수
 
            sgn = (-1)**(col)
            # 부호(실제 파이썬 인덱스는 0부터 시작하므로, 1행과 k열의 숫자 합은 col 변수와 동일한 홀/짝의 성질을 가짐)
            det += a*sgn*M
 
    return det

 

  재귀함수이기 때문에 이전에 정의한 라이프니츠 공식에 비해 코드가 단순하다. 이 함수는 if문에 의해 재귀 과정에서의 분기가 구현되어 있는데, 차원이 2차원 이하($ad-bc$의 형태로 행렬식을 쉽계 계산할 수 있는 경우)일 때는 행렬식을 바로 계산하여 반환하고, 그렇지 않을 경우 여인수 전개를 통해 원소 $a_{ij}$와 여인수 $C_{ij}$를 곱하여 모두 더하는, 여인수 전개의 과정을 수행한다(이때 $C$는 소행렬식 $M$과 부호함수의 곱이다). $n$차 행렬이 입력되면, 재귀 호출을 수행하고, 최종적으로 2차 소행렬식을 반환할 때 까지 내려간 후, 이를 더하여 다시 3차부터 $n$차의 최종 행렬식을 반환한다.

 

 

가우스 소거법과 행렬식의 성질을 이용한 방법

---

  여인수 전개 또한 재귀 형태로 반복되므로, (라이프니츠 공식만큼은 아니지만) 행렬의 크기가 커질수록 연산이 복잡해지는 단점을 여전히 가진다. 앞선 두 방법에 비해 획기적으로 연산 시간을 절감할 수 있는 방법이 있는데, 바로 가우스 소거법을 사용하여 행렬을 행사다리꼴 형태로 변환(정방행렬이므로 상삼각행렬)하는 방법이다. 정확하게는 가우스 소거법에서의 기본행 연산에 따른 행렬식의 변화를 이용한 방법이라고 할 수 있다. 

 

 

  이 방법을 위해서는 우선 기본행 연산을 수행함에 따라 행렬식이 변화하는 성질을 파악해야 한다. 이러한 성질들이 어떻게 유도되었는지는 쑤튜브의 관련 강의(강력추천!)을 참조하고, 결론만 정리하면 다음과 같다.

 

1. 행의 상수배 : $r_{i} \in A$인 어떤 행 $r_{i}$에 k만큼 상수배하여 행렬 $A'$를 만들 경우 $det(A') = kA$이다

2. 행 교환 : 행의 위치와 관계없이 서로 다른 행 $r_{i}$와 $r_{j}$의 위치가 교환되면 det(A)의 부호가 바뀐다.

3. 행의 (상수배 후) 덧셈 : 행렬식에는 변화가 없다.

 

 

  그리고, 가우스 소거법에 의해 선행원소가 1이 된 행사다리꼴을 $B$라고 하면, $det(B) = 1$이다(대각원소끼리의 곱이 아닌 경우 반드시 대각원소 아래의 0이 곱셈에 포함되기 때문). 결국 가우스 소거법으로 행렬 A를 행사다리꼴로 변환하고, 적용된 기본행 연산에 따른 변화를 모두 곱하여 역수를 취한 것이 행렬 $A$의 행렬식이 되는 것이다. 예를 들어 1행에 $\frac{1}{3}$만큼 상수배가 적용되고, 2행과 3행이 1회 교환된 행렬 $A'$는

 

$det(A) \times \frac{1}{3} \times (-1) = det(A') = 1 \Leftrightarrow det(A) = -3$

 

인 것이다.

 

 

 

가우스 소거법을 바탕으로 행렬식의 계산 과정을 구현한 코드는 다음과 같다.

def det_gauss(matrix_input):
    matrix=matrix_input.copy() #기존 배열을 보존하기 위해
    dim = len(matrix)
    det = 1 #행사다리꼴의 행렬식은 1
 
    row_count = 0
    for col_count in range(dim): #선행 원소 아래의 값(열 하단)이 0이 될때까지 반복 수행
        comp_num = np.inf # 비교할 숫자의 기본값을 무한대로 지정(보다 작은 수)
        
        
        # 첫 열이 1이거나, 0이 아닌 수 중 가장 작은 행을 추출
        for i in range(row_count,dim):
            if (0 < abs(matrix[i][col_count])) & (abs(matrix[i][col_count]) < abs(comp_num)) : 
                comp_num = matrix[i][col_count] #절댓값이 가장 작은 첫 행의 값
 
                first_row = i #첫 행으로 사용할 행
                if matrix[i][0] == 1: #1을 찾은 경우 
                    break
                    
            
 
        
        matrix[first_row]=matrix[first_row]/comp_num  #첫 행의 첫 열을 1로 변환
        #print(round(comp_num,3), "만큼 상수배 적용")
        det *= comp_num #상수배 만큼 적용
        
        if first_row != row_count:
            det *= -1
            #print(first_row+1,"행이", row_count+1,"행과 교환")
            matrix[first_row], matrix[row_count] = matrix[row_count].copy(), matrix[first_row].copy() #대상 인덱스와 첫 행을 교환
        
        #first_row가 첫 행을 가리키지 않으면 첫 행과 다른 행이 1회 행교환되었으므로 부호가 음수가 됨
 
            
        #상수배 후 덧셈연산(행렬식에 영향을 주지 않음)
        for j in range(row_count+1,dim):
            if matrix[j][col_count] != 0:
                con_no = matrix[j][col_count]
                matrix[j] = matrix[j] - con_no * matrix[row_count]
                
        row_count += 1
 
        
    return det

  전체적인 알고리즘은 가우스-조르당 소거법의 행사다리꼴 변환 과정과 유사하며, 행렬식에 영향을 주는 행의 상수배 연산과 행교환 연산을 체크하여 이를 det 객체에 반영하는 과정만 추가되었다. 임의로 정의한 4차 정방행렬의 행렬식을 det_gauss() 함수로 구한 결과는 다음과 같다.

 

각 1, -9, 18.889(이하 반올림), 11.324만큼 상수배가 적용되었으므로 이들을 모두 곱하고, 행교환이 3회 발생했으므로 (-)부호를 적용한 것이 위 행렬의 행렬식이 된다(부동소숫점 처리 문제로 인한 출력 문제) 발생.

 

 

 

행렬식을 구하는 방법들 간의 비교

---

  가우스 소거법을 이용한 행렬식 연산은 이전의 다른 연산과 동일한 결과값을 제공하면서, 훨씬 짧은 시간 안에 연산을 처리할 수 있다는 장점이 있다. 실제 연산 시간을 확인하기 위해, 이전에 정의한 determinant(라이프니츠 공식), det_cofactor(여인수 전개), det_gauss(가우스 소거법) 함수와 함께, Numpy에서 제공하는 np.linalg.det 메서드의 결괏값과  실제 수행 시간을 비교하였다. 유의미한 연산 시간의 차이를 측정하기 위해, 임의의 $10 \times 10$ 행렬을 입력하였다.

 

 

 

각 함수의 결괏값(정수 반올림 : 실제 모든 원소가 정수인 행렬의 행렬식은 항상 정수이다)

 

  사실, 가우스 소거법과 np.linalg.det 메서드는 정확한 정수가 아닌 부동소숫점 근사치를 반환한다. 아마 선행원소를 1로 만드는 과정에서 생기는 무한소수의 처리 문제와 관련이 있는 듯 하며, 행렬의 원소에 따라 적절히 반올림해주면 큰 문제가 되지는 않는다. 결과적으로는 모두 동일한 값을 반환한다.

 

 

 

각 함수의 수행 시간(time 라이브러리를 사용하여 시작 시간과 종료 시간의 차이 측정)

 

  수행 시간을 측정하여 소수 셋째자리까지 반올림하였으며, 앞서 설명하였던 것과 같이 라이프니츠 공식에 비해 여인수 전개가 조금 더 빠른 시간 안에 처리되며, 가우스 소거법이 다른 두 함수에 비해 월등히 빠른 것을 볼 수 있다. 전문적으로 구현된 넘파이 메서드의 경우 가우스 소거법보다도 유의미하게 빠른 시간 안에 수행(0.0006s vs 0.0001s)되었으며, 아마 가우스 소거법과 유사한 알고리즘으로 구현되었을 것으로 추측된다.

 

 

 

 

 

참고자료

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

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