행렬 곱셈과 전치

요약

두 행렬의 곱은 “먼저 오른쪽 행렬로 바꾸고, 이어서 왼쪽 행렬로 바꾸는” 두 변환을 하나로 합친 행렬이다. 그래서 여러 단계의 좌표 변환이나 신경망의 층들을 행렬 하나로 미리 합칠 수 있다. 합성이라 순서가 중요해서, 곱하는 순서를 바꾸면 보통 결과가 달라진다. 곱하는 순서를 괄호로 어떻게 묶느냐에 따라 계산량이 수백 배 달라지기도 한다. 행과 열을 맞바꾼 전치는 곱의 순서를 뒤집는다.

예시로 보기

평면에서 \(R\)은 90° 회전, \(S\)는 가로로 두 배 늘이기다.

\[R = \begin{pmatrix}0 & -1\\ 1 & 0\end{pmatrix}, \quad S = \begin{pmatrix}2 & 0\\ 0 & 1\end{pmatrix}\]

점 \((1, 0)\)에 “회전 뒤 늘이기”를 하면 \(R(1, 0) = (0, 1)\), 이어서 \(S(0, 1) = (0, 1)\)이다. “늘이기 뒤 회전”은 \(S(1, 0) = (2, 0)\), 이어서 \(R(2, 0) = (0, 2)\)이다. 결과가 다르다. 두 과정을 하나로 합친 행렬은 각각

\[SR = \begin{pmatrix}0 & -2\\ 1 & 0\end{pmatrix}, \qquad RS = \begin{pmatrix}0 & -1\\ 2 & 0\end{pmatrix}\]

이다. \(SR\)이 “먼저 \(R\), 다음 \(S\)“다. 오른쪽 행렬이 벡터에 먼저 작용한다. \(R\)과 \(S\)가 아래 정의의 \(B\)와 \(A\)다.

같은 글자 F에 두 순서로 했더니 모양이 다르다. \(SR\)에서는 누운 F가 가로로 두 배 늘어나고, \(RS\)에서는 넓어진 F가 눕는다. 점 \((1, 0)\)도 각각 \((0, 1)\)과 \((0, 2)\)로 간다¹.

정의

\(A \in \mathbb{R}^{m \times n}\)(\(\in\)은 “~에 속한다”), \(B \in \mathbb{R}^{n \times p}\)일 때 \(AB \in \mathbb{R}^{m \times p}\)는 모든 \(\mathbf{x}\)에서 \((AB)\mathbf{x} = A(B\mathbf{x})\)가 되도록 정한 행렬이다. 성분으로는

\[(AB)_{ij} = \sum_{k=1}^{n} a_{ik}b_{kj} = (A\text{의 } i\text{행}) \cdot (B\text{의 } j\text{열}).\]

\(A\)의 열 수와 \(B\)의 행 수가 같아야 한다².

         A (m x n)                 B (n x p)          AB (m x p)
   [ .  .  .  .  .  . ]          [ .  .  #  . ]       [ .  .  .  . ]
i  [ #  #  #  #  #  # ]          [ .  .  #  . ]    i  [ .  .  *  . ]
   [ .  .  .  .  .  . ]    x     [ .  .  #  . ]  =    [ .  .  .  . ]
                                 [ .  .  #  . ]
                                 [ .  .  #  . ]
                                 [ .  .  #  . ]
                                         j                    j

A의 i행(#)과 B의 j열(#)은 둘 다 n칸이라 한 칸씩 짝지어 곱해 더할 수 있다. 그 합이 AB의 (i, j) 칸(*)이고, 결과의 크기는 바깥쪽 두 수 m × p다³.

\(AB\)의 \(j\)번째 열은 \(A\)에 \(B\)의 \(j\)번째 열을 곱한 것이다. \((AB)\mathbf{e}_j = A(B\mathbf{e}_j)\)이기 때문이다. 이것이 성분 공식의 근거다.

성질. 결합법칙 \((AB)C = A(BC)\), 분배법칙 \(A(B + C) = AB + AC\), 단위행렬 \(AI = IA = A\)가 맞는다. 교환법칙은 맞지 않는다. 결합법칙은 변환의 합성이 결합적이라는 사실(함수의 합성)에서 나온다.

전치

\(A^\top\)는 \(A\)의 행과 열을 맞바꾼 행렬이다: \((A^\top)_{ij} = a_{ji}\). \(A^\top = A\)인 정사각 행렬을 대칭행렬이라 한다.

내적은 \(\mathbf{u}\cdot\mathbf{v} = \mathbf{u}^\top\mathbf{v}\)(\(1 \times n\) 곱하기 \(n \times 1\))이고, \((AB)^\top = B^\top A^\top\)이다. 어떤 \(A\)든 \(A^\top A\)는 대칭이다(\((A^\top A)^\top = A^\top(A^\top)^\top = A^\top A\)).

\((AB)^\top = B^\top A^\top\)의 증명

\(\big((AB)^\top\big)_{ij} = (AB)_{ji} = \sum_k a_{jk}b_{ki} = \sum_k (B^\top)_{ik}(A^\top)_{kj} = (B^\top A^\top)_{ij}\). 곱의 순서가 뒤집혀야 인덱스가 맞는다. ∎

예제

괄호 위치가 비용을 바꾼다. \(n \times n\) 행렬 \(A\), \(B\)와 벡터 \(\mathbf{x}\)로 \(AB\mathbf{x}\)를 계산한다.

\((AB)\mathbf{x}\): 행렬 곱에 곱셈 \(n^3\)번, 이어서 행렬-벡터 곱 \(n^2\)번.
\(A(B\mathbf{x})\): 행렬-벡터 곱 두 번, \(2n^2\)번.
차이: \(n = 1000\)이면 약 \(10^9\)번 대 \(2 \times 10^6\)번으로 500배 차이다. 결과는 결합법칙으로 같다.

검증: 예시의 \(SR\), \(RS\)와 점의 이동, 정의 \((AB)\mathbf{x} = A(B\mathbf{x})\)(무작위 1,000개, 유리수), \(AB\)의 열 = \(A \times\) (\(B\)의 열), 결합·분배법칙, 교환법칙의 반례 비율, \((AB)^\top = B^\top A^\top\), \(A^\top A\)의 대칭성, 곱셈 횟수, 카드의 값 — 06_matrix-multiplication_verify.py

활용

변환 파이프라인. 그래픽스는 모델 → 월드 → 카메라 → 화면 변환을 행렬 곱 하나로 합쳐 두고, 수백만 개의 꼭짓점에 한 번씩만 곱한다.
신경망. 활성 함수 없이 층을 쌓으면 \(W_2(W_1\mathbf{x}) = (W_2W_1)\mathbf{x}\)라 한 층과 같다. 층 사이의 비선형 함수가 꼭 필요한 이유다(뉴런의 연산 모형).
비용과 알고리즘. 곱셈을 그대로 하면 \(n^3\)번이다. 분할 정복으로 \(7T(n/2) + O(n^2)\)를 만든 슈트라센 방법은 \(O(n^{2.81})\)이다(마스터 정리). 여러 행렬을 곱할 때 괄호 순서를 고르는 것은 동적 계획법의 대표 문제다.
흔한 실수. 코드에서 A * B(NumPy의 성분별 곱)와 A @ B(행렬 곱)를 혼동하는 것.
알고리즘에서: 위의 괄호 순서 고르기는 마지막 곱셈의 자리를 모두 따지는 구간 DP로 풀고, 행렬이 \(k\)개면 \(O(k^3)\)이다. 더하기를 min으로, 곱하기를 +로 바꾼 곱은 가운데 점 하나를 거치는 가장 싼 길을 주고, 플로이드–워셜은 이 곱을 되풀이하는 대신 같은 연산으로 거쳐도 되는 점을 하나씩 늘려 정점 \(n\)개의 모든 쌍 최단 거리를 \(O(n^3)\)에 구한다. 파이썬 2차원 리스트의 전치는 [list(row) for row in zip(*a)]이고, 위아래를 먼저 뒤집고 전치하면 격자가 시계 방향으로 90도 돈다(구현과 시뮬레이션). 그 밖에 자물쇠와 열쇠에서도 쓴다.

연결

선수: 행렬과 행렬-벡터 곱
같은 구조: 함수의 합성(교환되지 않는 합성)
이어지는 개념: 역행렬, LU 분해

과목별 관점

자료구조 (1-2학기). 0이 아닌 칸만 (행, 열, 값) 묶음으로 적은 목록에서 전치를 만든다. 정의 \((A^\top)_{ij} = a_{ji}\)대로 묶음마다 행 번호와 열 번호를 맞바꾸면 값은 맞다. 하지만 목록은 “윗줄부터, 줄 안에서는 왼쪽부터” 서 있어야 하는데 그 순서가 깨진다. 그래서 이 목록의 전치는 번호를 바꾸는 일에 줄을 다시 세우는 일이 더해진 것이다. 빠른 전치(fast transpose)는 정렬하지 않고 세 단계로 한다. 원래 행렬의 열마다 0이 아닌 칸을 세고, 그 수를 앞에서부터 더해 새 행마다 목록의 몇 번 칸에서 시작하는지 정하고, 원래 목록을 앞에서부터 읽어 제자리에 꽂는다. \(m \times n\) 행렬에 0이 아닌 칸이 \(t\)개면 \(O(n + t)\) 시간이다. 2차원 배열에서 칸마다 옮기면 \(mn\)칸을 모두 건드린다. 두 번 전치하면 원래 목록으로 돌아오는 것(\((A^\top)^\top = A\))도 이 방법으로 확인된다⁴. 자세한 것은 희소 행렬의 전치에 있다.

확인 문제

C1 \(A = \begin{pmatrix}1 & 2\\ 3 & 4\end{pmatrix}\), \(B = \begin{pmatrix}0 & 1\\ 1 & 0\end{pmatrix}\)일 때 \(AB\)와 \(BA\)를 구하라.

답: \(AB = \begin{pmatrix}2 & 1\\ 4 & 3\end{pmatrix}\)(열을 바꿈), \(BA = \begin{pmatrix}3 & 4\\ 1 & 2\end{pmatrix}\)(행을 바꿈). 서로 다르다.

C2 두 정사각 행렬에서 \(AB = BA\)가 맞지 않는 예를 들고, 변환으로 해석하라.

답: 90° 회전 \(R\)과 가로 두 배 늘이기 \(S\). \((1, 0)\)은 \(SR\)로 \((0, 1)\), \(RS\)로 \((0, 2)\)에 간다. 늘인 뒤 돌리는 것과 돌린 뒤 늘이는 것은 다르다.

C3 \((AB)^\top = B^\top A^\top\)에서 순서가 뒤집히는 이유를 성분으로 설명하라.

답: \((AB)^\top\)의 \((i, j)\) 성분은 \((AB)_{ji} = \sum_k a_{jk}b_{ki}\)이다. 이것을 \(\sum_k (B^\top)_{ik}(A^\top)_{kj}\)로 읽으면 \(B^\top\)의 \(i\)행과 \(A^\top\)의 \(j\)열의 내적, 곧 \(B^\top A^\top\)의 성분이다. 크기로 봐도 \(A^\top B^\top\)는 보통 곱이 정의되지 않는다.

06_matrix-multiplication_plot.py로 그렸고, \(SR\), \(RS\)와 점 \((1, 0)\)의 도착점을 같은 코드로 확인했다. ↩
Strang, Introduction to Linear Algebra 5판, 2.4절 “Rules for Matrix Operations”(곱의 네 가지 보는 법, 결합법칙, 교환 불가), 2.7절 “Transposes and Permutations”(\((AB)^\top = B^\top A^\top\), 대칭행렬, \(A^\top A\)). ↩
이 문서 정의의 성분 공식 \((AB)_{ij} = (A\text{의 } i\text{행}) \cdot (B\text{의 } j\text{열})\)과 크기 조건을 ASCII로 그렸다(Strang 5판 2.4절). ↩
12_sparse-matrix-transpose_impl.c에서 무작위 행렬 1,000개로 확인했다. ↩