행렬 곱셈

1. 개요

행렬 곱셈은 두 행렬을 곱하여 새로운 행렬을 생성하는 연산이다. m × n 행렬 A와 n × p 행렬 B의 곱 AB는 m × p 행렬로 정의되며, 결과 행렬의 각 성분은 A의 행과 B의 열의 스칼라곱으로 계산된다. 행렬 곱셈은 결합법칙이 성립하지만, 일반적으로 교환법칙은 성립하지 않는다. 행렬 곱셈은 선형 변환, 연립 일차 방정식, 생산 모델링 등 다양한 분야에 응용된다. 스칼라 곱, 아다마르 곱, 크로네커 곱 등 다른 유형의 행렬 곱셈도 존재한다. 행렬 곱셈의 계산 복잡도는 알고리즘에 따라 다르며, 슈트라센 알고리즘과 같은 효율적인 알고리즘이 개발되었다.

2. 표기

행렬은 굵은 대문자(예: A)로, 벡터는 굵은 소문자(예: a)로, 행렬 및 벡터의 성분은 기울임체(예: *A*, *a*)로 표기한다. 첨자표기법에 따라 행렬 A의 *i*행 *j*열 성분은 (A)_*ij*, *A*_*ij*, *a*_*ij* 등으로 표시한다. 반면 행렬 성분의 집합은 A₁, A₂ 등으로 표시한다.

3. 정의

A^영어, B^영어를 각각 m × n, n × p 행렬이라고 하자.

: $\backslash mathbf\{A\}=\backslash begin\{pmatrix\}$
a_{11} & a_{12} & \cdots & a_{1n} \\
a_{21} & a_{22} & \cdots & a_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
a_{m1} & a_{m2} & \cdots & a_{mn} \\
\end{pmatrix},\quad\mathbf{B}=\begin{pmatrix}
b_{11} & b_{12} & \cdots & b_{1p} \\
b_{21} & b_{22} & \cdots & b_{2p} \\
\vdots & \vdots & \ddots & \vdots \\
b_{n1} & b_{n2} & \cdots & b_{np} \\
\end{pmatrix}

행렬곱 는 m × p 행렬로 정의된다. 이때 곱셈 기호는 따로 쓰지 않는다.

: $\backslash mathbf\{C\}=\backslash begin\{pmatrix\}$
c_{11} & c_{12} & \cdots & c_{1p} \\
c_{21} & c_{22} & \cdots & c_{2p} \\
\vdots & \vdots & \ddots & \vdots \\
c_{m1} & c_{m2} & \cdots & c_{mp} \\
\end{pmatrix}

이때 i = 1, ..., m, j = 1, ..., p에 대해 C의 성분은 다음과 같이 정의된다.

: $c\_\{ij\}\; =\; a\_\{i1\}b\_\{1j\}\; +\; a\_\{i2\}b\_\{2j\}\; +\backslash cdots\; +\; a\_\{in\}b\_\{nj\}=\; \backslash sum\_\{k=1\}^n\; a\_\{ik\}b\_\{kj\},$

이는 A의 i번째 행과 B의 j번째 열의 성분들을 각각 곱해 더한 것과 같은데, 다시 말해 A의 i번째 행과 B의 j번째 열의 스칼라곱이다.

따라서 AB는 다음과 같이 쓸 수도 있다.

: $\backslash mathbf\{C\}=\backslash begin\{pmatrix\}$
a_{11}b_{11} +\cdots + a_{1n}b_{n1} & a_{11}b_{12} +\cdots + a_{1n}b_{n2} & \cdots & a_{11}b_{1p} +\cdots + a_{1n}b_{np} \\
a_{21}b_{11} +\cdots + a_{2n}b_{n1} & a_{21}b_{12} +\cdots + a_{2n}b_{n2} & \cdots & a_{21}b_{1p} +\cdots + a_{2n}b_{np} \\
\vdots & \vdots & \ddots & \vdots \\
a_{m1}b_{11} +\cdots + a_{mn}b_{n1} & a_{m1}b_{12} +\cdots + a_{mn}b_{n2} & \cdots & a_{m1}b_{1p} +\cdots + a_{mn}b_{np} \\
\end{pmatrix}


이러한 이유로 첫째 행렬의 열 갯수와 둘째 행렬의 행 갯수가 동일해야 행렬곱이 정의될 수 있다.

대부분의 경우 행렬의 성분은 숫자이지만, 덧셈과 곱셈이 정의되고, 곱셈의 결합법칙과 덧셈의 교환법칙이 성립하여 곱셈의 분배법칙이 성립하게 되는 다른 수학적 대상들도 성분이 될 수 있다. 가장 대표적인 예시로 성분이 행렬인 블록 행렬을 생각할 수 있다.

두 행렬 A와 B의 곱을 도표로 나타낸 것으로, 곱 행렬의 각 교집합이 A의 행과 B의 열에 어떻게 해당하는지 보여준다.

$$$$
\overset{4\times 2 \text{ 행렬}}{\begin{bmatrix}
a_{11} & a_{12} \\
\cdot & \cdot \\
a_{31} & a_{32} \\
\cdot & \cdot \\
\end{bmatrix}}
\overset{2\times 3\text{ 행렬}}{\begin{bmatrix}
\cdot & b_{12} & b_{13} \\
\cdot & b_{22} & b_{23} \\
\end{bmatrix}}

= \overset{4\times 3\text{ 행렬}}{\begin{bmatrix}
\cdot & c_{12} & \cdot \\
\cdot & \cdot & \cdot \\
\cdot & \cdot & c_{33} \\
\cdot & \cdot & \cdot \\
\end{bmatrix}}


오른쪽 그림에서 원으로 표시된 교차점의 값은 다음과 같다.
$$\backslash begin\{align\}$$
c_{12} & = a_{11} b_{12} + a_{12} b_{22} \\
c_{33} & = a_{31} b_{13} + a_{32} b_{23} .
\end{align}

길이가 n인 벡터 x는 n × 1 행렬 X에 해당하는 열 벡터로 볼 수 있으며, 여기서 항목은 X_i1 = x_i로 주어진다. A가 m × n 행렬인 경우, Ax로 표시되는 행렬-벡터 곱은 열 벡터로 간주될 때 m × 1 행렬 AX와 동일한 벡터 y이다. 인덱스 표기법으로 나타내면 다음과 같다.

: $y\_i=\backslash sum\_\{j=1\}^n\; a\_\{ij\}x\_j.$

마찬가지로, 길이가 n인 벡터 x는 1 × n 행렬에 해당하는 행 벡터로 볼 수 있다. 행 벡터임을 명확히 하기 위해, 이 맥락에서는 열 벡터의 전치 행렬로 표현하는 것이 일반적이다. 따라서 x^TA와 같은 표기를 볼 수 있다. 등식 x^TA = (A^Tx)^T가 성립한다. 지표 표기법에서, A가 n × p 행렬이고, x^TA = y^T인 경우 다음과 같다.

: $y\_k=\backslash sum\_\{j=1\}^n\; x\_j\; a\_\{jk\}.$

두 벡터 a와 b의 내적 a ⋅ b는 길이가 같을 때, 이 벡터들을 행 벡터와 열 벡터로 곱하여 얻는 1 × 1 행렬의 단일 요소와 같다. 즉, a^Tb (또는 b^Ta는 동일한 1 × 1 행렬을 생성한다).

행렬 A의 i행과 행렬 B의 j열의 각 성분의 곱을 실선 부분처럼 취하고, 이어서 점선처럼 더해감으로써, 곱 AB의 ij 성분을 얻는다.

n × m 행렬 A와 m × p 행렬 B를

: $A=\backslash begin\{bmatrix\}$
a_{11} & a_{12} & \cdots & a_{1m} \\
a_{21} & a_{22} & \cdots & a_{2m} \\
\vdots & \vdots & \ddots & \vdots \\
a_{n1} & a_{n2} & \cdots & a_{nm}
\end{bmatrix},\quad
B=\begin{bmatrix}
b_{11} & b_{12} & \cdots & b_{1p} \\
b_{21} & b_{22} & \cdots & b_{2p} \\
\vdots & \vdots & \ddots & \vdots \\
b_{m1} & b_{m2} & \cdots & b_{mp}
\end{bmatrix}

라고 할 때, 이들의 행렬의 곱 AB (통상 곱셈 기호는 특별히 사용하지 않고 병치로 나타낸다)는 각 (i, j) 성분 c_ij가 A의 i행에 가로로 늘어선 성분 a_ik와 B의 j열에 세로로 늘어선 성분 b_kj를 k = 1, 2, ..., m에 걸쳐 더한 합

: $c\_\{ij\}\; =\; \backslash sum\_\{k=1\}^m\; a\_\{ik\}b\_\{kj\}$

로 주어지는 n × p 행렬

: $AB\; =\backslash begin\{bmatrix\}$
c_{11} & c_{12} & \cdots & c_{1p} \\
c_{21} & c_{22} & \cdots & c_{2p} \\
\vdots & \vdots & \ddots & \vdots \\
c_{n1} & c_{n2} & \cdots & c_{np}
\end{bmatrix}

이다. 따라서 곱 AB가 정의되는 것은 A의 열의 개수와 B의 행의 개수가 일치하는 경우에 한정된다 (이 경우에는 m개).

4. 성질

행렬 곱셈은 일반적인 곱셈과 비슷한 성질을 가지지만, 몇 가지 중요한 차이점이 있다.

* 결합법칙: 세 행렬 A, B, C에 대해, 곱셈의 순서와 상관없이 결과는 같다. 즉, (AB)C = A(BC)이다.
* 분배법칙: 행렬 덧셈에 대해 분배법칙이 성립한다. 즉, A(B + C) = AB + AC 이고, (B + C)D = BD + CD 이다.
* 스칼라 곱: 스칼라 *c*와 행렬 A, B의 곱에 대해, *c*(AB) = (*c*A)B = A(*c*B)가 성립한다.
* 전치: 두 행렬의 곱의 전치는 각 행렬의 전치를 순서를 바꾸어 곱한 것과 같다. 즉, (AB)^T = B^TA^T이다.
* 복소 켤레: 복소수 행렬의 경우, (AB)^* = A^*B^*이다. (단, ^*는 켤레 복소수를 나타냄)
* 비가환성: 일반적으로 행렬 곱셈은 교환법칙이 성립하지 않는다. 즉, AB ≠ BA이다. 하지만, *A* + *B* = *AB* 와 같은 특수한 경우에는 교환법칙이 성립할 수 있다.

정사각 행렬의 경우, 행렬 곱셈은 항등 행렬을 항등원으로 갖는 환을 이룬다.

4.1. 정사각 행렬

환의 원소를 갖는 n×n 정사각 행렬의 집합은 곱셈이 모든 행렬 쌍에 대해 정의되므로 항등 행렬(대각선 성분은 1이고 다른 모든 성분은 0인 행렬)을 항등원으로 갖는 환을 이룬다.

만약 n > 1이면, 많은 행렬은 곱셈 역원을 갖지 않는다. 예를 들어, 행(또는 열)의 모든 성분이 0인 행렬은 역행렬을 갖지 않는다. 역행렬이 존재하면, 행렬 A의 역행렬은 A⁻¹로 표시되며, AA⁻¹ = A⁻¹A = I를 만족한다. 역행렬을 갖는 행렬은 가역 행렬이고, 그렇지 않으면 특이 행렬이다. 행렬의 곱은 각 인수가 가역 행렬일 경우에만 가역 행렬이며, (AB)^-1 = B^-1A^-1이다.

가환환에서 곱의 행렬식은 행렬식들의 곱과 같다. 행렬식은 스칼라이고, 스칼라는 교환 가능하므로, det(AB) = det(BA) = det(A)det(B)이다.

정사각 행렬은 자기 자신을 반복해서 곱하여 음이 아닌 정수 거듭제곱으로 올릴 수 있다. 즉:
:A⁰ = I
:A¹ = A
:A^k = AAA (k 번 곱함)

행렬의 k번째 거듭제곱을 계산하는 데에는 단순한 알고리즘(반복 곱셈)을 사용하면 단일 행렬 곱셈 시간의 k – 1배가 필요하다. 이는 매우 시간이 오래 걸릴 수 있으므로 일반적으로 제곱에 의한 거듭제곱을 사용하는 것이 좋다. 이 방법은 2 log₂ k보다 적은 행렬 곱셈이 필요하므로 훨씬 더 효율적이다.

대각 행렬의 경우, 대각 행렬의 k번째 거듭제곱은 항목들을 k 거듭제곱으로 올려 얻는다.

:$$
\begin{bmatrix}
a_{11} & 0 & \cdots & 0 \\
0 & a_{22} & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & a_{nn}
\end{bmatrix}^k =
\begin{bmatrix}
a_{11}^k & 0 & \cdots & 0 \\
0 & a_{22}^k & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & a_{nn}^k
\end{bmatrix}.

5. 응용

행렬 곱셈은 선형 변환을 표현하고 합성하는 데 사용된다. 예를 들어, 유클리드 평면에서 회전 변환은 행렬 곱셈으로 표현할 수 있다.

유클리드 평면에서 직교 좌표계를 사용할 때, 원점을 중심으로 각도 $\backslash alpha$만큼 회전하는 선형 변환은 다음과 같이 표현된다.

:

여기서 원본 점 $(x,y)$와 그 이미지 $(x\text{'},y\text{'})$는 열 벡터로 표기된다.

각도 $\backslash alpha$만큼의 회전과 각도 $\backslash beta$만큼의 회전을 합성한 결과는 다음 행렬 곱셈으로 나타낼 수 있다.

:
\begin{bmatrix} \cos \alpha & - \sin \alpha \\ \sin \alpha & \cos \alpha \end{bmatrix}
= \begin{bmatrix} \cos (\alpha+\beta) & - \sin(\alpha+\beta) \\ \sin(\alpha+\beta) & \cos(\alpha+\beta) \end{bmatrix}

이는 각도 $\backslash alpha+\backslash beta$만큼의 회전에 해당한다.

연립 일차 방정식은 다음과 같은 행렬 방정식 형태로 나타낼 수 있다.

:$\backslash mathbf\{Ax\}=\backslash mathbf\; b$

여기서,
* A는 계수 행렬
* x는 미지수 벡터
* b는 상수 벡터

선형 사상 A는 행렬
:$\backslash mathbf\{A\}=\backslash begin\{pmatrix\}$
a_{11} & a_{12} & \cdots & a_{1n} \\
a_{21} & a_{22} & \cdots & a_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
a_{m1} & a_{m2} & \cdots & a_{mn} \\
\end{pmatrix},
로 정의되며 열 벡터 $\backslash mathbf\; x$를 행렬 곱
:$\backslash mathbf\; y\; =\; \backslash mathbf\; \{Ax\}.$
에 사상한다.

행렬 곱셈은 경제학에서 자원 할당 문제 등 경제학적 모델링에도 활용된다. 예를 들어, 여러 종류의 기본 상품을 사용하여 중간재를 생산하고, 이 중간재를 다시 사용하여 최종 제품을 생산하는 과정을 행렬 곱셈으로 나타낼 수 있다.

가상의 공장에서 4가지 종류의 기본 상품 $b\_1,\; b\_2,\; b\_3,\; b\_4$를 사용하여 3가지 종류의 중간재 $m\_1,\; m\_2,\; m\_3$을 생산하고, 이 중간재는 다시 3가지 종류의 최종 제품 $f\_1,\; f\_2,\; f\_3$을 생산하는 경우를 가정할 수 있다. 행렬

:   와  

는 주어진 양의 중간재에 필요한 기본 상품의 양과, 주어진 양의 최종 제품에 필요한 중간재의 양을 각각 제공한다.

행렬 곱셈을 사용하여 다음을 계산한다.

:

이 행렬은 주어진 양의 최종 상품에 필요한 기본 상품의 양을 직접 제공한다.

이 외에도 행렬 곱셈은 물리학, 화학, 공학, 컴퓨터 과학 등 다양한 분야에서 활용된다.

6. 기타 곱셈

만약 $\backslash mathbf\{A\}$가 행렬이고 $c$가 스칼라라면, 행렬 $c\backslash mathbf\{A\}$와 $\backslash mathbf\{A\}c$는 $\backslash mathbf\{A\}$의 모든 성분에 $c$를 왼쪽 또는 오른쪽에서 곱하여 얻어진다. 스칼라가 교환 법칙을 만족한다면, $c\backslash mathbf\{A\}\; =\; \backslash mathbf\{A\}c$이다.

만약 곱 $\backslash mathbf\{AB\}$가 정의된다면 (즉, $\backslash mathbf\{A\}$의 열의 개수가 $\backslash mathbf\{B\}$의 행의 개수와 같다면), 다음이 성립한다.
:$c(\backslash mathbf\{AB\})\; =\; (c\; \backslash mathbf\{A\})\backslash mathbf\{B\}$ 그리고 $(\backslash mathbf\{A\}\; \backslash mathbf\{B\})c=\backslash mathbf\{A\}(\backslash mathbf\{B\}c).$
만약 스칼라가 교환 법칙을 만족한다면, 네 행렬은 모두 같다.

이러한 성질은 스칼라 곱의 쌍선형성에서 비롯된다.
:$c\; \backslash left(\backslash sum\_k\; a\_\{ik\}b\_\{kj\}\backslash right)\; =\; \backslash sum\_k\; (c\; a\_\{ik\}\; )\; b\_\{kj\}$
:$\backslash left(\backslash sum\_k\; a\_\{ik\}b\_\{kj\}\backslash right)\; c\; =\; \backslash sum\_k\; a\_\{ik\}\; (\; b\_\{kj\}c).$

행렬의 다른 유형의 곱셈은 다음과 같다.

* 프로베니우스 내적: 벡터로 간주되는 행렬의 내적, 또는 동일하게는 아다마르 곱의 성분의 합
* 아다마르 곱: 동일한 크기의 두 행렬의 곱으로, 동일한 크기의 행렬이 생성되며, 이는 항목별 곱이다.
* 크로네커 곱 또는 텐서 곱: 크기에 제한 없이 정의되는 곱셈이다.
* 카트리-라오 곱 및 페이스 분할 곱
* 외적: 두 열 행렬의 쌍대곱 또는 텐서 곱이라고도 하며, $\backslash mathbf\{a\}\backslash mathbf\{b\}^\backslash mathsf\{T\}$이다.
* 스칼라 곱Scalar multiplication^영어: 행렬에 부수되는 가장 단순한 형태의 곱셈으로 크로네커 곱의 특별한 경우이다.

행렬 $\backslash mathbf\{A\}$의 스칼라 $\backslash lambda$에 의한 왼쪽 스칼라 곱(left scalar multiplication^en-short)은,
: $\backslash lambda\; A\; =\; (\backslash lambda\; a\_\{ij\})$
로 주어지는 $\backslash mathbf\{A\}$와 같은 크기의 행렬 $\backslash lambda\backslash mathbf\{A\}$가 된다. 즉,
: $\backslash lambda\; A\; =\; \backslash lambda\; \backslash begin\{bmatrix\}$
a_{11} & a_{12} & \cdots & a_{1m} \\
a_{21} & a_{22} & \cdots & a_{2m} \\
\vdots & \vdots & \ddots & \vdots \\
a_{n1} & a_{n2} & \cdots & a_{nm}
\end{bmatrix} = \begin{bmatrix}
\lambda a_{11} & \lambda a_{12} & \cdots & \lambda a_{1m} \\
\lambda a_{21} & \lambda a_{22} & \cdots & \lambda a_{2m} \\
\vdots & \vdots & \ddots & \vdots \\
\lambda a_{n1} & \lambda a_{n2} & \cdots & \lambda a_{nm}
\end{bmatrix}\

마찬가지로, 행렬 $\backslash mathbf\{A\}$의 스칼라 $\backslash lambda$에 의한 오른쪽 스칼라 곱(right scalar multiplication^en-short)은
:$A\backslash lambda\; =\; \backslash begin\{bmatrix\}$
a_{11} & a_{12} & \cdots & a_{1m} \\
a_{21} & a_{22} & \cdots & a_{2m} \\
\vdots & \vdots & \ddots & \vdots \\
a_{n1} & a_{n2} & \cdots & a_{nm}
\end{bmatrix}\lambda = \begin{bmatrix}
a_{11} \lambda & a_{12} \lambda & \cdots & a_{1m} \lambda \\
a_{21} \lambda & a_{22} \lambda & \cdots & a_{2m} \lambda \\
\vdots & \vdots & \ddots & \vdots \\
a_{n1} \lambda & a_{n2} \lambda & \cdots & a_{nm} \lambda
\end{bmatrix}
로 정의된다.

기초가 되는 환이 (예를 들어 실수 또는 복소수체와 같은) 가환환이라면, 왼쪽 및 오른쪽 스칼라 곱의 개념은 일치하여 단순히 스칼라 곱이라고 불린다.

같은 크기의 두 행렬에 대해, 아다마르 곱(Hadamard product^en-short), 원소별 곱(element-wise product^en-short), 점별 곱(pointwise product^en-short), 성분별 곱(entrywise product^en-short) 또는 슈어 곱(Schur product^en-short)이라고 불리는 곱을 정의할 수 있다。같은 크기의 두 행렬 $\backslash mathbf\{A\}$, $\backslash mathbf\{B\}$의 아다마르 곱 $\backslash mathbf\{A\}\; \backslash circ\; \backslash mathbf\{B\}$는 원래와 같은 크기의 행렬로, 그 $(i,\; j)$-성분은 $\backslash mathbf\{A\}$의 $(i,\; j)$-성분과 $\backslash mathbf\{B\}$의 $(i,\; j)$-성분의 곱으로 주어진다. 즉,
: $A\; \backslash circ\; B\; =\; (a\_\{ij\}b\_\{ij\})$
전부 쓰면,

:
a_{21} & a_{22} & \cdots & a_{2m} \\
\vdots & \vdots & \ddots & \vdots \\
a_{n1} & a_{n2} & \cdots & a_{nm}
\end{bmatrix}\circ\begin{bmatrix}
b_{11} & b_{12} & \cdots & b_{1m} \\
b_{21} & b_{22} & \cdots & b_{2m} \\
\vdots & \vdots & \ddots & \vdots \\
b_{n1} & b_{n2} & \cdots & b_{nm}
\end{bmatrix} =\begin{bmatrix}
a_{11}b_{11} & a_{12}b_{12} & \cdots & a_{1m}b_{1m} \\
a_{21}b_{21} & a_{22}b_{22} & \cdots & a_{2m}b_{2m} \\
\vdots & \vdots & \ddots & \vdots \\
a_{n1}b_{n1} & a_{n2}b_{n2} & \cdots & a_{nm}b_{nm}
\end{bmatrix}\

이 연산은 통상적인 수의 곱을 일제히 행하는 것에 불과하다. 따라서 아다마르 곱은 교환적이며, 결합적이며, 성분별 합에 대해 분배 법칙이 성립한다. 이것은 또한 크로네커 곱의 주 소행렬이기도 하다.
프로베니우스 내적(Frobenius inner product^en-short)은 행렬을 단순히 벡터로 간주하여 성분별로 계산한 내적으로, $A:B$ 등으로 표기하기도 한다. 이는 아다마르 곱의 성분 합과 같으며, 구체적으로는
: $A\; :\; B\; =\; \backslash sum\_\{i,j\}\; a\_\{ij\}\; b\_\{ij\}\; =\; \backslash operatorname\{vec\}(\{\}^t\backslash !\; A)\; \backslash operatorname\{vec\}(B)\; =\; \backslash operatorname\{tr\}(\{\}^t\backslash !\; A\; B)\; =\; \backslash operatorname\{tr\}(A\backslash ,\{\}^t\backslash !B)$
와 같다. 단, "$\backslash operatorname\{tr\}$"는 행렬의 대각합이며, "$\backslash operatorname\{vec\}$"는 행렬 일렬화이다. 이 내적으로부터 프로베니우스 노름이 유도된다.

두 행렬 $\backslash mathbf\{A\}$, $\backslash mathbf\{B\}$의 크기가 각각 $m\; \backslash times\; n$, $p\; \backslash times\; q$일 때, 이들이 어떤 크기이든 (크기에 관한 제약 조건 없이) 이 두 행렬의 크로네커 곱(Kronecker product^en-short)은
:$A\; \backslash otimes\; B\; =\; \backslash begin\{bmatrix\}$
a_{11}B & a_{12}B & \cdots & a_{1n}B \\
a_{21}B & a_{22}B & \cdots & a_{2n}B \\
\vdots & \vdots & \ddots & \vdots \\
a_{m1}B & a_{m2}B & \cdots & a_{mn}B
\end{bmatrix}
로 주어지는 크기 $mp\; \backslash times\; nq$의 행렬이다。이는 더 일반적인 텐서 곱을 행렬에 적용한 것이다.

7. 계산 복잡도

일반적인 행렬 곱셈 알고리즘은 두 개의 정사각 행렬의 곱을 계산하기 위해 $n^3$번의 곱셈과 $(n-1)n^2$번의 스칼라 덧셈을 필요로 한다. 따라서 해당 알고리즘의 계산 복잡도는 스칼라 연산이 상수 시간 안에 완료되는 계산 모델에서 $O(n^3)$이다.

1969년 볼커 슈트라센이 제시한 슈트라센 알고리즘은 이보다 더 빠른 $O( n^{\log_{2}7}) \approx O(n^{2.8074})$의 복잡도를 가진다. 슈트라센 알고리즘은 성능을 더욱 향상시키기 위해 병렬화될 수 있다. 현재 검증된 최고의 행렬 곱셈 알고리즘은 버지니아 바실레브스카 윌리엄스, 옌잔 쉬, 지쉬안 쉬, 렌페이 저우가 개발한 알고리즘으로, 복잡도는 $O(n^{2.371552})$이다.

행렬 곱셈의 계산 복잡도는 수치 선형대수와 이론 컴퓨터 과학에서 중요한 연구 주제이다. 행렬 곱셈은 많은 알고리즘의 기초를 형성하며, 행렬에 대한 많은 연산이 행렬 곱셈과 동일한 복잡도를 가지기 때문이다.