Joonas' Note

Joonas' Note

행렬식(determinant) 알아보기 + 구현 본문

AI/수학

행렬식(determinant) 알아보기 + 구현

2023. 2. 1. 22:18 joonas

    책을 읽다가 행렬식(determinant)에 대한 노트를 읽었는데, 기하학적으로 설명된 부분에 궁금한 점이 생겨서 정리해보고자 한다.

    2X2 행렬

    책에서는 2X2 행렬에 대해서 \(det(A)~=~a_{11}a_{22} - a_{12}a_{21}\) 을 이렇게 설명하고 있었다.

    행렬 \(A~=~\begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix}\) 의 행렬식은 두 개의 열 벡터 \(\begin{pmatrix} a_{11} \\ a_{21} \end{pmatrix}\) 와  \(\begin{pmatrix} a_{12} \\ a_{22} \end{pmatrix}\) 를 두 변으로 하는 평행사변형의 면적이다.

    그럼 행렬 \(\begin{pmatrix} 3 & 2 \\ 1 & 4 \end{pmatrix}\) 를 2차원 좌표평면에 아래처럼 그릴 수 있고, 행렬식은 이 사각형에 대한 넓이를 계산한다는 의미라는 것이다.

    [[3, 2], [1, 4]] 를 2차원 평면 위에 표시

    궁금한 점은 2가지인데, 하나는 \(det(A)~=~a_{11}a_{22} - a_{12}a_{21}\) 로 구한 값 (1)평행사변형의 넓이 (2), 그리고 벡터의 내적으로 구해지는 넓이 (3)가 모두 같은 값인가? 가 첫 번째 의문점이었다.

    감사하게도 먼저 깔끔하고 자세하게 정리를 해주신 분의 글이 있었다.
    두 번째 궁금증 역시 아래의 포스트를 참고해서 해결할 수 있었다.

     

    [Linear Algebra] Lecture 20-(2) 행렬식(Determinant)의 기하학적 해석(Geometrical Analysis)

    이번 강의는 행렬식(Determinant)에 관한 마지막 강의다. 이번에 알아볼 내용은 determinant가 기하학적(geometrical)으로 어떤 의미를 갖는지에 대해서 알아볼 것이다. 미리 결론부터 언급하자면 행렬식(d

    twlab.tistory.com

    위 포스트에 따르면 결과적으로 (1), (2), (3)은 모두 같은 값으로 계산된다. 즉, 2X2 행렬의 행렬식은 그 넓이를 계산하는 것이 맞다는 것이다.

     

    3x3 행렬

    두 번째 궁금증은, 그럼 3X3 행렬은 3차원 점들에 대해서 부피를 구한다는 의미인가? 이다.

    먼저 이것을 기하학적으로 이해하기 위해서, 2X2 행렬 \(\begin{pmatrix} 3 & 2 \\ 1 & 4 \end{pmatrix}\) 에 한 층 쌓아서 \(\begin{pmatrix} 3 & 2 & 0 \\ 1 & 4 & 0 \\ 2 & 1 & 2 \end{pmatrix}\) 를 만들어보자. 기존의 2개의 점은 z=0 인 평면에 둔다.

    위에서처럼 이것들을 행 벡터로 생각하면 세 점 (3, 2, 0), (1, 4, 0), (2, 1, 2) 으로 그려볼 수 있을 것이라 생각했다.
    (3X3의 정방행렬이고, 행렬식의 결과값은 하나의 상수이므로 뒤집어도 계산 과정에는 문제가 없다.)

    3차원으로 옮기고 점을 하나 추가해본다.

    그럼 기존에 2X2 행렬은 노란색 부분처럼 표시된다는 것이고, 새로 추가된 점 (2, 1, 2) 에 대해서도 평행하게 모서리를 전부 그려보면 하나의 직육면체가 나온다.

    3x3 행렬이 나타내는 기하학적인 형태

    이제 det(A)는 위와 같은 직육면체에 대한 부피를 구하게 된다는 것이다.
    (각 평면이 깜빡거리는 이유는 matplotlib 에서 z-order 관련한 버그(?)이다. 해결하려면 다른 라이브러리인 Mayavi 를 쓰면 된다고 하지만 지금은 굳이...)

    3X3 행렬에 대해서도 첫 번째 의문이었던 (1), (2), (3) 모두 위 포스트에서 정리가 되어있다. 새로 추가한 점에 대한 벡터가, 노란색 평면에 수직이 아니라서, 계산 과정이 복잡해지지만 결국은 부피가 잘 구해진다.


    NXN 행렬

    그럼 4X4, 5X5 행렬에 대해서도 가능하다는 것인데, 크기별로 행렬식에 대한 공식이 정확히 어떻게 되는 것이고 어떻게 구할 수 있는가?

    NumPy 함수

    먼저, 다행스럽게도 NumPy에서 함수를 제공한다.

    from numpy.linalg import det
    
    det([[3,2,0],[1,4,0],[2,1,2]])
    # 20.0

    레퍼런스는 아래를 참고하면 된다.

     

    numpy.linalg.det — NumPy v1.24 Manual

    Another way to represent the determinant, more suitable for large matrices where underflow/overflow may occur.

    numpy.org

    직접 구현해보기

    행렬 \(A~=~\begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix}\) 의 행렬식은 2X2 행렬식으로부터 아래와 같이 정의할 수 있다.

    여기서 재귀적으로 4X4 이상의 행렬도 정의할 수 있는데, 아래처럼 색칠해보면 규칙을 확인하기 쉽다.

    이것을 파이썬 함수로 직접 작성해보면 아래와 같다.

    def submatrix(a: list, col_i: int) -> list:
        m = []
        n = len(a)
        for i in range(1, n):
            row = []
            for j in range(n):
                if col_i == j: continue
                row.append(a[i][j])
            m.append(row)
        return m
    
    
    def det(a: List[list]) -> float:
        n = len(a)
        # 정방행렬만 가능
        for row in a:
            assert len(row) == n
    
        # 2X2 는 직접 가능
        if n == 2:
            return a[0][0]*a[1][1] - a[0][1]*a[1][0]
    
        result = 0
        for i in range(n):
            sign = (-1) ** i
            coeff = a[0][i]
            # 재귀적으로 계산
            result += sign * coeff * det(submatrix(a, i))
        return result

    위처럼 직접 계산할 수 있긴한데, 이 방법은 곱셈이 많아서 소수점 아래로 오차가 많아져서 overflow를 피하기 어렵다.

    다른 방법으로는 라이프니츠 공식으로 N X N 크기 행렬의 행렬식을 구할 수 있다.
    어떻게 전개되는 지는 아래 유튜브에 잘 설명되어 있다.

    Leibniz formula for computing determinants  | Lecture 30 | Matrix Algebra for Engineers

    numpy 를 설치하지 못하는 등의 상황이라면, 라이프니츠 공식의 pyhton 구현체도 많이 찾아볼 수 있다.

     

    Finding determinant of a nxn matrix using Leibniz formula on python

    I have tried to code the permutations in python. I am looking for suggestions on how to code the determinant using the Leibniz formula in python 3.7

    stackoverflow.com

    # https://github.com/python/cpython/blob/main/Modules/itertoolsmodule.c
    def permutations(iterable, r=None):
        pool = tuple(iterable)
        n = len(pool)
        r = n if r is None else r
        if r > n: return
        indices = list(range(n))
        cycles = list(range(n, n-r, -1))
        parity = 0
        yield tuple(pool[i] for i in indices[:r]), parity
        while n:
            for i in reversed(range(r)):
                cycles[i] -= 1
                if cycles[i] == 0:
                    if ((n-i) & 1) == 0: parity = 1 - parity
                    indices[i:] = indices[i+1:] + indices[i:i+1]
                    cycles[i] = n - i
                else:
                    j = cycles[i]
                    parity, indices[i], indices[-j] = 1 - parity, indices[-j], indices[i]
                    yield tuple(pool[i] for i in indices[:r]), parity
                    break
            else: return
    
    # 행렬식 계산
    def determinant(mat):
        n = len(mat)
        def dosign(parity, x): return -x if parity else x
        det = 0
        for sigma, parity in permutations(range(n)):
            mul = 1
            for i in range(n):
                mul *= mat[i][sigma[i]]
            det += dosign(parity, mul)
        return det

    numpy 패키지와 비교하면 오차가 미세하게 있지만, 재귀식으로 구현한 함수보다는 훨씬 낫다.

     

    'AI > 수학' 카테고리의 다른 글

    Links for Machine Learning  (0) 2017.10.29
    Comments