선형대수 기초 강좌

정의. 함수 $f: \mathbb{R}^n \to \mathbb{R}^m$에 대해 다음이 성립하면 이 함수를 선형이라고 합니다:

1. $f(x+y) = f(x) + f(y)$
2. $f(ax) = a f(x), ; a \in \mathbb{R}$

예를 들어, 다음과 같은 함수들은 선형입니다:

• 벡터를 $k$배 「늘이는」 함수: $f(x) = k x$.
• 평면 위의 벡터를 각도 $\theta$만큼 회전시키는 함수.
• 3차원 벡터를 어떤 평면에 사영하는 함수.
• 내적 $f(x, y) = x \cdot y = \sum x_ky_k$도 두 인자 모두에 대해 선형입니다.

선형대수학은 선형 함수를 연구하는 학문입니다.

정의에 있는 단 두 가지 조건만으로도 유용한 성질을 많이 이끌어 낼 수 있습니다:

• 선형 함수의 합은 선형 함수입니다.
• 선형 함수의 합성 $f(g(x)) = (f \circ g)(x)$는 선형 함수입니다.
• 선형 함수의 합은 교환 법칙을 만족합니다: $f+g = g+f$.
• 선형 함수의 합은 결합법칙을 만족합니다: $(f+g)+h = f+(g+h)$.
• 선형 함수의 합성은 결합 법칙을 만족합니다: $(f \circ g) \circ h = f \circ (g \circ h) = f \circ g \circ h$.
• 합성은 일반적으로 교환 법칙이 성립하지 않습니다. 예: $f(x) = (-x_2, x_1)$은 평면 위의 점을 직각만큼 회전하는 것이고, $g(x) = (x_1, 0)$은 $Ox$로의 사영입니다. 평면 위의 거의 모든 점에 대해 이 두 연산의 순서가 중요합니다.

#행렬

임의의 선형 함수 $f: \mathbb{R}^n \to \mathbb{R}^m$은 다음과 같은 형태로 나타낼 수 있음을 보일 수 있습니다:

$\mathbb{R}^n$에서 $\mathbb{R}^m$으로 가는 모든 선형 함수 $f$에는 크기가 $n \times m$인 어떤 행렬 $A$가 대응하며(첫 번째 수는 행의 개수, 두 번째 수는 열의 개수입니다), 그 역도 성립합니다. $i$번째 행과 $j$번째 열이 교차하는 위치의 원소는 $A_{ij}$로 표기하겠습니다. 혼동하지 마십시오.

벡터가 스칼라의 순서 있는 집합이라면, 행렬은 벡터의 벡터로 볼 수 있습니다. 특히 벡터는 차원 중 하나가 1인 행렬로 나타낼 수 있으며, 이때 이를 열 벡터 또는 행 벡터(벡터-문자열)라고 부릅니다.

typedef vector<vector<int>> matrix;

또한 텐서라는 것도 있습니다. 이는 그보다 더 높은 차수의 모든 객체를 가리키는 말로, 행렬의 벡터(3차원 텐서), 행렬의 행렬(4차원 텐서), 행렬의 행렬의 벡터 등이 이에 해당합니다.

텐서에는 나름의 흥미로운 대수 체계가 있지만, 일반적인 프로그래머가 텐서를 접하는 맥락에서는 대개 어떠한 대수도 염두에 두지 않으며, 이 용어는 단지 “다차원 배열"이라는 말이 너무 길기 때문에 쓰일 뿐입니다.

#행렬 곱셈

선형 함수 $f$에 행렬 $A$가 대응하고, 함수 $g$에 행렬 $B$가 대응한다고 합시다. 그러면 이 함수들의 합성 $h = f \circ g$에는 행렬 $A$와 $B$의 곱 $C$가 대응하며, 이는 다음과 같이 정의됩니다:

독자는 $g$의 식을 $f$에 대입했을 때 어떤 계수가 나오는지 직접 전개해 보면 이를 확인할 수 있습니다.

행렬을 손으로 곱할 때는 다음과 같이 생각하면 편리합니다. $i$번째 열과 $j$번째 행이 교차하는 위치의 원소는 $A$의 $i$번째 행과 $B$의 $j$번째 열의 내적입니다. 이는 곱하는 행렬들의 차원에 제약을 가한다는 점에 주목합시다. 첫 번째 행렬의 크기가 $n \times k$라면 두 번째 행렬의 크기는 $k \times m$이어야 합니다. 즉, “가운데” 차원이 반드시 일치해야 합니다.

이제 $f(x)$에 대한 원래 식은 각각 $n$개의 항으로 이루어진 $m$개의 방정식 대신 $f(x) = Ax$로 간결하게 쓸 수 있습니다.

행렬 곱셈을 구현하는 함수를 작성해 봅시다:

const int n, k, m;

matrix matmul(matrix a, matrix b) {
    matrix c(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            for (int t = 0; t < k; t++)
                c[i][j] += a[i][t] * b[t][j];
    return c;
}

이러한 구현은 가장 간단하기는 하지만, 캐시의 동작 특성 때문에 최적은 아닙니다(「행렬 곱셈 최적화」 절을 참고하십시오).

#행렬의 성질

행렬을 어떤 수들이 적혀 있는 표처럼 여길 필요는 없습니다. 모든 행렬에는 벡터를 어떤 방식으로 변환하는 선형 함수가 하나씩 대응합니다. 선형대수학의 핵심 대상은 행렬이 아니라 바로 선형 함수입니다.

이러한 일대일 대응 덕분에 앞서 언급한 선형 함수의 모든 성질이 행렬에도 그대로 적용됩니다:

• 행렬 $A$와 $B$의 합도 행렬입니다: $C = A+B: ; C_{ij} = A_{ij} + B_{ij}$.
• 행렬의 덧셈은 교환법칙을 만족합니다: $A+B = B+A$.
• 행렬의 덧셈은 결합법칙을 만족합니다: $(A+B)+C = A+(B+C)$.
• 행렬 곱셈은 결합법칙이 성립합니다: $(AB)C = A(BC) = ABC$.
• 행렬 곱셈은 일반적으로 교환 법칙이 성립하지 않습니다.

곱셈에 대해 아무런 작용도 하지 않는, 즉 1처럼 동작하는 특별한 행렬 $I$(때로는 $E$로 표기)가 있으며, 이를 단위 행렬이라고 합니다. 이 행렬은 주대각선 위의 원소가 1이고 그 밖의 원소는 0입니다:

어떤 선형 함수는 가역이고(예를 들어, 각도만큼의 회전), 어떤 선형 함수는 비가역입니다(예를 들어, 사영). 가역성의 개념은 행렬로도 확장할 수 있습니다.

정의. $A \cdot A^{-1} = A^{-1} \cdot A = I$를 만족하는 행렬 $A^{-1}$이 존재하면 행렬 $A$는 가역입니다.

정의로부터 행렬 $A$는 정사각 행렬이어야 함을 알 수 있지만, 이것만으로 항상 충분한 것은 아닙니다. 정사각 행렬이 아닌 행렬에는 역행렬이 존재하지 않습니다. 역행렬은 조금 뒤에 살펴볼 가우스 소거법으로 $O(n^3)$에 구할 수 있습니다.

#행렬의 예

«모든 것을 두 배로 늘려라» 행렬:

#기하학 외의 응용

지금까지의 예시는 모두 기하학에 관한 것이었습니다. 그렇게 하면 생각하기가 더 쉽기 때문입니다. 평면 위 벡터의 회전과 늘이기를 머릿속으로 떠올리는 편이 추상적인 n차원 공간의 성질을 따지는 것보다 쉽습니다.

그러나 우리는 프로그래머이며, 주로 관심을 두는 것은 기하학 밖의 문제입니다.

#동적 계획법

일부 DP에서는 전이를 행렬 곱셈으로 표현할 수 있는 경우가 있습니다.

구체적인 예를 살펴봅시다. 인접 행렬로 주어진 방향 그래프 $G$가 있고, $s$에서 $t$로 정확히 $k$번의 이동을 거치는 경로의 개수를 구해야 한다고 합시다. 그래프의 크기는 $k$에 비해 작습니다(예를 들어 정점은 수백 개 정도이고, $k$는 $10^{18}$ 정도의 수입니다).

일반적으로는 정확히 $i$번의 이동으로 $v$번째 정점에 도달하는 방법의 수를 나타내는 DP $f_{i,v}$를 정의할 것입니다. 갱신은 경로의 마지막에서 두 번째 정점을 모두 시도해 보는 방식으로 이루어집니다:

벡터 $f_{i}$는 $f_{i-1}$에 선형적으로 의존한다는 것을 알 수 있습니다. 그 $v$번째 원소는 $f_{i-1}$과 인접 행렬 $G$의 $v$번째 열을 스칼라곱하여 얻어집니다.

따라서 다음 등식이 성립합니다.

(그래서 $G$를 인접 행렬이라고 부릅니다.)

따라서 $f_k$는 $f_k = f_0 \cdot G \cdot G \cdot \ldots \cdot G$와 같이 전개할 수 있습니다. 행렬 곱셈이 교환 법칙을 만족한다는 점을 떠올리면, 스칼라의 경우와 마찬가지로 $G^k$를 계산하는 데 이진 거듭제곱을 적용할 수 있습니다.

이 공식에 따르면 크기가 $n$인 두 행렬을 $\log k$번 곱해야 하므로, 전체적으로 $O(n^3 \log k)$의 시간이 걸립니다.

const int n;

matrix binpow(matrix a, int p) {
    // создадим единичную матрицу
    matrix b(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++)
        b[i][i] = 1;

    while (p > 0) {
        if (p & 1)
            b = matmul(b, a);
         a = matmul(a, a);
         p >>= 1;
    }

    return b;
}

결과로 얻은 행렬의 칸 $g_{ij}$에는 정확히 $k$번의 이동을 사용하여 $i$번째 정점에서 $j$번째 정점까지 도달하는 방법의 수가 들어 있습니다. 답으로는 $g_{st}$를 그대로 출력하면 됩니다.

문제의 변형:

• 알고리즘 자체를 거의 바꾸지 않고도, 불리언 인접 행렬 대신 마르코프 연쇄에서 한 정점에서 다른 정점으로 이동할 확률이 주어진 경우 “정점 $s$에서 정점 $t$로 도달할 확률은 얼마인가"라는 문제를 풀 수 있습니다.

• 경우의 수가 필요 없고 정확히 $k$번의 전이로 도달할 수 있는지 여부만 알면 된다면, 행렬을 비트셋으로 감싸서 풀이를 크게 가속할 수 있습니다.

• “최대 $k$번의 전이로"라고 묻는다면, 행렬의 $k$제곱 대신 비슷한 방법으로 등비수열의 합을 계산할 수 있습니다.

• 이 기법은 무언가를 하는 방법의 수를 세야 하는 다른 DP에도 적용할 수 있으며, 때로는 전혀 자명하지 않은 방식으로 적용됩니다. 예를 들어, 주어진 짧은 금지 부분 문자열들을 포함하지 않는 길이 $k \approx 10^{18}$의 문자열의 개수를 구하는 문제를 풀 수 있습니다. 이를 위해서는 아호-코라식에서 “허용되는” 전이들로 이루어진 그래프를 만들고, 그 인접 행렬을 $k$제곱한 뒤 첫 번째 행의 원소를 모두 더하면 됩니다.

일부 까다로운 경우에는 행렬 곱셈에서 곱셈과 덧셈 대신, 곱셈과 덧셈처럼 동작하는 다른 연산을 사용해야 합니다. 예제 문제: «정확히 $k$번 이동하여 $s$에서 $t$로 가는, 간선 가중치가 최소인 경로를 찾으십시오»; 이 경우 그래프의 가중치 행렬을 $(k-1)$제곱해야 하며, 두 연산 대신 그래프의 가중치 행렬에 최솟값을 사용해야 합니다.

#선형 점화식

다른 예로 피보나치 수열을 살펴봅시다. 이것도 DP가 아니겠습니까?

보다시피 $n$번째 원소는 앞의 두 원소를 통해 선형적으로 표현됩니다.

일반적으로 피보나치 수열은 여러 가지가 있으며, 반드시 $0$과 $1$로 시작할 필요는 없습니다. 수열 전체를 유일하게 식별하려면 서로 다른 임의의 두 원소의 위치와 값만 알면 충분합니다. 따라서 DP의 상태로 다음과 같은 열벡터를 도입합시다:

(또한 이 행렬의 역행렬을 구하면 반대 방향으로 ‘걸어가는’ 것도 가능합니다.)

이 전이 행렬을 $A$로 나타냅시다. $n$번째 피보나치 수를 계산하려면 이 행렬을 벡터 $(f_0, f_1) = (0, 1)$에 $n$번 적용해야 합니다. 앞의 경우와 마찬가지로 이진 거듭제곱을 사용할 수 있습니다. 행렬 곱셈 연산은 결합법칙이 성립하므로, 전이 행렬을 벡터에 $n$번 적용하는 것은 $n$제곱한 전이 행렬을 그 벡터에 한 번 적용하는 것과 같습니다. 이번에는 행렬의 크기가 상수이므로 이것을 $O(\log n)$에 계산할 수 있습니다.

일반적으로, 선형 점화식 $f_n = a_1 f_{n-1} + a_2 f_{n-2} + \ldots + a_k f_{n-k}$의 전이 행렬은 다음과 같습니다:

#고유벡터

행렬에는 매우 자주 고유 벡터가 존재합니다. 고유 벡터란 그 행렬을 적용해도 방향이 바뀌지 않는 벡터를 말합니다.

$Av = kv$이며, 여기서 $k \neq 0$입니다. 수 $k$를 행렬의 고윳값이라고 합니다.

$Av - kv = (A-kI)v = 0$.

일반적으로 선형대수학에서 고유벡터는 산술에서 소수가 갖는 것과 거의 같은 중요성을 갖습니다.

#선형 독립

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

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

벡터계 ${a_1, a_2, \dots, a_n}$에 대해 적어도 하나의 $j$에 대해 $\lambda_j \neq 0$이면서 $\lambda_1 \cdot a_1 + \lambda_2 \cdot a_2 + \dots + \lambda_n \cdot a_n = 0$을 만족하는 실수 계수의 조합 $(\lambda_1, \lambda_2, \dots, \lambda_n)$이 존재하면, 이 벡터계를 선형 종속이라고 합니다. 그렇지 않은 경우 이 벡터계를 선형 독립이라고 합니다. 예를 들어, $N$차원 공간의 기저는 $N$개의 벡터로 이루어진 선형 독립인 집합입니다. (증명: 기저가 선형 종속이라고 가정합시다. 그러면 길이가 0인 벡터를 적어도 두 가지 방법으로 표현할 수 있습니다)

행렬의 두 열(또는 두 행)은 그것들이 이루는 두 벡터가 선형 종속(공선)이면 선형 종속이라고 합니다. 행렬의 랭크 $rang$ $A$는 행렬에서 $r$개의 서로 쌍마다 선형 독립인 열 또는 행을 고를 수 있는 최대의 수 $r$입니다.

#연립방정식과 가우스 소거법

때때로 연립 일차 방정식을 풀어야 하는 문제가 나옵니다. 그중 매우 많은 부분은 실제로 체 $\mathbb{Z}_2$ 위에서 다루어집니다. 즉, 모든 수를 2로 나눈 나머지로 다룹니다. 예를 들어, 전구 스위치가 $n$개 있고, 켜진 각 스위치는 $n$개의 전구 중 어떤 부분집합의 상태를 바꿉니다(켜거나 끕니다). 모든 전구의 상태를 알고 있을 때, 스위치들의 상태를 복원해야 합니다.

결국 우리에게 요구되는 것은 다음 연립방정식을 푸는 것입니다:

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

크라메르 공식은 최적이 아닙니다. 연산이 $O(n^4)$번 필요하기 때문입니다.

이 경우 일반적인 가우스 소거법을 크게 빠르고 간단하게 만들 수 있습니다:

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;
}

이 코드는 해가 존재하고 유일하다는 조건에서 방정식 $Ax = b$로부터 벡터 $x$를 구합니다. 코드를 간단하게 하기 위해 벡터 $b$가 행렬 $A$의 오른쪽에 덧붙여져 있다고 가정합니다.

이 시스템은 2를 법으로 하여 풀어야 하는 경우가 많습니다. 이때 코드는 상당히 간단해지고 빨라집니다(역시 비트셋을 참고하십시오).

#행렬 곱셈 최적화

글 첫머리에서 소개한 행렬 곱셈의 단순한 구현은 b의 원소에 접근하는 패턴 때문에 최적이 아닙니다. 매번 메모리에서 포인터를 $m$칸씩 앞으로 옮기기 때문에 불필요한 캐시 라인 로드가 발생하고, 컴파일러가 자동 벡터화를 적용할 수 없습니다.

하지만 이를 해결하려면 모든 반복문 전에 b를 전치하기만 하면 됩니다. 즉, 각 $(i, j)$번째 원소를 $(j, i)$번째 원소와 맞바꾸는 것입니다(명확하게 하기 위해 $i < j$라고 합시다). 이렇게 구현하면 약 5배 빠르게 동작하며, 여기서 더 최적화하기는 이미 상당히 어렵습니다.

이후로는 캐시에 통째로 들어가지 않는 큰 행렬을 다룰 때만 어려움이 생깁니다. $C$의 각 행마다 매번 $A$와 $B$의 모든 원소를 처음부터 다시 훑기 때문입니다. 이럴 때는 다음과 같이 할 수 있습니다. 행렬 $A$와 $B$를 예를 들어 4개의 같은 부분으로 나누고 블록 단위로 곱하는 것입니다.

이 공식을 재귀적으로 계산하면 캐시는 그 크기뿐만 아니라 캐시 라인의 크기와도 관계없이 최적으로 사용됩니다(이러한 알고리즘을 cache-oblivious라고 부릅니다).

행렬을 곱하는 더 빠른 방법도 학계에 알려져 있지만, 이들은 상수가 상당히 크기 때문에 원소가 수천 개 이상인 행렬에서만 더 효율적입니다. 실제로는 행렬 중 하나를 전치하고 세 배열 모두에서 두 번째 차원을 따라 반복하는 것으로 충분합니다.