선형 방정식

일부 선형 함수는 역함수가 존재합니다. 예를 들어, 어떤 각도만큼의 회전이 그렇습니다. 반면 역함수가 존재하지 않는 함수도 있습니다. 예를 들어, 사영이 그렇습니다. 가역성의 개념은 행렬로도 확장할 수 있습니다.

정의. 행렬 $A$가 가역이라는 것은 다음을 만족하는 행렬 $A^{-1}$이 존재한다는 것입니다.

행렬 곱셈의 성질에 따라, 역행렬이 존재하려면 행렬 $A$는 정사각 행렬이어야 하지만, 이것만으로 항상 충분하지는 않습니다.

#연립 선형 방정식

행렬의 가역성 개념은 선형 방정식을 푸는 데 중요합니다:

그렇지 않으면 해가 없거나 무한히 많으며, 일반적으로 이 해들은 어떤 다차원 공간 위에 놓이게 됩니다. 이는 다음과 같이 생각하면 편리합니다. 각 조건(방정식 한 줄)은 $n$차원 공간에서 어떤 초평면을 정의하며, 이 초평면들의 교집합은 비어 있거나, 서로 일치하거나, 더 낮은 차원의 어떤 부분공간을 이룹니다.

연립일차방정식의 풀이는 수치 선형대수의 기본 문제 중 하나이며, 다른 알고리즘의 하위 문제로 자주 등장합니다.

#가우스 소거법

가우스 소거법(영어: Gaussian elimination)을 사용하면 연립일차방정식을 풀 수 있을 뿐만 아니라 역행렬을 구하고 관련 문제들을 해결할 수도 있습니다.

이 방법은 연립방정식에 대해 다음과 같은 연산을 자유롭게 할 수 있다는 사실에 기반합니다:

• 두 방정식의 위치를 서로 바꾸는 것,
• 임의의 방정식에 0이 아닌 상수를 곱합니다,
• 한 방정식에서 다른 방정식을 뺍니다.

이때 위의 모든 연산은 가역적이며 어떤 정보도 잃지 않습니다. 모든 행은 항상 서로의 자명하지 않은 선형 결합이 되고, 원래의 모든 방정식은 항상 어느 한 방정식에 어떤 계수와 함께 반영되기 때문입니다.

알고리즘의 목표는 이 세 가지 연산을 사용하여 연립방정식을 다음과 같은 형태로 만드는 것입니다.

그러면 해는 단순히 $x = b’$가 됩니다.

#알고리즘

해가 존재하며 유일하다고 가정하고 진행하겠습니다.

행렬 $A$의 오른쪽에 벡터 $b$를 덧붙이고, 그 결과로 얻은 $n \times (n+1)$ 행렬을 반복적으로 원하는 형태로 변환해 나가겠습니다. $i$번째 단계에서는 셀 $a_{ii}$에 1이 오고, $i$번째 열의 나머지 모든 셀에는 0이 오도록 만들고자 합니다.

$i$번째 단계를 수행하려면 다음과 같이 합니다:

1. $i$번째 열에서 0이 아닌 원소를 아무거나 하나 찾고, 그 원소가 있는 행을 $i$번째 행과 서로 바꿉니다;
2. $i$번째 행 전체를 원소 $a_{ii}$로 나눕니다(이 원소는 0이 아닙니다. 바로 이전 단계에서 일부러 찾았기 때문입니다).
3. 나머지 모든 행 $j \ne i$를 차례로 돌면서 $i$번째 행에 계수 $a_{ji}$를 곱한 것을 뺍니다.

그 결과 $i$번째 단계가 끝나면 원소 $a_{ii}$는 1이 되고(그 원소를 자기 자신으로 나누었기 때문입니다), $i$번째 열의 나머지 모든 칸은 0이 됩니다(그 위치들에서 $a_{ij} \cdot a_{ii} = a_{ij}$를 뺐기 때문입니다).

따라서 $n$번의 단계를 거치면 행렬을 원하는 형태로 만들 수 있으며, 덧붙인 마지막 $(n+1)$번째 열이 답이 됩니다.

#구현

계산 안정성을 고려하면 각 단계에서 0이 아닌 아무 원소나 피벗으로 택하는 것이 아니라 가장 큰 원소를 택하는 것이 합리적입니다. 결국 그 원소로 나누게 되는데, 부동소수점 수의 경우 0에 매우 가까운 수가 나올 수 있기 때문입니다.

typedef vector< vector<double> > matrix;

vector<double> gauss(matrix a) {
    int n = (int) a.size();
    for (int i = 0; i < n; i++) {
        // находим опорный элемент
        int best = i;
        for (int j = i + 1; j < n; j++)
            if (abs(a[j][i]) > abs(a[best][i]))
                best = j;
        // меняем строчки местами
        swap(a[best], a[i]);
        // нормализуем i-тую строчку (слева нули, с ними ничего делать не надо)
        for (int j = n; j >= i; j--)
            a[i][j] /= a[i][i];
        // зануляем все остальные ячейки в i-том столбце
        for (int j = 0; j < n; j++)
            if (j != i)
                // слева только нули, так что можно пройтись только по правой части
                for (int k = n; k >= i; k--)
                    a[j][k] -= a[i][k] * a[j][i];
    }
    vector<double> ans(n);
    for (int i = 0; i < n; i++)
        ans[i] = a[i][n];
    return ans;
}

이 알고리즘은 $O(n^3)$ 시간에 동작합니다.

또한 이 알고리즘은 실수뿐만 아니라 다른 체(field)로도 일반화할 수 있습니다. 예를 들어 소수 모듈로의 나머지에도 적용할 수 있으며, 이때는 나눗셈에 해당하는 적절한 절차를 사용하기만 하면 됩니다.

#불 행렬

올림피아드 맥락에서 연립 일차방정식을 풀어야 하는 문제 대부분은 실제로는 이를 체 $\mathbb{Z}_2$ 위에서, 즉 2를 법으로 하여 풀어야 합니다.

문제. $n$개의 전구와 $n$개의 스위치가 있습니다. 활성화된 각 스위치는 전구들의 어떤 부분집합의 상태를 바꿉니다(켜거나 끕니다). 모든 전구의 상태가 알려져 있을 때, 스위치들의 상태를 복원해야 합니다.

결국 다음 연립방정식을 풀라는 것입니다:

여기서 $x$는 스위치의 상태, $b$는 전구의 상태, $A$는 스위치가 전구에 영향을 주는지에 대한 정보입니다.

이 경우 비트셋을 사용하여 일반적인 가우스 소거법을 크게 가속하고 단순화할 수 있습니다:

typedef bitset<maxn> t;
typedef array<t, maxn> matrix;

t gauss(matrix a) {
    for (int i = 0; i < n; i++) {
        int nonzero = i;
        for (int j = i + 1; j < n; j++)
            if (a[j][i])
                nonzero = j;
        swap(a[nonzero], a[i]);
        for (int j = 0; j < n; j++)
            if (j != i && a[j][i])
                a[j] ^= a[i];
    }
    t x;
    for (int i = 0; i < n; i++)
        x[i] = a[i][n] ^ a[i][i];
    return x;
}

이번 구현과 이전 구현 모두에서 해가 존재하며 유일하다고 가정했다는 점에 주의하십시오. 그렇지 않다면 어느 시점에서 피벗으로 쓸 0이 아닌 원소를 찾지 못하게 됩니다.

이 경우 완전히 0인 열은 무시하고 알고리즘을 계속 실행할 수 있으며, 그러면 마지막에 어떤 $b_i’$와 같은 0인 합이 몇 개 남게 됩니다. 이 $b_i’$가 모두 0이면 해가 존재하고, 그렇지 않으면 해가 존재하지 않습니다.

“실제 세계"에서 온 입력 데이터의 경우 계수에 작은 노이즈 $\epsilon_{ij}$를 더할 수 있습니다. 이렇게 하면 해가, 그것도 유일한 해가 항상 존재함을 보장할 수 있습니다.

#기저

정의. 벡터 집합의 기저란 선형 결합을 통해 그 집합의 모든 벡터를, 그리고 오직 그 벡터들만을 유일한 방법으로 표현할 수 있는 벡터들의 모음을 말합니다.

기저는 선형대수학에만 있는 것이 아닙니다. 예를 들어, ${1, x, x^2}$는 모든 이차 다항식의 기저입니다. 또는 ${\neg, \land, \lor}$는 모든 논리식의 기저입니다(즉, 모든 것을 AND, OR, NOT으로 표현할 수 있습니다). 임의의 프로그래밍 언어에서도 무엇이든 작성할 수 있게 해 주는 어떤 명령어 집합을 골라낼 수 있으며, 이 집합 역시 이러한 의미에서 기저라고 할 수 있습니다.

정의. 벡터계 ${a_1, a_2, \dots, a_n}$에 대하여, 적어도 하나의 $i$에 대해 $\lambda_i \neq 0$이고 다음 식을 만족하는 실수 계수의 조합 $(\lambda_1, \lambda_2, \dots, \lambda_n)$이 존재하면, 이 벡터계를 선형 종속이라고 합니다.

그렇지 않은 경우 이 시스템을 선형 독립이라고 합니다.

명제. $n$차원 공간의 기저는 $n$개의 벡터로 이루어진 선형 독립인 집합입니다.

증명. 기저가 선형 종속이라고 합시다. 그러면 길이가 0인 벡터를 적어도 두 가지 방법으로 표현할 수 있는데, 이는 정의에 모순됩니다.

올림피아드 문제에서는 기저를 찾거나 유지해야 하는 경우가 많으며, 흔히 “각 벡터에 어떤 비용이 있을 때 최대 가중치 기저를 구성하라"와 같은 형태입니다. 벡터 집합이 기저인지 확인하려면 이 벡터들로 영벡터를 자명하지 않은 방식으로 표현할 수 있는지 확인하면 되며, 이는 가우스 소거법으로 할 수 있습니다.

연습 문제. $0$부터 $(2^{30}-1)$까지의 정수 $10^5$개로 이루어진 배열이 주어집니다. 이 배열의 서로 다른 부분 수열 중 xor-합이 주어진 수 $x$와 같은 것의 개수를 구하십시오.