행렬곱 접근법

$m \times n$ 행렬 $A$와 $n \times p$ 행렬 $B$를 곱하면, 결과 행렬 $AB$의 형상은 $m \times p$이다.

$$(m \times n)(n \times p) = (m \times p)$$

이때 $B$의 모든 열은 $A$와 곱해진다.

열 기반 접근법에서는 $B$를 열벡터들의 묶음으로 보고, $A$를 각각의 열벡터에 곱한다.

$$AB = A[b_1 \ \ b_2] = [Ab_1 \ \ Ab_2]$$

행렬곱에서 중요한 사실은 결합법칙이 성립한다는 것이다.

$$(AB)C = A(BC)$$

행렬곱의 순서를 바꿀 수는 없지만, 괄호를 치는 순서는 바꿀 수 있다. 이때 계산 순서에 따라 연산 횟수가 크게 달라질 수 있다.

---

첫 번째 접근법: $A$의 행과 $B$의 열의 내적

$AB$의 각 원소는 내적으로 계산된다.

$$(AB)_{ij} = (\text{row } i \text{ of } A) \cdot (\text{column } j \text{ of } B)$$

즉, $AB$의 $(i,j)$ 원소는 $A$의 $i$번째 행과 $B$의 $j$번째 열의 내적이다.

일반적으로 두 행렬 $A(m \times n)$과 $B(n \times p)$의 곱은 다음과 같이 계산된다.

$$(AB)_{ij} = \sum_{k=1}^{n} a_{ik}b_{kj}$$

결과 행렬 $AB$는 $m \times p$개의 원소를 가진다. 각 원소를 계산하려면 길이 $n$짜리 내적을 수행해야 한다.

따라서 일반적인 사각행렬의 경우 연산 횟수는 다음과 같다.

$$O(mnp)$$

특히 $n \times n$ 정방행렬끼리 곱하는 경우 시간 복잡도는 다음과 같다.

$$O(n^3)$$

정리하면 다음과 같다.

$mp$개의 dot product가 있고, 각 dot product는 $n$단계로 계산된다.

형상은 다음처럼 볼 수 있다.

$$\begin{bmatrix} m \ \text{rows} \\ n \ \text{columns} \end{bmatrix} \begin{bmatrix} n \ \text{rows} \\ p \ \text{columns} \end{bmatrix} = \begin{bmatrix} m \ \text{rows} \\ p \ \text{columns} \end{bmatrix}$$

---

두 번째 접근법: Column Picture

Column picture에서는 $B$를 여러 개의 열벡터로 나누어 본다.

$$B = [b_1 \ \cdots \ b_p]$$

그러면 행렬곱은 다음과 같다.

$$A[b_1 \ \cdots \ b_p] = [Ab_1 \ \cdots \ Ab_p]$$

즉, $AB$의 각 열은 $A$에 $B$의 각 열을 곱한 결과이다.

---

세 번째 접근법: Row Picture

Row picture에서는 $A$의 각 행이 $B$ 전체와 곱해진다고 본다.

예를 들어 $A$의 $i$번째 행을 $B$에 곱하면, 그 결과가 $AB$의 $i$번째 행이 된다.

$$[\text{row } i \text{ of } A] \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix} = [\text{row } i \text{ of } AB]$$

즉, $AB$의 각 행은 $A$의 해당 행이 $B$와 곱해진 결과이다.

---

네 번째 접근법: $A$의 열과 $B$의 행

네 번째 접근법은 외적(outer product) 기반이다.

$A$의 열벡터와 $B$의 행벡터를 곱하면 하나의 행렬이 만들어진다.

$$(\text{column } i)(\text{row } i)$$

여기서 $A$의 열은 $m \times 1$이고, $B$의 행은 $1 \times p$이다.

따라서 두 벡터의 곱은 $m \times p$ 행렬이 된다.

$$(m \times 1)(1 \times p) = (m \times p)$$

행렬곱 $AB$는 이러한 외적 행렬들의 합으로 표현된다.

$$AB = (\text{col } 1)(\text{row } 1) + (\text{col } 2)(\text{row } 2) + \cdots + (\text{col } n)(\text{row } n)$$

예를 들어 다음 행렬곱을 보자.

$$AB = \begin{bmatrix} a & b \\ c & d \end{bmatrix} \begin{bmatrix} E & F \\ G & H \end{bmatrix}$$

일반적인 방식으로 계산하면 다음과 같다.

$$AB = \begin{bmatrix} aE+bG & aF+bH \\ cE+dG & cF+dH \end{bmatrix}$$

이를 외적 기반으로 보면 다음과 같다.

$$AB = \begin{bmatrix} a \\ c \end{bmatrix} \begin{bmatrix} E & F \end{bmatrix} + \begin{bmatrix} b \\ d \end{bmatrix} \begin{bmatrix} G & H \end{bmatrix}$$

즉, $A$의 열과 $B$의 행을 곱한 행렬들의 합으로 $AB$를 얻을 수 있다.

---

행렬 연산의 규칙

1. 행렬 덧셈

행렬 덧셈에서는 교환 법칙이 성립한다.

$$A+B = B+A$$

분배 법칙도 성립한다.

$$c(A+B) = cA + cB$$

결합 법칙도 성립한다.

$$A+(B+C) = (A+B)+C$$

---

2. 행렬 곱셈

행렬 곱셈에서는 교환 법칙이 일반적으로 성립하지 않는다.

$$AB \neq BA$$

분배 법칙은 성립한다.

$$A(B+C) = AB + AC$$ $$(A+B)C = AC + BC$$

결합 법칙도 성립한다.

$$A(BC) = (AB)C$$

단위행렬은 행렬곱에서 1과 비슷한 역할을 한다.

$$IA = A$$

또한 크기가 맞는 경우 다음도 성립한다.

$$AI = A$$

---

3. 행렬 제곱

행렬의 거듭제곱은 같은 행렬을 반복해서 곱한 것이다.

$$A^p = AAAA \cdots A$$

여기서 $A$는 총 $p$번 곱해진다.

같은 행렬의 거듭제곱끼리는 다음이 성립한다.

$$(A^p)(A^q)=A^{p+q}$$

또한 다음도 성립한다.

$$(A^p)^q = A^{pq}$$

주의할 점은 행렬의 음수 제곱은 역행렬을 의미한다는 것이다.

$$A^{-1}$$

이는 일반 스칼라의 음수 제곱인 $\frac{1}{a}$와 완전히 같은 개념은 아니다. 행렬에서는 역행렬이 존재할 때만 $A^{-1}$을 정의할 수 있다.

---

블록 행렬과 블록 곱셈

블록 행렬은 큰 행렬을 작은 행렬, 즉 블록으로 쪼개어 보는 방식이다.

예를 들어 다음 행렬은 여러 개의 단위행렬 블록으로 볼 수 있다.

$$A= \left[ \begin{array}{cc|cc|cc} 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ \hline 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \end{array} \right] = \begin{bmatrix} I & I & I \\ I & I & I \end{bmatrix}$$

전체 행렬의 크기가 일치하고 블록 사이즈가 맞다면, 행렬 덧셈은 각 위치의 블록끼리 더해서 계산할 수 있다.

블록 행렬의 곱셈도 일반 행렬곱과 비슷하게 계산된다.

$$\begin{bmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{bmatrix} \begin{bmatrix} B_{11} \\ B_{21} \end{bmatrix} = \begin{bmatrix} A_{11}B_{11} + A_{12}B_{21} \\ A_{21}B_{11} + A_{22}B_{21} \end{bmatrix}$$

이때 $A$의 열 방향 분할과 $B$의 행 방향 분할이 서로 일치해야 한다.

즉, $A$의 열 사이의 컷이 $B$의 행 사이의 컷과 맞아야 블록 곱셈이 가능하다.

---

외적을 이용한 행렬곱 예시

행렬곱은 외적의 합으로도 계산할 수 있다.

$$\begin{bmatrix} 1 & 4 \\ 1 & 5 \end{bmatrix} \begin{bmatrix} 3 & 2 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \end{bmatrix} \begin{bmatrix} 3 & 2 \end{bmatrix} + \begin{bmatrix} 4 \\ 5 \end{bmatrix} \begin{bmatrix} 1 & 0 \end{bmatrix}$$

각 외적을 계산하면 다음과 같다.

$$= \begin{bmatrix} 3 & 2 \\ 3 & 2 \end{bmatrix} + \begin{bmatrix} 4 & 0 \\ 5 & 0 \end{bmatrix}$$

따라서 결과는 다음과 같다.

$$= \begin{bmatrix} 7 & 2 \\ 8 & 2 \end{bmatrix}$$

---

블록 소거

블록 소거는 기존 가우스 소거법의 아이디어를 블록 행렬에 적용한 것이다.

다음 블록 행렬을 생각한다.

$$\begin{bmatrix} A & B \\ C & D \end{bmatrix}$$

여기서 피벗 블록은 $A$이다. 일반 소거법에서 피벗 원소 $a$에 해당한다.

소거 대상은 $A$ 아래에 있는 $C$ 블록이다. 일반 소거법에서 제거 대상 $c$에 해당한다.

일반 소거법에서는 두 번째 행에서 첫 번째 행에 $\frac{c}{a}$를 곱한 것을 뺀다.

블록 소거법에서는 두 번째 블록 행에서 첫 번째 블록 행에 어떤 행렬을 곱한 것을 뺀다.

목표는 $C$ 위치에 영행렬이 오도록 만드는 것이다.

---

블록 소거 과정

두 번째 블록 행은 다음과 같다.

$$[C \ \ D]$$

첫 번째 블록 행은 다음과 같다.

$$[A \ \ B]$$

두 번째 블록 행에서 첫 번째 블록 행에 어떤 행렬 $X$를 곱한 것을 뺀다고 하자.

$$[C \ \ D] - X[A \ \ B]$$

$C$ 위치를 0으로 만들려면 다음을 만족해야 한다.

$$C - XA = 0$$

따라서 $X$는 다음과 같다.

$$X = CA^{-1}$$

즉, 두 번째 블록 행에서 첫 번째 블록 행에 $CA^{-1}$을 곱한 것을 빼면 된다.

이 연산을 행렬로 표현하면 다음과 같다.

$$E_{\text{block}} = \begin{bmatrix} I & 0 \\ -CA^{-1} & I \end{bmatrix}$$

이 행렬은 다음 연산을 수행한다.

$CA^{-1} \times$ 첫 번째 블록 행을 두 번째 블록 행에서 뺀다.

실제로 곱하면 다음과 같다.

$$\begin{bmatrix} I & 0 \\ -CA^{-1} & I \end{bmatrix} \begin{bmatrix} A & B \\ C & D \end{bmatrix} = \begin{bmatrix} A & B \\ 0 & D - CA^{-1}B \end{bmatrix}$$

각 블록을 보면 다음과 같다.

$(2,1)$ 블록은 다음과 같다.

$$(-CA^{-1})A + IC = -C + C = 0$$

$(2,2)$ 블록은 다음과 같다.

$$(-CA^{-1})B + ID = D - CA^{-1}B$$

---

슈어 보완(Schur Complement)

소거를 수행한 뒤, $(2,2)$ 위치에 새롭게 나타난 블록을 슈어 보완이라고 한다.

$$S = D - CA^{-1}B$$

이 블록을 $A$에 대한 슈어 보완이라고 부른다.

일반적인 $2 \times 2$ 행렬의 소거 결과와 형태가 같다.

숫자에서는 다음과 같은 꼴이다.

$$d - \frac{c}{a}b$$

블록에서는 다음과 같은 꼴이다.

$$D - CA^{-1}B$$

즉, 큰 행렬을 $A, B, C, D$라는 블록으로 나누었을 때, $A$를 피벗으로 사용하여 $C$를 0으로 만드는 과정에서 슈어 보완이 자연스럽게 등장한다.

슈어 보완은 행렬식 계산이나 선형 방정식 풀이 등에서 유용하게 사용된다.

예를 들어 $A^{-1}$이 존재할 때 다음 관계가 성립한다.

$$\det \begin{bmatrix} A & B \\ C & D \end{bmatrix} = \det(A)\det(D - CA^{-1}B)$$

---

정리

1. $AB$의 $(i,j)$ 원소

$AB$의 $(i,j)$ 원소는 $A$의 $i$번째 행과 $B$의 $j$번째 열의 점곱이다.

$$(AB)_{ij} = (\text{row } i \text{ of } A) \cdot (\text{column } j \text{ of } B)$$

예를 들어 다음 두 행렬을 보자.

$$A = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}, \quad B = \begin{bmatrix} 5 & 6 \\ 7 & 8 \end{bmatrix}$$

$AB$의 $(1,2)$ 원소는 다음과 같이 계산한다.

• $A$의 1번째 행: $\begin{bmatrix} 1 & 2 \end{bmatrix}$
• $B$의 2번째 열: $\begin{bmatrix} 6 \\ 8 \end{bmatrix}$

따라서 점곱은 다음과 같다.

$$(1 \times 6) + (2 \times 8) = 22$$

---

2. 행렬곱의 연산량

$m \times n$ 행렬과 $n \times p$ 행렬을 곱하면 $m \times p$ 행렬이 나온다.

$$(m \times n)(n \times p) = (m \times p)$$

결과 행렬은 총 $m \times p$개의 원소를 가진다.

각 원소 하나를 계산하려면 길이 $n$짜리 내적이 필요하므로 $n$번의 곱셈이 필요하다.

따라서 전체 곱셈 횟수는 다음과 같다.

$$mnp$$

---

3. 행렬곱의 결합 법칙

행렬곱에서는 결합 법칙이 성립한다.

$$A(BC) = (AB)C$$

행렬의 순서 $A, B, C$를 바꾸는 것은 불가능하지만, 곱셈을 수행하는 괄호의 위치는 바꿀 수 있다.

이 법칙이 중요한 이유는 계산 효율성 때문이다.

예를 들어 $A$가 $10 \times 100$, $B$가 $100 \times 5$, $C$가 $5 \times 50$ 행렬이라고 하자.

먼저 $(AB)C$로 계산하면 다음과 같다.

• $AB$ 계산: $10 \times 100 \times 5 = 5{,}000$
• $(AB)C$ 계산: $10 \times 5 \times 50 = 2{,}500$
• 총합: $7{,}500$

반대로 $A(BC)$로 계산하면 다음과 같다.

• $BC$ 계산: $100 \times 5 \times 50 = 25{,}000$
• $A(BC)$ 계산: $10 \times 100 \times 50 = 50{,}000$
• 총합: $75{,}000$

즉, 결합 법칙은 성립하지만 계산 순서에 따라 연산 횟수는 크게 달라질 수 있다.

또한 이 법칙이 성립하기 때문에 $A^3 = AAA$ 같은 행렬의 거듭제곱이 잘 정의된다.

---

4. 행렬곱은 외적의 합으로도 표현된다

$AB$는 $A$의 $j$번째 열과 $B$의 $j$번째 행을 곱한 $n$개 행렬의 합으로 볼 수 있다.

$A$를 $n$개의 열벡터 $\mathbf{c}_j$로 나누고, $B$를 $n$개의 행벡터 $\mathbf{r}_j$로 나누면 다음과 같다.

$$AB = \sum_{j=1}^{n} \mathbf{c}_j\mathbf{r}_j$$

즉,

$$AB = \mathbf{c}_1\mathbf{r}_1 + \mathbf{c}_2\mathbf{r}_2 + \cdots + \mathbf{c}_n\mathbf{r}_n$$

여기서 $\mathbf{c}_j$는 $m \times 1$ 벡터이고, $\mathbf{r}_j$는 $1 \times p$ 벡터이다.

따라서 $\mathbf{c}_j\mathbf{r}_j$는 $m \times p$ 행렬이 된다.

이를 외적이라고 한다.

---

5. 블록 곱셈

블록의 모양이 올바르게 맞는다면 블록 곱셈이 허용된다.

$$\begin{bmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{bmatrix} \begin{bmatrix} B_{11} & B_{12} \\ B_{21} & B_{22} \end{bmatrix} = \begin{bmatrix} A_{11}B_{11} + A_{12}B_{21} & A_{11}B_{12} + A_{12}B_{22} \\ A_{21}B_{11} + A_{22}B_{21} & A_{21}B_{12} + A_{22}B_{22} \end{bmatrix}$$

이 계산이 성립하려면 블록의 크기가 맞아야 한다.

예를 들어 다음 조건이 필요하다.

• $A_{11}$의 열 개수와 $B_{11}$의 행 개수가 같아야 한다.
• $A_{12}$의 열 개수와 $B_{21}$의 행 개수가 같아야 한다.
• 즉, $A$ 행렬의 수직 분할이 $B$ 행렬의 수평 분할과 일치해야 한다.

---

6. 블록 소거와 슈어 보완

블록 소거는 다음 블록 행렬에서 시작한다.

$$M = \begin{bmatrix} A & B \\ C & D \end{bmatrix}$$

여기서 $A^{-1}$이 존재한다고 가정한다.

$C$ 위치를 0으로 만들기 위해 다음 블록 소거 행렬을 곱한다.

$$\begin{bmatrix} I & 0 \\ -CA^{-1} & I \end{bmatrix}$$

그러면 다음과 같이 소거된다.

$$\begin{bmatrix} I & 0 \\ -CA^{-1} & I \end{bmatrix} \begin{bmatrix} A & B \\ C & D \end{bmatrix} = \begin{bmatrix} A & B \\ 0 & D - CA^{-1}B \end{bmatrix}$$

이때 새롭게 나타나는 블록

$$D - CA^{-1}B$$

를 슈어 보완이라고 한다.