행렬

정의. 함수 $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$가 대응하며, 그 역도 성립합니다. 수 $n$은 행의 개수와 같고, $m$은 열의 개수와 같습니다. $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;
}

이러한 구현은 가장 간단하기는 하지만 최적은 아닙니다. 매 반복마다 $B$에 대한 포인터를 $m$칸씩 앞으로 이동시키므로 불필요한 캐시 라인 로드가 발생하고, 컴파일러가 자동 벡터화를 적용할 수 없게 됩니다. 하지만 모든 반복문에 앞서 $B$를 전치하면, 즉 $B$의 각 $(i, j)$번째 원소를 $(j, i)$번째 원소와 맞바꾸면 이 문제를 쉽게 해결할 수 있으며, 이렇게 구현하면 5~10배 더 빠르게 동작합니다.

행렬 곱셈을 이보다 훨씬 더, 즉 단순한 구현에 비해 50~100배까지 최적화하는 방법도 있지만, 이는 이 글의 범위를 크게 벗어납니다. 또한 행렬을 $O(n^3)$보다 점근적으로 더 빠르게 곱하는 방법도 알려져 있지만, 실제로는 원소가 수천 개 이상인 행렬에서만 효율적입니다.

#행렬의 성질

행렬을 어떤 숫자들이 적혀 있는 표로 여겨서는 안 됩니다. 모든 행렬에는 벡터를 어떤 방식으로 변환하는 선형 함수가 하나씩 대응합니다. 선형대수학의 중심 대상은 행렬이 아니라 바로 선형 함수입니다.

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

• 행렬 $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$.
• 행렬 곱셈은 일반적으로 교환 법칙이 성립하지 않습니다.

행렬을 실수에 대해서만 다룰 필요는 없습니다. 이 모든 성질은 임의의 체로 옮겨집니다. 체란 연산에 일정한 제약 조건이 붙은 $*$와 $+$가 정의된 집합입니다.

이러한 체 중 가장 널리 쓰이는 부류는 소수 모듈로의 나머지입니다. 특수한 경우로 $p = 2$일 때, 체에는 0과 1 두 원소만 있으며, 덧셈으로는 xor, 곱셈으로는 and를 사용합니다. 이를 통해 행렬을 비트 시퀀스 형태로 효율적으로 저장할 수 있습니다.

#행렬의 예

“모든 것을 두 배로 늘려라” 행렬: