6.15 행렬 곱셈과 결합 법칙

1. 행렬 곱셈의 정의 재검토

행렬 곱셈은 선형 변환의 합성을 수치적으로 표현하는 연산이며, 그 정의는 함수 합성의 자연스러운 일반화로 이해할 수 있다. 본 절에서는 행렬 곱셈을 여러 각도에서 해석하고, 결합 법칙의 의미와 그 응용을 깊이 있게 다룬다.

정의 6.15.1. $m \times p$ 행렬 $A$ 와 $p \times n$ 행렬 $B$ 의 곱 $C = AB$ 는 $m \times n$ 행렬이며, 그 성분은

$c_{ij} = \sum_{k=1}^{p} a_{ik} b_{kj}$

로 정의된다.

행렬 곱셈의 네 가지 해석

해석 1: 성분별 내적

행렬 곱 $AB$ 의 $(i, j)$ 성분은 $A$ 의 $i$ 행과 $B$ 의 $j$ 열의 내적이다.

$(AB)_{ij} = \mathbf{a}_i^{\text{row}} \cdot \mathbf{b}_j$

1.1 해석 2: 열 결합

행렬 곱 $AB$ 의 $j$ 열은 $A$ 의 열들의 선형 결합이며, 결합 계수는 $B$ 의 $j$ 열이다.

$(AB)_{:, j} = A \mathbf{b}_j = \sum_{k=1}^{p} b_{kj} \mathbf{a}_k$

이 해석에 의하면 행렬 곱은 $A$ 의 열공간에서의 선형 결합 연산이다.

해석 3: 행 결합

행렬 곱 $AB$ 의 $i$ 행은 $B$ 의 행들의 선형 결합이며, 결합 계수는 $A$ 의 $i$ 행이다.

$(AB)_{i, :} = \mathbf{a}_i^{\text{row}} B = \sum_{k=1}^{p} a_{ik} \mathbf{b}_k^{\text{row}}$

1.2 해석 4: 외적 합

행렬 곱은 $p$ 개의 외적(rank-1 행렬)의 합으로 분해된다.

$AB = \sum_{k=1}^{p} \mathbf{a}_k \mathbf{b}_k^{\text{row}}$

여기서 $\mathbf{a}_k$ 는 $A$ 의 $k$ 열이고 $\mathbf{b}_k^{\text{row}}$ 는 $B$ 의 $k$ 행이다. 각 항 $\mathbf{a}_k \mathbf{b}_k^{\text{row}}$ 는 랭크 1 행렬이다. 이 해석은 SVD의 저랭크 근사 이론에 활용된다.

결합 법칙의 형식적 진술

정리 6.15.1 (결합 법칙). 행렬 $A \in \mathbb{R}^{m \times p}$ , $B \in \mathbb{R}^{p \times q}$ , $C \in \mathbb{R}^{q \times n}$ 에 대하여 다음이 성립한다.

$(AB)C = A(BC)$

증명. 좌변의 $(i, j)$ 성분은

$((AB)C)_{ij} = \sum_{l=1}^{q} (AB)_{il} c_{lj} = \sum_{l=1}^{q} \left( \sum_{k=1}^{p} a_{ik} b_{kl} \right) c_{lj} = \sum_{l=1}^{q} \sum_{k=1}^{p} a_{ik} b_{kl} c_{lj}$

우변의 $(i, j)$ 성분은

$(A(BC))_{ij} = \sum_{k=1}^{p} a_{ik} (BC)_{kj} = \sum_{k=1}^{p} a_{ik} \left( \sum_{l=1}^{q} b_{kl} c_{lj} \right) = \sum_{k=1}^{p} \sum_{l=1}^{q} a_{ik} b_{kl} c_{lj}$

이중 합의 순서를 교환할 수 있으므로 두 표현은 같다. $\square$

2. 결합 법칙의 함수 합성 해석

행렬 $A$ 와 $B$ 를 각각 선형 변환 $T_A: \mathbb{R}^p \to \mathbb{R}^m$ 과 $T_B: \mathbb{R}^q \to \mathbb{R}^p$ 로 해석하면, 행렬 곱 $AB$ 는 합성 함수 $T_A \circ T_B$ 에 대응한다. 함수 합성은 본질적으로 결합적이므로, 이를 표현하는 행렬 곱셈도 결합 법칙을 만족하는 것은 자연스럽다.

$T_A \circ (T_B \circ T_C) = (T_A \circ T_B) \circ T_C$

결합 법칙의 계산적 의의

결합 법칙은 여러 행렬의 곱셈에서 괄호의 위치를 자유롭게 선택할 수 있게 한다. 비록 결과 행렬은 동일하지만, 계산 순서에 따라 연산량이 크게 달라질 수 있다.

행렬 연쇄 곱셈 문제

$k$ 개의 행렬 $A_1 A_2 \cdots A_k$ 를 곱하는 경우, 곱셈 순서에 따른 총 연산량의 차이는 매우 크다. 예를 들어 $A_1 \in \mathbb{R}^{10 \times 100}$ , $A_2 \in \mathbb{R}^{100 \times 5}$ , $A_3 \in \mathbb{R}^{5 \times 50}$ 의 곱 $A_1 A_2 A_3$ 를 고려하자.

순서 1: (A_1 A_2) A_3
- $A_1 A_2$ : $10 \times 100 \times 5 = 5{,}000$ 번의 곱셈
- $(A_1 A_2) A_3$ : $10 \times 5 \times 50 = 2{,}500$ 번의 곱셈
- 합계: $7{,}500$ 번
순서 2: A_1 (A_2 A_3)
- $A_2 A_3$ : $100 \times 5 \times 50 = 25{,}000$ 번의 곱셈
- $A_1 (A_2 A_3)$ : $10 \times 100 \times 50 = 50{,}000$ 번의 곱셈
- 합계: $75{,}000$ 번

순서 1이 순서 2보다 약 10배 빠르다. 최적의 곱셈 순서를 결정하는 문제는 동적 계획법으로 해결되며, 행렬 연쇄 곱셈 문제(matrix chain multiplication problem)로 알려져 있다.

결합 법칙과 결합되지 않는 연산

결합 법칙은 모든 이항 연산이 만족하는 성질이 아니다. 다음의 예가 결합 법칙이 일반적으로 성립하지 않음을 보여 준다.

벡터의 외적: $(\mathbf{a} \times \mathbf{b}) \times \mathbf{c} \neq \mathbf{a} \times (\mathbf{b} \times \mathbf{c})$
뺄셈: $(a - b) - c \neq a - (b - c)$

행렬 곱셈이 결합 법칙을 만족하는 것은 행렬을 도구로 하는 거의 모든 수학적 조작을 가능하게 하는 핵심 성질이다.

결합 법칙과 비교환성의 공존

행렬 곱셈은 결합 법칙을 만족하지만 교환 법칙은 만족하지 않는다. 이 두 성질의 공존은 행렬 곱셈의 본질을 이해하는 데 중요하다.

결합 법칙: 곱셈의 그룹화를 자유롭게 변경할 수 있다.
비교환성: 곱셈의 순서는 절대 변경할 수 없다.

따라서 $ABC$ 를 계산할 때 $(AB)C$ 또는 $A(BC)$ 로 그룹화할 수 있지만, $BAC$ 또는 $CBA$ 로 순서를 바꾸는 것은 일반적으로 결과를 변경한다.

거듭제곱과 결합 법칙

결합 법칙으로 인해 정방 행렬의 거듭제곱이 모호성 없이 정의된다.

$A^k = \underbrace{A \cdot A \cdots A}_{k \text{개}}$

거듭제곱은 다음의 지수 법칙을 만족한다.

$A^m \cdot A^n = A^{m+n}, \quad (A^m)^n = A^{mn}$

그러나 일반적으로 $(AB)^n \neq A^n B^n$ 이다. 이 등식은 $AB = BA$ 인 경우, 즉 $A$ 와 $B$ 가 가환할 때에만 성립한다.

분배 법칙과의 결합

결합 법칙과 분배 법칙을 결합하면 다음의 유용한 항등식을 얻는다.

$(A + B)C = AC + BC$
$A(B + C) = AB + AC$
$(A + B)(C + D) = AC + AD + BC + BD$

마지막 식에서 항의 순서가 보존됨에 주의하여야 한다. $(A + B)(C + D) \neq AC + BC + AD + BD$ 인 경우가 일반적이며, 이는 $AD + BC \neq BC + AD$ 가 아니라 (덧셈은 교환 가능), 사실상 두 표현은 같다. 따라서 다음과 같이 정리해도 무방하다.

$(A + B)(C + D) = AC + AD + BC + BD$

다만 합 안의 각 곱의 순서는 변경할 수 없다.

로봇공학에서의 응용

다관절 로봇의 순기구학

$n$ 자유도 매니퓰레이터의 말단 장치 위치는 각 관절 사이의 동차 변환 행렬을 차례로 곱하여 계산된다.

${}^0 T_n(\mathbf{q}) = {}^0 T_1(q_1) \cdot {}^1 T_2(q_2) \cdots {}^{n-1} T_n(q_n)$

결합 법칙으로 인해 이 곱셈은 어떤 순서로 그룹화해도 결과가 같다. 예를 들어, 6관절 로봇의 경우 다음과 같은 그룹화가 모두 가능하다.

$T_{\text{end}} = ((T_1 T_2)(T_3 T_4))(T_5 T_6) = T_1 (T_2 (T_3 (T_4 (T_5 T_6))))$

실시간 응용에서는 부분 결과를 효율적으로 재사용하는 것이 중요하며, 일반적으로 베이스에서 말단 방향으로 차례로 곱셈을 수행한다.

자코비안의 효율적 계산

자코비안의 재귀적 계산에서 부분 결과의 재사용을 위해 결합 법칙이 활용된다. 각 관절의 자코비안 기여를 계산할 때, 이전 관절까지의 누적 회전 행렬을 재사용함으로써 전체 계산량을 줄일 수 있다.

동역학의 재귀적 계산

뉴턴-오일러 재귀 동역학(Newton-Euler recursive dynamics)에서는 베이스에서 말단으로 진행하는 정방향 재귀와 말단에서 베이스로 진행하는 역방향 재귀가 사용된다. 각 단계에서 부분 곱이 누적되며, 결합 법칙으로 인해 이 누적 곱셈이 단일한 결과를 만들어 낸다.

칼만 필터의 공분산 갱신

확장 칼만 필터의 공분산 갱신 식

$P^{+} = (I - KH) P^{-} (I - KH)^\top + K R K^\top$

은 여러 행렬의 곱을 포함한다. 결합 법칙에 의해 부분 곱을 미리 계산하여 재사용함으로써 계산 효율을 높일 수 있다. 특히 $I - KH$ 를 한 번 계산해 두면 양쪽에 활용할 수 있다.

2.1 좌표 변환의 합성

서로 다른 좌표계 간의 변환을 합성할 때 결합 법칙이 사용된다.

${}^A T_D = {}^A T_B \cdot {}^B T_C \cdot {}^C T_D$

이 식의 그룹화는 결합 법칙으로 자유롭게 선택할 수 있으며, 자주 사용되는 부분 곱을 미리 계산하여 캐싱하는 전략이 효과적이다.

참고문헌

Strang, G. (2023). Introduction to Linear Algebra (6th ed.). Wellesley-Cambridge Press.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.). MIT Press.
Golub, G. H., & Van Loan, C. F. (2013). Matrix Computations (4th ed.). Johns Hopkins University Press.
Featherstone, R. (2008). Rigid Body Dynamics Algorithms. Springer.

Version: 1.0