[MIT 18.065] 1.2. Matrix-Matrix Multiplication AB

---

💡 이 글은 MIT의 선형대수학 강의 MIT 18.065 Spring 2018 및 Gilbert Strang 교수님의 책 『Linear Algebra and Learning from Data』을 따라 정리했습니다. 강의 내용과 일부 연습문제 풀이를 포함합니다.

1. $uv^T$ = Rank One Matrix

일반적으로 행렬 간 곱셈 $AB$를 계산할 때는 $A$의 row와 $B$의 column을 내적(inner product)하여 계산한다.

\[AB = \begin{bmatrix} - & a_1^* & - \\ - & a_2^* & - \\ & \vdots & \\ - & a_m^* & - \end{bmatrix} \begin{bmatrix} | & | & & | \\ b_1 & b_2 & \cdots & b_n \\ | & | & & | \end{bmatrix} = \begin{bmatrix} a_1^*b_1 & a_1^*b_2 & \cdots & a_1^*b_n \\ a_2^*b_1 & a_2^*b_2 & \cdots & a_2^*b_n \\ \vdots & \vdots & \ddots & \vdots \\ a_m^*b_1 & a_m^*b_2 & \cdots & a_m^*b_n \end{bmatrix}\]

그러나 1.1절에서 했던 것처럼, “rows times columns”가 아니라 “columns times rows”로 계산하자는 것이 핵심 아이디어이다. 이를 이해하기 위해서는 먼저 하나의 column과 하나의 row의 곱인 rank one matrix $uv^T$를 살펴보자. 여기서는 이를 “outer product”라고 표현했다.

\[\begin{aligned} uv^T &= \begin{bmatrix} 2 \\ 2 \\ 1 \end{bmatrix} \begin{bmatrix} 3 & 4 & 6 \end{bmatrix} = \begin{bmatrix} 6 & 8 & 12 \\ 6 & 8 & 12 \\ 3 & 4 & 6 \end{bmatrix} \end{aligned}\]

모든 column이 $u$의 상수배이고, 모든 row가 $v^T$의 상수배이다. 이러한 특성 때문에 $uv^T$는 rank one matrix이다. 다른 말로 하면 $\mathbf{C}(uv^T)$는 $u$ 방향의 직선이고, $\mathbf{R}(uv^T)$는 $v$ 방향의 직선이다.

2. $AB$ = Sum of Rank One Matrices

이제 $AB$를 column-row multiplication으로 보고, 다음과 같이 나타낼 수 있다.

\[AB = \begin{bmatrix} \vert & \vert & & \vert \\ a_1 & a_2 & \cdots & a_n \\ \vert & \vert & & \vert \end{bmatrix} \begin{bmatrix} - & b_1^* & - \\ - & b_2^* & - \\ & \vdots & \\ - & b_n^* & - \end{bmatrix} = a_1b_1^* + a_2b_2^* + \cdots + a_nb_n^*\]

이것은 각각의 column과 row의 곱인 $a_kb_k^*$의 합으로 이루어진다. 따라서 다음과 같이 표현할 수 있겠다.

$AB$는 rank one matrix들의 합이다.

$AB$를 $(m \times n)(n \times p)$라고 하면 계산할 때에는 총 $mnp$번의 곱셈이 필요하다. Rank one matrices 하나를 계산할 때마다 $m \times p$번 곱셈이 필요하고, 그런 rank one matrices가 총 $n$개 있으므로 $mnp$번의 곱셈이 필요하다. 이는 row-column multiplication에서도 마찬가지이다. 내적을 1회 시행할 때 $n$번의 곱셈이 필요하고, 총 $m \times p$번의 내적이 필요하므로 $mnp$번의 곱셈이 필요하다. 결국 어떻게 하나 $mnp$번의 곱셈이 필요하다.

3. Insight from Column times Row

이러한 “outer product approach”가 중요한 이유는 뭘까? 결국 $A$는 작은 $uv^T$들로 쪼개질 수 있고, 만약 $A$의 중요한 부분을 찾고 싶다면, 가장 큰 $uv^T$를 선택할 수 있다. 실제로 중요한 응용선형대수학의 주제는 $A=CR$로 분해한 뒤 $c_kr_k^*$를 분석하는 것이다. 다른 중요한 분해들에서도 마찬가지이다. 책에서는 앞으로 5가지 중요한 분해(factorization)를 다룬다.

1. $A=LU$: Elimination
2. $A=QR$: Orthogonalization (Gram-Schmidt)
3. $S = Q \Lambda Q^T$: Eigenvalue, Eigenvector (Spectral Theorem)
4. $A=X \Lambda X^{-1}$: Diagonalization
5. $A=U \Sigma V^T$: Singular Value Decomposition (SVD)

4. Selected Solutions to Problems

Problem 5.

Q. 다음 $A,B,C$에 대해 $\left(AB \right)C = A\left(BC \right)$가 성립하는지 확인하라.

\[A = \begin{bmatrix} 1 & a \\ 0 & 1 \end{bmatrix}, \quad B = \begin{bmatrix} b_1 & b_2 \\ b_3 & b_4 \end{bmatrix}, \quad C = \begin{bmatrix} 1 & 0 \\ c & 1 \end{bmatrix}\]

식이 성립하는지 확인하는 것은 계산에 불과하지만 이 문제에서 얻을 것은 다음과 같다.

$B$의 combination of rows를 얻고 싶으면, $AB$를 계산한다.
$A$의 combination of columns를 얻고 싶으면, $BC$를 계산한다.

이로부터 다음 결과도 얻을 수 있다.

$AB$의 row space는 $B$의 row space에 포함된다.
$BC$의 column space는 $B$의 column space에 포함된다.

MIT 18.065 카테고리 내 다른 글 보러가기