59. Gaussian Elimination

가우스 소거법(Gaussian Elimination)은 연립일차방정식의 해를 구할 때 사용되는 행렬 연산이며, 그밖에도 다양한 방법으로 응용이 가능하다. 가우스 소거법은 행렬에 다음과 같은 세 가지 연산을 수행한다. 첫 번째 연산을 두 번째 연산과 세 번째 연산의 조합으로 대체할 수 있기 때문에 두 가지 연산이라고 해도 상관없지만 편의상 세 가지로 구분했다.

• $i$행과 $j$행을 서로 바꾼다.
• $i$행의 각 성분에 $0$이 아닌 실수 $k$를 곱한다.
• $i$행에 $j$행을 더한다.

가우스 소거법의 목표는 행렬의 랭크와 독립이 아닌 열 사이의 상관관계를 유지하면서 행렬을 행사다리꼴로 만드는 것이다. 이와 관련하여 다음 용어들을 알아 두는 것이 좋다.

• 피벗(Pivot, Leading Entry)은 각 행에서 처음으로 나오는 $0$이 아닌 성분이다.
• 행사다리꼴(Row Echelon Form Matrix)은 모든 피벗이 다른 열에 위치하고, 모든 성분이 $0$인 행이 그렇지 않은 행의 앞쪽에 나오는 경우가 존재하지 않으며, 임의의 두 피벗을 비교했을 때 항상 앞쪽 행의 피벗이 앞쪽 열에 위치하는 행렬이다.
• 기약행사다리꼴(Reduced Row Echelon Form, RREF)은 피벗의 값이 모두 $1$이고, 피벗과 같은 열에 위치하는 성분은 모두 $0$인 행사다리꼴이다.
• 상삼각행렬(Upper Triangular Matrix)은 주대각선 아래의 성분이 모두 $0$인 정사각행렬이다.
• 하삼각행렬(Lower Triangular Matrix)은 주대각선 위의 성분이 모두 $0$인 정사각행렬이다.
• 대각행렬(Diagonal Matrix)은 주대각선 이외의 성분이 모두 $0$인 정사각행렬이다.

$n \times m$ 행렬 $A$를 행사다리꼴로 만드는 과정은 다음과 같다.

    1. $i = j = 1$

    2. $i \le k \le n$이고 피벗이 $j$열에 있는 행 $k$를 하나 찾는다. 그런 행이 없으면 6번으로 넘어간다.

    3. $i$행과 $k$행을 바꾼다.

    4. $i < t \le n$을 만족하는 모든 $t$에 대해 $t$행에 $i$행의 $-\frac{A_{t, j}}{A_{i, j}}$배를 더한다.

    5. $i$에 $1$을 더한다.

    6. $j = m$일 경우 연산을 종료한다. $j < m$일 경우 $j$에 $1$을 더하고 2번으로 돌아간다.

이를 구현하면 다음과 같다. 4번 과정의 구현에서 실수 연산을 최대한 줄이는 것이 좋지만 불가피한 경우 적절하게 사용하도록 한다.

void f1(int n, int m)
{
    int i = 1, j = 1, k;
    for(; i <= n && j <= m; j++)
    {
        for(k = i + 1; k <= n; k++)
        {
            if(a[k][j] != 0)break;
        }
        if(k <= n)
        {
            for(int y = 1; y <= m; y++)swap(a[i][y], a[k][y]);
            for(int x = i + 1; x <= n; x++)
            {
                double w = a[x][j] / a[i][j];
                for(int y = 1; y <= m; y++)a[x][y] -= a[i][y] * w;
            }
            i++;
        }
    }
}

시간복잡도는 $\Theta(nm^2)$이고 단순화하면 $\Theta(n^3)$이 된다.

---

때때로 행사다리꼴로 변환한 행렬을 다시 기약행사다리꼴로 만들어야 하는 경우가 생긴다. 이때는 위의 과정 이후 다음과 같은 과정을 추가로 거친다. 이렇게 행렬을 기약행사다리꼴로 만드는 방법을 가우스-조단 소거법(Gauss-Jordan Elimination)이라고 한다.

    7. $i = j = 1$

    8. $i$행에 $\frac{1}{A_{i, j}}$를 곱한다.

    9. $1 \le t < i$를 만족하는 모든 $t$에 대해 $t$행에 $i$행의 $-A_{t, j}$배를 더한다.

    10. $i = n$일 경우 연산을 종료한다. $i < n$일 경우 $i$에 $1$을 더한다.

    11. $j \le m$이고 $A_{i, j} = 0$일 동안 $j$에 $1$을 더한다. 만약 $j$가 $m$보다 커졌을 경우 연산을 종료한다.

    12. 8번으로 돌아간다.

이를 구현하면 다음과 같다.

void f2(int n, int m)
{
    int i = 1, j = 1, k;
    for(; j <= m; )
    {
        for(k = m; k >= 1; k--)a[i][k] /= a[i][j];
        for(int x = 1; x < i; x++)
        {
            double w = a[x][j];
            for(int y = 1; y <= m; y++)a[x][y] -= a[i][y] * w;
        }
        i++;
        if(i > n)break;
        for(; j <= m && a[i][j] == 0; j++);
    }
}

시간복잡도는 단순화해서 $\Theta(n^3)$이 된다. $6$행에서 $i$행을 피벗으로 나눌 때 뒤쪽 열부터 처리하는데 이것을 단순히 앞쪽 열부터 처리하게 바꾸면 결과가 달라질 수 있으므로 주의해야 한다.

---

가우스-조단 소거법을 이용하면 정사각행렬의 역행렬(Inverse Matrix)을 구할 수 있다. 정사각행렬 $A$의 역행렬 $A^{-1}$은 $A \cdot A^{-1} = I$를 만족하는 행렬이며, $A$의 랭크가 행의 수보다 작을 경우 $A^{-1}$은 존재하지 않는다. 역행렬이 존재하는 행렬을 가역 행렬(Invertible Matrix)이라고 한다.

 

행렬 $A$의 역행렬 $A^{-1}$을 구하는 과정은 다음과 같다.

    1. $A$와 $I$를 가로로 이어붙인다.

    2. 가우스-조단 소거법을 이용하여 $A$ 부분을 $I$로 만든다. 이때 $I$ 부분은 가우스-조단 소거법에 의해 $A^{-1}$이 된다.

 

[연습문제]

 

BOJ 9254. 역행렬 (Gold III)

위에서 설명한 대로 역행렬을 구하면 된다.

 

BOJ 20307. RREF (Platinum IV)

위에서 설명한 대로 RREF를 구하면 된다. 단 유리수를 분수 형태로 출력해야 하므로 적절한 처리가 필요하며, $128$비트 정수 자료형을 사용해야 한다.

 

BOJ 20178. Switches (Platinum III)

Boolean 행렬의 XOR 역행렬을 구하면 된다. 스페셜 저지가 붙어 있지만 답은 유일하게 결정된다.

 

→ solved.ac tag: gaussian_elimination