추가 설명 — Strassen의 7은 어디서 왔고, 왜 최소인가

행렬 곱셈 본편은 Strassen의 7개 곱이 답을 재구성함( $C$ 의 네 블록이 맞음)을 검증했다. 하지만 두 가지가 남았다. 그 일곱 개는 대체 어디서 왔는가, 그리고 여섯 개로는 안 되는가. 이 글은 “곱셈 한 번”의 의미를 다시 정의해 이 둘에 답한다.

이 글에서 다루는 내용

“곱셈 한 번”을 이중선형 곱으로 다시 보기 — 왜 이것이 곱셈 횟수의 올바른 단위인가
복소수 곱을 4번 → 3번으로 줄이는 가우스의 요령 — Strassen의 축소판
2×2 행렬 곱의 랭크가 정확히 7이라는 사실(6은 불가능)과 그 의미
3×3 이상에서 최소 곱셈 수는 아직 열린 문제

”곱셈 한 번”을 다시 정의한다

본편에서는 곱셈 횟수만 셌다. Strassen의 각 곱을 자세히 보면 형태가 특별하다.

P_5 = (A_{11} + A_{22})\,(B_{11} + B_{22})

이는 $A$ 의 블록을 선형결합한 값과 $B$ 의 블록을 선형결합한 값을 곱한 형태다. 나머지 $P_i$ 도 모두 그렇다. 결과 블록 $C_{ij}$ 는 이 곱들의 선형결합으로 만들어진다. 여기서 곱셈이 진짜로 일어나는 곳은 오직 “선형결합 × 선형결합” 지점뿐이고, 선형결합 자체는 덧셈·뺄셈(스칼라배)이다.

정의 1이중선형 곱

행렬 곱을 계산할 때의 이중선형 곱(bilinear product) 이란

\Big(\textstyle\sum_{i} \alpha_i \,A_i\Big)\Big(\textstyle\sum_{j} \beta_j \,B_j\Big)

형태의 곱 하나를 말한다. 여기서 $A_i, B_j$ 는 입력 블록이고 $\alpha_i,\beta_j$ 는 상수다. 왼쪽은 $A$ 의 원소들만, 오른쪽은 $B$ 의 원소들만 섞는다.

이렇게 단위를 잡는 이유는, 덧셈은 싸고 곱셈은 비싸며 재귀에서 비용을 지배하는 쪽이 곱셈이기 때문이다(본편의 점화식에서 $\Theta(N^2)$ 덧셈이 $N^{\log_2 7}$ 에 흡수된 대목을 떠올리자). 진짜 물어야 할 질문은 이것이다.

$C$ 의 네 블록을 모두 이 이중선형 곱들의 선형결합으로 얻으려면, 최소 몇 개의 이중선형 곱이 필요한가?

나이브는 8개, Strassen은 7개를 쓴다. 이 “최소 개수”에는 이름이 있다.

핵심 — 곱셈의 최소 개수 = 랭크

행렬 곱은 입력 $A$ , $B$ 에 각각 선형이고 출력에 이중선형인 사상이다. 이런 이중선형 사상을 이중선형 곱들의 합으로 나타낼 때 필요한 최소 항 수를 그 사상의 랭크(rank) 라 부른다(텐서 랭크). 즉 “2×2 블록 곱에 곱셈이 최소 몇 번 드는가”는 2×2 행렬 곱 사상의 랭크는 얼마인가와 같은 질문이다.

발판: 복소수 곱을 3번으로

랭크를 정면으로 다루기 전에, 훨씬 작은 예로 “곱을 덧셈과 맞바꾼다”는 감각을 잡자. 두 복소수의 곱

(a + b\,i)(c + d\,i) = (ac - bd) + (ad + bc)\,i

를 정의대로 계산하면 실수 곱이 네 번( $ac,\,bd,\,ad,\,bc$ ) 든다. 가우스는 세 번으로 충분함을 알았다.

정리 1복소수 곱은 실수 곱 3번이면 된다

k_1 = c\,(a+b),\qquad k_2 = a\,(d-c),\qquad k_3 = b\,(c+d)

로 두면, 곱의 실수부는 $k_1 - k_3$ , 허수부는 $k_1 + k_2$ 이다. 곱셈은 $k_1,k_2,k_3$ 의 세 번뿐이다.

증명. 직접 전개한다.

\begin{aligned} k_1 - k_3 &= c(a+b) - b(c+d) = ca + cb - bc - bd = ac - bd, \\ k_1 + k_2 &= c(a+b) + a(d-c) = ca + cb + ad - ac = bc + ad. \end{aligned}

각각 곱의 실수부·허수부와 일치한다. $k_1,k_2,k_3$ 을 만드는 데 곱셈은 세 번, 나머지는 덧셈·뺄셈뿐이다. ∎

핵심은 $k_1 = c(a+b)$ 이 실수부와 허수부 양쪽에 재활용된다는 데 있다. 하나의 곱을 여러 출력이 나눠 쓰기 때문에 곱의 총 개수가 준다. Strassen의 $C_{11}$ 과 $C_{22}$ 가 $P_5$ 를 공유한 방식과 정확히 같은 요령이다. Strassen은 이 아이디어를 $2\times2$ 행렬 블록으로 끌어올려, 8개의 이중선형 곱을 7개로 묶은 랭크 7짜리 분해를 찾아냈다.

어디서 왔는가

솔직히 말하면, Strassen의 정확한 일곱 개는 “이 원리에서 유일하게 도출되는 공식”이 아니다. 랭크 7짜리 분해는 여러 형태가 있고(부호·순서를 바꾼 변형이 많다), Strassen이 제시한 형태는 그중 하나다. 중요한 점은 개별 공식의 출처가 아니라 이중선형 곱을 공유하면 8을 7로 줄일 수 있다는 구조적 사실이다.

왜 6개는 안 되는가

그렇다면 더 욕심내서 6개로 줄일 수는 없을까? 없다. 이것이 $2\times2$ 에서 7이 갖는 특별한 위치다.

핵심 정리 — 2×2 행렬 곱의 랭크는 정확히 7

$2\times2$ 행렬 곱 사상의 랭크는 $7$ 이다. Strassen(1969)이 7개로 가능함을 보여 랭크 $\le 7$ 을, Winograd(1971)가 6개로는 불가능함을 증명해 랭크 $\ge 7$ 을 확립했다. 이로써 이중선형 곱의 관점에서 $2\times2$ 블록 곱에 필요한 곱셈은 최소 7번이며, Strassen은 이 하한을 달성한다.

하한 $\ge 7$ 의 증명은 이 글의 범위를 넘는 대수적 논증이라 결과만 인용한다. 왜 6으로 안 되는지를 여기서 설명할 수 있는 직관은 없다. 6개의 곱으로 만들 수 있는 이중선형 사상의 모임이 $2\times2$ 곱을 포함하지 못한다는 것이 Winograd가 보인 내용이고, 그 논증은 계수체 위의 대수적 성질에 기댄다.

3×3부터는 아직 모른다

$2\times2$ 는 7로 깔끔히 닫혔지만, $3\times3$ 행렬 곱의 최소 곱셈 수는 아직 미해결이다. Laderman이 23번으로 가능함을 보여 상한이 서 있고, 하한 쪽은 20 안팎에서 조금씩 올라가는 중이다. 하한 값은 계수체를 무엇으로 잡느냐에 따라서도 달라지므로, 특정 숫자를 인용할 때는 어느 체에서 언제 나온 결과인지 함께 봐야 한다.

한 가지 구분해 둘 것이 있다. 고정 크기의 랭크와 행렬 곱 지수 $\omega$ 는 같은 문제가 아니다. $3\times3$ 의 랭크를 정확히 알아내도 그것만으로 $\omega$ 가 정해지지 않는다. $\omega$ 는 크기를 무한히 키울 때의 점근적 양이고, 오늘날의 상한은 한 고정 크기의 알고리즘이 아니라 훨씬 복잡한 점근적 기법에서 나온다. 다만 두 문제가 곱셈을 몇 번 해야 하는가라는 같은 뿌리를 공유한다는 점은 그대로다.

Winograd 변형 — 곱은 그대로, 덧셈을 줄인다

곱셈 7번은 최소라 더 못 줄인다. 하지만 Strassen 원형은 블록 덧셈·뺄셈을 18번 쓰는데, 이는 줄일 수 있다. Winograd 변형은 같은 7번의 곱을 쓰면서 덧셈·뺄셈을 15번으로 낮춘다. 공통으로 쓰이는 중간 합( $A_{11}+A_{12}$ 같은 항)을 한 번만 계산해 여러 곱이 나눠 쓰도록 정리한 방식이다.

곱셈 횟수가 재귀의 지수를 정하므로 점근 복잡도는 $\Theta(N^{\log_2 7})$ 로 그대로다. 그러나 덧셈의 상수를 줄이면 실제 구현에서 나이브로 전환하는 임계 크기가 낮아져, Strassen이 이기기 시작하는 지점이 앞당겨진다.

정리

“곱셈 한 번”을 이중선형 곱으로 다시 정의하면, 곱셈의 최소 개수는 행렬 곱 사상의 랭크가 된다. 가우스가 복소수 곱에서 하나의 곱을 두 출력이 공유해 4를 3으로 줄였듯, Strassen은 $2\times2$ 블록에서 8을 7로 줄였다. 그 7은 $2\times2$ 행렬 곱 사상의 랭크이며, 6으로는 안 된다는 것이 Winograd의 결과다. 이 글은 그 하한을 증명하지 않고 인용했다. 본편으로 돌아가면, 이 “7”이 어떻게 $N^{\log_2 7}$ 의 지수로 자라나는지 다시 읽어볼 수 있다.

← 행렬 곱셈 본편으로