행렬 곱셈

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 표기
3. 정의
4. 성질
- 4.1. 정사각 행렬
5. 응용
6. 기타 곱셈
7. 계산 복잡도
참조

1. 개요

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

더 읽어볼만한 페이지

곱셈 - 구구단
구구단은 곱셈을 간편하게 계산하도록 곱셈 결과를 표로 정리한 것이며, 1단부터 9단까지 외우는 곱셈 구구가 일반적이고, 덧셈, 뺄셈, 나눗셈 구구 등 다양한 형태가 존재하며, 수학적 개념 이해의 기초가 되고 실생활에도 응용된다.
곱셈 - 네이피어의 뼈
네이피어의 뼈는 존 네이피어가 1617년에 발명한 계산 도구로, 곱셈을 덧셈으로 변환하여 계산을 간편하게 하고 나눗셈과 제곱근 계산에도 활용되며, 계산 기반과 막대 세트로 구성되어 막대에 표시된 숫자를 이용하여 복잡한 곱셈을 단순화한다.
행렬론 - 행렬식
행렬식은 정사각 행렬에 대해 정의되는 값으로, 선형 방정식의 해를 구하고 선형 독립성을 확인하며 기저의 방향과 부피를 계산하는 데 사용되며, 가우스 소거법 등의 계산 기법과 가역성 판단, 고유값 연관성 등의 성질을 갖는다.
행렬론 - 행렬 분해
행렬 분해는 주어진 행렬을 특정 성질을 갖는 여러 행렬의 곱으로 표현하는 방법으로, 수치 해석에서 행렬 알고리즘 구현 및 선형 연립 방정식 해를 구하거나 행렬 특성 분석에 활용되며 LU 분해, QR 분해, 특잇값 분해 등이 있다.
수치선형대수학 - 가우스 소거법
가우스 소거법은 연립 일차 방정식의 해를 구하기 위해 행렬을 사다리꼴로 변환하는 알고리즘이며, 기본 행 연산을 통해 전진 소거와 후퇴 대입 단계를 거쳐 해를 계산하고, 행렬식 계산 등 다양한 분야에 응용된다.
수치선형대수학 - LINPACK
LINPACK은 부동소수점 연산 성능을 평가하는 벤치마크 프로그램이자 FORTRAN 라이브러리로, 슈퍼컴퓨터 성능 측정 기준으로 사용되는 HPLinpack 벤치마크의 기반이 되었으며, TOP500 목록에서 고성능 컴퓨터 순위를 결정하는 데 기여한다.

행렬 곱셈
개요
분야	선형대수학
정의	행렬의 곱셈은 첫 번째 행렬의 행과 두 번째 행렬의 열 간의 내적으로 정의된다.
표기법	AB
정의
행렬 곱셈	행렬 A와 행렬 B의 곱 AB
조건	A의 열의 수가 B의 행의 수와 같아야 함
결과	곱셈의 결과로 생성되는 행렬
크기	A가 n × m 행렬이고 B가 m × p 행렬이면, AB는 n × p 행렬이 됨.
예시
계산	각 요소는 A의 해당 행과 B의 해당 열의 요소별 곱의 합으로 계산됨.
성질
결합 법칙	(AB)C = A(BC)
분배 법칙	A((B + C) = AB + AC, (A + B)C = AC + BC'
스칼라 곱셈	(kA)B = A(kB) = k(AB) 여기서 k는 스칼라
항등 행렬	AI = A = IA 여기서 I는 항등 행렬
전치	(AB)^T = B^TA^T
복소수 켤레	(AB)^* = B^A^
수반 행렬	(AB)^† = B^†A^†
주의사항
교환 법칙	일반적으로 AB ≠ BA (교환 법칙 성립 안 함)
가역성	A와 B가 정사각 행렬이고 가역적이면, (AB)^-1 = B^-1A^-1
관련 개념
선형 변환	행렬 곱셈은 선형 변환의 합성을 나타냄
행렬식	정사각 행렬의 행렬식은 곱셈에 대해 곱셈적임: det(AB) = det(A)det(B)
고윳값 및 고유 벡터	행렬의 고윳값과 고유 벡터는 행렬 곱셈과 관련됨
역사
발명	자크 필리프 마리 비네가 1812년에 발명

2. 표기

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

3. 정의

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

: $\mathbf{A}=\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 행렬로 정의된다. 이때 곱셈 기호는 따로 쓰지 않는다.^[34]^[35]^[36]^[37]

: $\mathbf{C}=\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} +\cdots + a_{in}b_{nj}= \sum_{k=1}^n a_{ik}b_{kj},$

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

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

: $\mathbf{C}=\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}$

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

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

두 행렬 '''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}}

오른쪽 그림에서 원으로 표시된 교차점의 값은 다음과 같다.

\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=\sum_{j=1}^n a_{ij}x_j.

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

:

y_k=\sum_{j=1}^n x_j a_{jk}.

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

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

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

:

A=\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},\quadB=\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} = \sum_{k=1}^m a_{ik}b_{kj}

로 주어지는 n × p 행렬

:

AB =\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}

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

4. 성질

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

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

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

4. 1. 정사각 행렬

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

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

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

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

: $\begin{bmatrix} x' \\ y' \end{bmatrix} = \begin{bmatrix} \cos \alpha & - \sin \alpha \\ \sin \alpha & \cos \alpha \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix}$

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

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

: $\begin{bmatrix} \cos \beta & - \sin \beta \\ \sin \beta & \cos \beta \end{bmatrix}\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}$

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

연립 일차 방정식은 다음과 같은 행렬 방정식 형태로 나타낼 수 있다.^[23]^[24]^[25]^[26]

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

여기서,

A는 계수 행렬
x는 미지수 벡터
b는 상수 벡터

선형 사상 A는 행렬

:

\mathbf{A}=\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},

로 정의되며 열 벡터

\mathbf x

를 행렬 곱

:

\mathbf y = \mathbf {Ax}.

에 사상한다.

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

생산 흐름 그래프에서 기본 상품 $b_4$ 에서 최종 제품 $f_1$ 까지의 모든 경로를 고려하여 행렬 $\mathbf{AB}$ 의 왼쪽 아래 항목을 계산한다.

가상의 공장에서 4가지 종류의 기본 상품

b_1, b_2, b_3, b_4

를 사용하여 3가지 종류의 중간재

m_1, m_2, m_3

을 생산하고, 이 중간재는 다시 3가지 종류의 최종 제품

f_1, f_2, f_3

을 생산하는 경우를 가정할 수 있다. 행렬

:

\mathbf{A} = \begin{pmatrix} 1 & 0 & 1 \\   2 & 1 & 1 \\   0 & 1 & 1 \\   1 & 1 & 2 \\   \end{pmatrix}

와

\mathbf{B} = \begin{pmatrix} 1 & 2 & 1 \\   2 & 3 & 1 \\   4 & 2 & 2 \\   \end{pmatrix}

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

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

:

\mathbf{AB} = \begin{pmatrix} 5 & 4 & 3 \\   8 & 9 & 5 \\\   6 & 5 & 3 \\   11 & 9 & 6 \\   \end{pmatrix}

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

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

6. 기타 곱셈

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

만약 곱 $\mathbf{AB}$ 가 정의된다면 (즉, $\mathbf{A}$ 의 열의 개수가 $\mathbf{B}$ 의 행의 개수와 같다면), 다음이 성립한다.

: $c(\mathbf{AB}) = (c \mathbf{A})\mathbf{B}$ 그리고 $(\mathbf{A} \mathbf{B})c=\mathbf{A}(\mathbf{B}c).$

만약 스칼라가 교환 법칙을 만족한다면, 네 행렬은 모두 같다.

이러한 성질은 스칼라 곱의 쌍선형성에서 비롯된다.

: $c \left(\sum_k a_{ik}b_{kj}\right) = \sum_k (c a_{ik} ) b_{kj}$

: $\left(\sum_k a_{ik}b_{kj}\right) c = \sum_k a_{ik} ( b_{kj}c).$

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

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

행렬

\mathbf{A}

의 스칼라

\lambda

에 의한 '''왼쪽 스칼라 곱'''()은,

:

\lambda A = (\lambda a_{ij})

로 주어지는

\mathbf{A}

와 같은 크기의 행렬

\lambda\mathbf{A}

가 된다. 즉,

:

\lambda A = \lambda \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}\

마찬가지로, 행렬

\mathbf{A}

의 스칼라

\lambda

에 의한 '''오른쪽 스칼라 곱'''()은

:

A\lambda = \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}

로 정의된다.

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

같은 크기의 두 행렬에 대해, '''아다마르 곱'''(), '''원소별 곱'''(), '''점별 곱'''(), '''성분별 곱'''() 또는 '''슈어 곱'''()이라고 불리는 곱을 정의할 수 있다^[27]。같은 크기의 두 행렬

\mathbf{A}

,

\mathbf{B}

의 아다마르 곱

\mathbf{A} \circ \mathbf{B}

는 원래와 같은 크기의 행렬로, 그

(i, j)

-성분은

\mathbf{A}

의

(i, j)

-성분과

\mathbf{B}

의

(i, j)

-성분의 곱으로 주어진다. 즉,

:

A \circ B = (a_{ij}b_{ij})

전부 쓰면,

:

\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}\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}\

이 연산은 통상적인 수의 곱을 일제히 행하는 것에 불과하다. 따라서 아다마르 곱은 교환적이며, 결합적이며, 성분별 합에 대해 분배 법칙이 성립한다. 이것은 또한 크로네커 곱의 주 소행렬이기도 하다.

'''프로베니우스 내적'''()은 행렬을 단순히 벡터로 간주하여 성분별로 계산한 내적으로,

A:B

등으로 표기하기도 한다. 이는 아다마르 곱의 성분 합과 같으며, 구체적으로는

:

A : B = \sum_{i,j} a_{ij} b_{ij} = \operatorname{vec}({}^t\! A) \operatorname{vec}(B) = \operatorname{tr}({}^t\! A B) = \operatorname{tr}(A\,{}^t\!B)

와 같다. 단, "

\operatorname{tr}

"는 행렬의 대각합이며, "

\operatorname{vec}

"는 행렬 일렬화이다. 이 내적으로부터 프로베니우스 노름이 유도된다.

두 행렬

\mathbf{A}

,

\mathbf{B}

의 크기가 각각

m \times n

,

p \times q

일 때, 이들이 어떤 크기이든 (크기에 관한 제약 조건 없이) 이 두 행렬의 '''크로네커 곱'''()은

:

A \otimes B = \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 \times nq

의 행렬이다^[28]。이는 더 일반적인 텐서 곱을 행렬에 적용한 것이다.

7. 계산 복잡도

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

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

행렬 곱셈의 계산 복잡도 $O(n^\omega)$에 대한 지수 $\omega$의 추정치 개선

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

참조

_[1] 웹사이트 Multiplying matrices and vectors https://mathinsight.[...] 2020-09-06
_[2] MacTutor Jacques Philippe Marie Binet
_[3] 서적 Encyclopaedia of Physics VHC publishers 1991
_[4] 서적 McGraw Hill Encyclopaedia of Physics https://archive.org/[...] McGraw-Hill 1994
_[5] 서적 Linear Algebra McGraw Hill (USA) 2009
_[6] 서적 Mathematical methods for physics and engineering https://archive.org/[...] Cambridge University Press 2010
_[7] 서적 Calculus, A Complete Course Addison Wesley 1995
_[8] 서적 Matrix Analysis Cambridge University Press 2013
_[9] 서적 Mathematik für Fachhochschulen – Technik und Informatik "[[Carl Hanser Verlag]]"
_[10] 웹사이트 Matrix Multiplication https://mathworld.wo[...] 2020-09-06
_[11] 서적 Linear Algebra McGraw Hill (USA) 2009
_[12] 서적 Matrix Analysis Cambridge University Press 2013
_[13] 간행물 Computation of Matrix Chain Products, Part I http://www.cs.ust.hk[...]
_[14] 간행물 Computation of Matrix Chain Products, Part II http://www.cs.ust.hk[...]
_[15] 서적 Randomized Algorithms https://books.google[...] Cambridge University Press
_[16] 간행물 Gaussian elimination is not optimal http://www.digizeits[...] 1969-08
_[17] 간행물 Parallelizing Strassen's Method for Matrix Multiplication on Distributed-Memory MIMD Architectures https://core.ac.uk/d[...]
_[18] conference New Bounds for Matrix Multiplication: from Alpha to Omega
_[19] 웹사이트 New Breakthrough Brings Matrix Multiplication Closer to Ideal https://www.quantama[...] 2024-03-09
_[20] 문서 that is, in time {{math|''n''^2+f(n)}}, for some function {{mvar|''f''}} with {{math|''f''(''n'')[[limit of a function|→]]0}} as {{math|''n''→∞}}
_[21] 서적 Encyclopaedia of Physics VHC publishers
_[22] 서적 McGraw Hill Encyclopaedia of Physics
_[23] 서적 Linear Algebra McGraw Hill (USA)
_[24] 서적 Mathematical methods for physics and engineering Cambridge University Press
_[25] 서적 Calculus, A Complete Course Addison Wesley
_[26] 서적 Matrix Analysis Cambridge University Press
_[27] Harvard citations
_[28] citation Matrix Calculus and Kronecker Product with Applications and C++ Programs https://books.google[...] World Scientific
_[29] 웹인용 Comprehensive List of Algebra Symbols https://mathvault.ca[...] 2020-09-06
_[30] 웹인용 Multiplying matrices and vectors https://mathinsight.[...] 2020-09-06
_[31] MacTutor Jacques Philippe Marie Binet
_[32] 서적 Encyclopaedia of Physics VHC publishers 1991
_[33] 서적 McGraw Hill Encyclopaedia of Physics https://archive.org/[...] 1994
_[34] 서적 Linear Algebra https://archive.org/[...] McGraw Hill (USA) 2009
_[35] 서적 Mathematical methods for physics and engineering https://archive.org/[...] Cambridge University Press 2010
_[36] 서적 Calculus, A Complete Course Addison Wesley 1995
_[37] 서적 Matrix Analysis Cambridge University Press 2013
_[38] 웹인용 Comprehensive List of Algebra Symbols https://mathvault.ca[...] 2020-03-25
_[39] 웹인용 Multiplying matrices and vectors https://mathinsight.[...]
_[40] 웹인용 Matrix Multiplication https://mathworld.wo[...]
_[41] 서적 Linear Algebra https://archive.org/[...] McGraw Hill (USA) 2009
_[42] 서적 Matrix Analysis Cambridge University Press 2013
_[43] 문서