Matrix multiplication

Original article: w:Matrix multiplication

For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the second matrix. The result matrix has the number of rows of the first and the number of columns of the second matrix.

수학(mathematics), 특히 선형 대수(linear algebra)에서, 행렬 곱셈(matrix multiplication)은 두 행렬에서 행렬(matrix)을 생성하는 이항 연산(binary operation)입니다. 행렬 곱셈에 대해, 첫 번째 행렬에서 열의 개수는 두 번째 행렬에서 행의 개수와 같아야 합니다. 행렬 곱으로 알려진 결과 행렬은 첫 번째 행렬의 행의 개수와 두 번째 행렬의 열의 개수를 가집니다. 행렬 A와 B의 곱은 AB로 표시됩니다.

행렬 곱셈은 1812년 프랑스 수학자 자크 필리프 마리 비네(Jacques Philippe Marie Binet)에 의해 행렬에 의해 표현되는 선형 맵(linear maps)의 합성(composition)을 나타내기 위해 처음으로 설명되었습니다. 행렬 곱셈은 따라서 선형 대수의 기본 도구이고, 수학의 많은 영역뿐만 아니라, 응용 수학, 통계학, 물리학, 경제학, 및 공학에서 수많은 응용을 가지고 있습니다. 행렬 곱을 계산하는 것은 선형 대수의 모든 계산 응용에서 중심 연산입니다.

Notation

이 기사는 다음과 같은 표기법적 관례를 사용합니다: 행렬은 굵은 글씨의 대문자, 예를 들어, A와 같이 표시됩니다; 벡터(vectors)는 굵은 글씨의 소문자, 예를 들어, a와 같이 표시됩니다; 그리고 벡터와 행렬의 엔트리는 기울어진 글씨 (그것들은 필드에서 숫자임), 예를 들어, A와 a와 같이 표시됩니다. 인덱스 표기법(Index notation)은 종종 정의를 표현하기 위해 가장 명확한 방법이고, 문헌에서 표준으로 사용됩니다. 행렬 A의 i 행, j 열의 엔트리는 (A)_ij, A_ij 또는 a_ij로 표시됩니다. 대조적으로, 단일 아래첨자, 예를 들어, A₁, A₂는 행렬 모음에서 행렬 (행렬 엔트리가 아님)을 선택하기 위해 사용됩니다.

Definition

만약 A가 m × n 행렬이고 B가 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}}$

행렬 곱(matrix product) C = AB (곱셈 기호 또는 점 없이 표시됨)는 m × p 행렬로 정의됩니다:

$\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_{ij}=a_{i1}b_{1j}+a_{i2}b_{2j}+\cdots +a_{in}b_{nj}=\sum _{k=1}^{n}a_{ik}b_{kj}.$

즉, 곱의 엔트리 $c_{ij}$는 A의 i번째 행과 B의 j번째 열의 엔트리를 항-별로 곱하고, 이들 n개의 곱을 합함으로써 얻습니다. 다시 말해서, $c_{ij}$는 A의 i번째 행과 B의 j번째 열의 점 곱(dot product)입니다.

그러므로, 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}}$

따라서 곱 AB가 정의되는 것과 A에서 열의 개수가 B에서 행의 개수와 같은 것은 필요충분 조건이며, 이 경우에서 n입니다.

대부분의 시나리오에서, 엔트리는 숫자이지만, 그것들은 덧셈과 곱셈이 정의되고, 결합적(associative)이고, 덧셈이 교환적임을 만족하고, 곱셈이 덧셈에 관해 분배적(distributive)이라는 임의의 종류의 수학적 대상(mathematical objects)일 수 있습니다. 특히, 엔트리는 행렬 자체일 수 있습니다 (블록 행렬 참조).

Illustration

오른쪽 그림은 두 행렬 A와 B의 곱을 도식적으로 보여주며, 곱 행렬에서 각 교차가 A의 행과 B의 열에 어떻게 대응하는지 보여줍니다.

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

오른쪽 그림에서 원으로 표시된 교차에서 값은 다음과 같습니다:

${\begin{aligned}c_{12}&=a_{11}b_{12}+a_{12}b_{22}\\c_{33}&=a_{31}b_{13}+a_{32}b_{23}\end{aligned}}$

Fundamental applications

역사적으로, 행렬 곱셈은 선형 대수에서 계산을 용이하게 하고 명확하게 하기 위해 도입되어 왔습니다. 행렬 곱셈과 선형 대수 사이의 이러한 강력한 관계는 모든 수학뿐만 아니라, 물리학, 화학, 공학, 및 컴퓨터 과학에서 토대적으로 남아 있습니다.

Linear maps

만약 벡터 공간(vector space)이 유한한 기저(basis)를 가지면, 그것의 벡터는 좌표 벡터(coordinate vector)라고 불리는 유한한 스칼라의 수열(sequence)로 각각 고유하게 표현되며, 그것의 원소는 기저에 있는 벡터의 좌표(coordinates)입니다. 이들 좌표 벡터는 원래 벡터 공간에 동형적(isomorphic)인 또 다른 벡터 공간을 형성합니다. 좌표 벡터는 공통적으로 오직 하나의 열을 갖는 행렬인 열 행렬 (열 벡터라고도 함)으로 구성됩니다. 따라서, 열 벡터는 좌표 벡터와 원래 벡터 공간의 벡터를 모두 나타냅니다.

차원 n의 벡터 공간에서 차원 m의 벡터 공간으로의 선형 맵(linear map) A는 다음 열 벡터를

$\mathbf {x} ={\begin{pmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{pmatrix}}$

다음 열 벡터 위로 매핑합니다:

$\mathbf {y} =A(\mathbf {x} )={\begin{pmatrix}a_{11}x_{1}+\cdots +a_{1n}x_{n}\\a_{21}x_{1}+\cdots +a_{2n}x_{n}\\\vdots \\a_{m1}x_{1}+\cdots +a_{mn}x_{n}\end{pmatrix}}.$

선형 맵 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가 차원 m의 이전 벡터 공간에서 차원 p의 벡터 공간으로의 또 다른 선형 맵이면, 그것은 $p\times m$ 행렬 $\mathbf {B}$로 표현됩니다. 간단한 계산은 합성 맵(composite map) $B\circ A$의 행렬이 행렬 곱 $\mathbf {BA}$임을 보여줍니다. 함수 합성을 정의하는 일반적인 형식 $(B\circ A)(\mathbf {x} )=B(A(\mathbf {x} ))$는 여기에서 행렬 곱의 결합성의 특정 사례로 인스턴스화됩니다 (아래 § Associativity 참조):

$(\mathbf {BA} )\mathbf {x} =\mathbf {B} (\mathbf {Ax} )=\mathbf {BAx} .$

Geometric rotations

유클리드 평면에서 데카르트 좌표(Cartesian coordinate) 시스템을 사용하여, 원점(origin) 주위로 각도 $\alpha$만큼 회전(rotation)은 선형 맵입니다. 보다 정확하게, $${\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 \beta \cos \alpha -\sin \beta \sin \alpha &-\cos \beta \sin \alpha -\sin \beta \cos \alpha \\\sin \beta \cos \alpha +\cos \beta \sin \alpha &-\sin \beta \sin \alpha +\cos \beta \cos \alpha \end{bmatrix}}={\begin{bmatrix}\cos(\alpha +\beta )&-\sin(\alpha +\beta )\\\sin(\alpha +\beta )&\cos(\alpha +\beta )\end{bmatrix}},$$ 여기서 적절한 삼각 항등식(trigonometric identities)이 두 번째 상등에 대해 사용됩니다. 즉, 그 합성은 기대한 것처럼 각도 $\alpha +\beta$만큼 회전에 해당합니다.

Resource allocation in economics

The computation of the bottom left entry of $\mathbf {AB}$ corresponds to the consideration of all paths (highlighted) from basic commodity $b_{4}$ to final product $f_{1}$ in the production flow graph.

예제로, 가상의 공장은 4가지 기본 상품(basic commodities) $b_{1},b_{2},b_{3},b_{4}$를 사용하여 3가지 중간재(intermediate goods) $m_{1},m_{2},m_{3}$을 생산하고, 이는 차례로 3가지 최종 제품(final products) $f_{1},f_{2},f_{3}$을 생산하기 위해 사용됩니다. 다음 행렬은

$\mathbf {A} ={\begin{pmatrix}1&0&1\\2&1&1\\0&1&1\\1&1&2\\\end{pmatrix}}$   and   $\mathbf {B} ={\begin{pmatrix}1&2&1\\2&3&1\\4&2&2\\\end{pmatrix}}$

주어진 총양의 중간재에 필요한 기본 상품의 총양과 주어진 총양의 최종 제품에 필요한 중간재의 총양을 각각 제공합니다. 예를 들어, 중간재 $m_{1}$ 한 단위를 생산하기 위해, 기본 상품 $b_{1}$ 한 단위, $b_{2}$의 두 단위, $b_{3}$의 단위 없음, 및 $b_{4}$의 한 단위가 필요하며, $\mathbf {A}$의 첫 번째 열에 해당합니다.

행렬 곱셈을 사용하여, 다음을 계산합니다:

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

이 행렬은 주어진 총양의 최종 상품에 필요한 기본 상품의 총양을 직접 제공합니다. 예를 들어, $\mathbf {AB}$의 바닥 왼쪽 엔트리는 $1\cdot 1+1\cdot 2+2\cdot 4=11$로 계산되며, $b_{4}$의 $11$ 단위는 $f_{1}$의 한 단위를 생성하기 위해 필요됨을 반영합니다. 실제로, $f_{1}$ 단위에 들어가는 $m_{1}$에는 하나의 $b_{4}$ 단위, $m_{2}$ $2$개당 하나씩, 및 $m_{3}$ 단위 4개당 $2$개가 필요합니다, 그림 참조.

생산하기 위해, 예를 들어, 최종 제품 $f_{1}$의 100단위, $f_{2}$의 80단위, 및 $f_{3}$의 60단위, 기본 상품의 필요 총양은 다음과 같이 계산될 수 있습니다:

$(\mathbf {AB} ){\begin{pmatrix}100\\80\\60\\\end{pmatrix}}={\begin{pmatrix}1000\\1820\\1180\\2180\end{pmatrix}},$

즉, $b_{1}$의 $1000$ 단위, $b_{2}$의 $1820$ 단위, $b_{3}$의 $1180$ 단위, $b_{4}$의 $2180$ 단위가 필요합니다. 유사하게, 제품 행렬 $\mathbf {AB}$는 다른 최종-상품 총양 데이터에 필요한 기본 상품 총양을 계산하기 위해 사용될 수 있습니다.

System of linear equations

선형 방정식 시스템(system of linear equations)의 일반 형식은 다음과 같습니다:

${\begin{matrix}a_{11}x_{1}+\cdots +a_{1n}x_{n}=b_{1}\\a_{21}x_{1}+\cdots +a_{2n}x_{n}=b_{2}\\\vdots \\a_{m1}x_{1}+\cdots +a_{mn}x_{n}=b_{m}\end{matrix}}.$

위와 같은 표기법을 사용하여, 그러한 시스템은 단일 행렬 방정식(equation)과 동등합니다:

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

Dot product, bilinear form and sesquilinear form

두 열 벡터의 점 곱(dot product)은 행렬 곱의 고유 엔트리입니다:

$\mathbf {x} ^{\mathsf {T}}\mathbf {y} ,$

여기서 $\mathbf {x} ^{\mathsf {T}}$는 $\mathbf {x}$를 전치함으로써 얻은 행 벡터(row vector)입니다. (이를테면, 1×1 행렬은 고유 엔트리로 식별됩니다.)

보다 일반적으로, 유한 차원의 벡터 공간에 걸쳐 쌍선형 형식(bilinear form)은 행렬 곱으로 표현될 수 있습니다:

$\mathbf {x} ^{\mathsf {T}}\mathbf {Ay} ,$

그리고 임의의 반쌍선형 형식(sesquilinear form)은 다음과 같이 표현될 수 있습니다:

$\mathbf {x} ^{\dagger }\mathbf {Ay} ,$

여기서 $\mathbf {x} ^{\dagger }$는 $\mathbf {x}$의 켤레 전치(conjugate transpose)를 나타냅니다 (전치의 켤레, 또는 동등하게 켤레의 전치).

General properties

행렬 곱셈(multiplication)은 보통의 곱셈과 일부 속성을 공유합니다. 어쨌든, 행렬 곱셈은 만약 첫 번째 인수의 열의 개수가 두 번째 인수의 행의 개수와 다르면 정의되지 않고, 인수의 순서를 변경한 후에도 곱이 정의된 상태로 유지되더라도, 비-교환적(non-commutative)입니다.

Non-commutativity

연산은 만약 곱 $\mathbf {A} \mathbf {B}$가 정의됨을 만족하는 두 원소 A와 B가 주어지면, $\mathbf {B} \mathbf {A}$도 정의되고 $\mathbf {A} \mathbf {B} =\mathbf {B} \mathbf {A}$이면 교환적(commutative)입니다.

만약 A와 B가 각각 크기 $m\times n$과 $m\times n$의 행렬이면, $\mathbf {A} \mathbf {B}$는 $n=p$이면 정의되고, $\mathbf {B} \mathbf {A}$는 $m=q$이면 정의됩니다. 그러므로, 곱 중 하나가 정의되면, 다른 곱은 정의될 필요는 없습니다. 만약 $m=q\neq n=p$이면, 두 곱이 정의되지만, 다른 크기를 가집니다; 따라서 그것들은 같을 수 없습니다. 만약 오직 $m=q=n=p$이면, 즉, A와 B가 오직 같은 크기의 정사각 행렬이면, 두 곱이 정의되고 같은 크기입니다. 심지어 이 경우에도, 일반적으로 다음을 가집니다:

$\mathbf {A} \mathbf {B} \neq \mathbf {B} \mathbf {A} .$

예를 들어

${\begin{pmatrix}0&1\\0&0\end{pmatrix}}{\begin{pmatrix}0&0\\1&0\end{pmatrix}}={\begin{pmatrix}1&0\\0&0\end{pmatrix}},$

그러나

${\begin{pmatrix}0&0\\1&0\end{pmatrix}}{\begin{pmatrix}0&1\\0&0\end{pmatrix}}={\begin{pmatrix}0&0\\0&1\end{pmatrix}}.$

이 예제는 A가 필드(field) F에 엔트리를 갖는 $n\times n$ 행렬이면, F에서 엔트리를 갖는 모든 각 $n\times n$ 행렬 B에 대해 $\mathbf {A} \mathbf {B} =\mathbf {B} \mathbf {A}$인 것과 $\mathbf {A} =c\,\mathbf {I}$인 것은 필요충분 조건임을 보여주기 위해 확장될 수 있으며, 여기서 $c\in F$이고, I는 $n\times n$ 항등 행렬(identity matrix)입니다. 만약 필드 대신 엔트리가 링(ring)에 속한다고 가정되면, c가 링의 중심(center)에 속한다는 조건을 추가해야 합니다.

교환성이 발생하는 하나의 특별한 경우는 D와 E가 두 개의 (정사각) 대각 행렬 (같은 크기)일 때입니다; 그런-다음 DE = ED입니다. 다시 말하지만, 행렬이 필드가 아닌 일반 링에 걸쳐 있으면, 각각에서 해당 엔트리도 이를 유지하기 위해 서로 교환해야 합니다.

Distributivity

행렬 곱은 행렬 덧셈(matrix addition)에 관해 분배적(distributive)입니다. 즉, A, B, C, D가 각각 크기 m × n, n × p, n × p, 및 p × q의 행렬이면, 다음과 같은 왼쪽 분배성을 가집니다:

$\mathbf {A} (\mathbf {B} +\mathbf {C} )=\mathbf {AB} +\mathbf {AC} ,$

그리고 오른쪽 분배성을 가집니다:

$(\mathbf {B} +\mathbf {C} )\mathbf {D} =\mathbf {BD} +\mathbf {CD} .$

이것은 다음에 의한 계수에 대해 분배성으로부터 결과입니다:

$\sum _{k}a_{ik}(b_{kj}+c_{kj})=\sum _{k}a_{ik}b_{kj}+\sum _{k}a_{ik}c_{kj}$

$\sum _{k}(b_{ik}+c_{ik})d_{kj}=\sum _{k}b_{ik}d_{kj}+\sum _{k}c_{ik}d_{kj}.$

Product with a scalar

만약 A가 행렬이고 c가 스칼라이면, 행렬 $c\mathbf {A}$와 $\mathbf {A} c$는 A의 모든 엔트리에 c를 왼쪽 또는 오른쪽으로 곱함으로써 얻습니다. 만약 스칼라가 교환 속성(commutative property)을 가지면, $c\mathbf {A} =\mathbf {A} c$입니다.

만약 곱 $\mathbf {AB}$가 정의되면 (즉, A의 열의 개수가 B의 행의 개수와 같으면), 다음과 같습니다:

$c(\mathbf {AB} )=(c\mathbf {A} )\mathbf {B}$ and $(\mathbf {A} \mathbf {B} )c=\mathbf {A} (\mathbf {B} c).$

만약 스칼라가 교환 속성을 가지면, 모든 4개의 행렬이 같습니다. 보다 일반적으로, 모든 4개는 만약 c가 행렬의 엔트리를 포함하는 링(ring)의 중심(center)에 속하면 같은데, 왜냐하면 이 경우에서, 모든 행렬 X에 대해 cX = Xc이기 때문입니다.

이들 속성은 스칼라의 곱의 쌍선형성(bilinearity)으로부터 결과입니다:

$c\left(\sum _{k}a_{ik}b_{kj}\right)=\sum _{k}(ca_{ik})b_{kj}$

$\left(\sum _{k}a_{ik}b_{kj}\right)c=\sum _{k}a_{ik}(b_{kj}c).$

Transpose

만약 스칼라가 교환 속성(commutative property)을 가지면, 행렬의 곱의 전치(transpose)는, 역순으로, 인수의 전치의 곱입니다. 즉,

$(\mathbf {AB} )^{\mathsf {T}}=\mathbf {B} ^{\mathsf {T}}\mathbf {A} ^{\mathsf {T}}$

여기서 ^T 는 전치, 즉 행과 열의 교환을 나타냅니다.

이 항등식은 비교환 엔트리에 대해 유지되지 않는데, 왜냐하면 A와 B의 엔트리 사이의 순서는 행렬 곱의 정의를 확장할 때 역전되기 때문입니다.

Complex conjugate

만약 A와 B가 복소(complex) 엔트리이면, 다음과 같습니다:

$(\mathbf {AB} )^{*}=\mathbf {A} ^{*}\mathbf {B} ^{*}$

여기서 ^* 는 행렬의 엔트리-별 복소 켤레(complex conjugate)를 나타냅니다.

이것은 합의 켤레는 피합수의 켤레의 합이고 곱의 켤레는 인수의 켤레의 곱이라는 사실을 행렬 곱의 정의에 적용한 결과입니다.

전치는 엔트리의 인덱스에 동작하고, 반면 켤레는 엔트리 자체에 독립적으로 동작합니다. 결과적으로, A와 B가 복소수 엔트리를 가지면, 다음을 가집니다:

$(\mathbf {AB} )^{\dagger }=\mathbf {B} ^{\dagger }\mathbf {A} ^{\dagger },$

여기서 ^† 는 켤레 전치(conjugate transpose) (전치의 켤레, 또는 동등하게 켤레의 전치)를 나타냅니다.

Associativity

3개의 행렬 A, B, 및 C가 주어졌을 때, 곱 (AB)C와 A(BC)가 정의되는 것과 A의 열의 개수가 B의 행의 개수와 같고 B의 열의 개수가 C의 행의 개수와 같은 것은 필요충분 조건입니다 (특히, 곱 중 하나가 정의되면, 다른 것도 정의됩니다). 이 경우에서, 결합 속성(associative property)을 가집니다:

$(\mathbf {AB} )\mathbf {C} =\mathbf {A} (\mathbf {BC} ).$

임의의 결합 연산에 관해서, 괄호를 생략하고, 위 곱을 ABC로 쓸 수 있습니다.

이것은 차원이 일치한다는 조건으로 하여 자연스럽게 임의의 행렬의 개수의 곱으로 확장됩니다. 즉, A₁, A₂, ..., A_n가 A_i의 열의 개수가 i = 1, ..., n – 1에 대해 A_{i + 1}의 행의 개수와 같음을 만족하는 행렬이면, 다음 곱은

$\prod _{i=1}^{n}\mathbf {A} _{i}=\mathbf {A} _{1}\mathbf {A} _{2}\cdots \mathbf {A} _{n}$

행렬의 순서가 고정되게 유지되면 정의되고 곱셈의 순서에 의존하지 않습니다.

이들 속성은 간단하지만 복잡한 합(summation) 조작에 의해 입증될 수 있습니다. 이 결과는 행렬이 선형 맵(linear maps)을 나타낸다는 사실에서도 이어집니다. 그러므로, 행렬의 결합 속성은 단순히 함수 합성(function composition)의 결합 속성의 특정 사례입니다.

Computational complexity depends on parenthezation

행렬의 수열의 곱의 결과는 연산의 순서에 의존하지 않지만 (행렬의 순서가 변경되지 않는다는 조건으로 함), 계산 복잡성(computational complexity)은 이 순서에 따라 극적으로 달라질 수 있습니다.

예를 들어, A, B, 및 C가 각각 크기 10×30, 30×5, 5×60의 행렬이면, (AB)C를 계산하는 것은 10×30×5 + 10×5×60 = 4,500 곱셈이 필요하고, 반면에 A(BC)는 30×5×60 + 10×30×60 = 27,000 곱셈이 필요합니다.

알고리듬은 최상의 곱의 순서를 선택하도록 설계되어 왔으며, 행렬 체인 곱셈을 참조하십시오. 행렬의 개수 n이 증가할 때, 최적의 순서를 선택은 $O(n\log n)$의 복잡도임을 알 수 있습니다.

Application to similarity

임의의 역-가능 행렬(invertible matrix) $\mathbf {P}$는 ($\mathbf {P}$와 같은 크기의 정사각 행렬 위에) 닮음 변환(similarity transformation)을 정의합니다:

$S_{\mathbf {P} }(\mathbf {A} )=\mathbf {P} ^{-1}\mathbf {A} \mathbf {P} .$

닮음 변환은 곱을 곱으로에 매핑합니다. 즉,

$S_{\mathbf {P} }(\mathbf {AB} )=S_{\mathbf {P} }(\mathbf {A} )S_{\mathbf {P} }(\mathbf {B} ).$

사실, 다음을 가집니다:

$\mathbf {P} ^{-1}(\mathbf {AB} )\mathbf {P} =\mathbf {P} ^{-1}\mathbf {A} (\mathbf {P} \mathbf {P} ^{-1})\mathbf {B} \mathbf {P} =(\mathbf {P} ^{-1}\mathbf {A} \mathbf {P} )(\mathbf {P} ^{-1}\mathbf {B} \mathbf {P} ).$

Square matrices

${\mathcal {M}}_{n}(R)$를 실제로 종종 필드(field)인 링(ring) R에서 엔트리를 갖는 n×n 정사각 행렬(square matrices)의 집합을 나타낸다고 표시합니다.

${\mathcal {M}}_{n}(R)$)에서, 곱은 모든 각 행렬의 쌍에 대해 정의됩니다. 이것은 ${\mathcal {M}}_{n}(R)$을 항등 행렬(identity matrix) I를 항등 원소(identity element)로 가지는 링(ring)으로 만듭니다 (항등 행렬은 그것의 대각 엔트리가 1과 같고 모든 다른 엔트리가 0인 것입니다). 이 링은 또한 결합 R-대수(associative R-algebra)입니다.

만약 n > 1이면, 많은 행렬은 곱셈 역(multiplicative inverse)을 가지지 않습니다. 예를 들어, 행 (또는 열)의 모든 엔트리가 0임을 만족하는 행렬은 역을 가지지 않습니다. 만약 그것이 존재하면, 행렬 A의 역은 A⁻¹로 표시되고, 따라서 다음과 같이 확인합니다:

$\mathbf {A} \mathbf {A} ^{-1}=\mathbf {A} ^{-1}\mathbf {A} =\mathbf {I} .$

역을 가지는 행렬은 역가능 행렬(invertible matrix)입니다. 그렇지 않으면, 그것은 특이 행렬(singular matrix)입니다.

행렬의 곱이 역가능인 것과 각 인수가 역가능인 것은 필요충분 조건입니다. 이 경우에서, 다음을 가집니다:

$(\mathbf {A} \mathbf {B} )^{-1}=\mathbf {B} ^{-1}\mathbf {A} ^{-1}.$

R이 교환적(commutative)이고, 특히, 그것이 필드일 때, 곱의 행렬식(determinant)은 행렬식의 곱입니다. 행렬식이 스칼라이고, 스칼라가 교환하기 때문에, 따라서 다음을 가집니다:

$\det(\mathbf {AB} )=\det(\mathbf {BA} )=\det(\mathbf {A} )\det(\mathbf {B} ).$

다른 행렬 불변(invariants)은 곱과 함께 잘 작동하지 않습니다. 그럼에도 불구하고, R이 교환적이면, AB와 BA는 같은 대각합, 같은 특성 다항식(characteristic polynomial), 및 같은 중복도를 갖는 같은 고윳값(eigenvalues)을 가집니다. 어쨌든, 고유벡터(eigenvectors)는 AB ≠ BA이면 일반적으로 다릅니다.

Powers of a matrix

보통의 숫자와 같은 방법으로 정사각 행렬과 자체를 반복적으로 곱함으로써 정사각 행렬에 임의의 비-음의 정수 거듭제곱을 올릴 수 있습니다. 즉,

$\mathbf {A} ^{0}=\mathbf {I} ,$

$\mathbf {A} ^{1}=\mathbf {A} ,$

$\mathbf {A} ^{k}=\underbrace {\mathbf {A} \mathbf {A} \cdots \mathbf {A} } _{k{\text{ times}}}.$

행렬의 k번째 거듭제곱을 계산하는 것은, 만약 그것이 자명한 알고리듬 (반복 곱셈)으로 수행되면 단일 행렬 곱셈의 k – 1배 시간이 필요합니다. 이것은 시간이 많이 소요될 수 있으므로, 일반적으로 2 log₂ k 미만의 행렬 곱셈이 필요하고, 따라서 훨씬 더 효율적인 제곱화에 의한 지수를 사용하는 것을 선호합니다.

거듭제곱에 대한 쉬운 경우는 대각 행렬(diagonal matrix)의 경우입니다. 대각 행렬의 곱은 단순히 대응하는 대각 원소를 함께 곱하는 것이기 때문에, 대각 행렬의 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}}.$

Abstract algebra

행렬 곱의 정의는 엔트리가 반링에 속할 것을 요구하고, 반링의 원소의 곱셈이 교환적(commutative)일 것을 요구하지 않습니다. 많은 응용에서, 행렬 원소는 필드에 속하지만, 비유적 반-링(tropical semiring)은 그래프 최단 경로 문제에 대한 공통적인 선택이기도 합니다. 필드에 걸쳐 행렬의 경우에서도, 곱은 일반적으로 교환적이지 않지만, 그것은 행렬 덧셈(matrix addition)에 걸쳐 결합적(associative)이고 분배적(distributive)입니다. 항등 행렬(identity matrices, 그 엔트리가 주요 대각선 밖에서 영이고 주요 대각선에서 1인 정사각 행렬)은 행렬 곱의 항등 원소(identity elements)입니다. 따라서 링(ring)에 걸쳐 n × n 행렬은 링을 형성하며, 이는 n = 1이고 바닥 링이 교환적인 경우를 제외하고 비교환적입니다.

정사각 행렬은 역 행렬(inverse matrix)이라고 불리는 곱셈의 역(multiplicative inverse)을 가질 수 있습니다. 엔트리가 교환 링(commutative ring) R에 속하는 공통적인 경우에서, 행렬이 역을 가지는 것과 그것의 행렬식(determinant)이 R에서 곱셈의 역을 가지는 것은 필요충분 조건입니다. 정사각 행렬의 곱의 행렬식은 인수 행렬식의 곱입니다. 역을 가지는 n × n 행렬은 행렬 곱셈 아래에서 그룹(group)을 형성하며, 그 부분그룹(subgroups)은 행렬 그룹(matrix groups)이라고 불립니다. 많은 고전적 그룹 (모든 유한 그룹 포함)은 행렬 그룹과 동형적(isomorphic)입니다; 이것이 그룹 표현(group representations)의 이론의 출발 점입니다.

Computational complexity

Main article: Computational complexity of matrix multiplication

For implementation techniques (in particular parallel and distributed algorithms), see Matrix multiplication algorithm.

Improvement of estimates of exponent ω over time for the computational complexity of matrix multiplication $O(n^{\omega })$.

정의에서 나온 행렬 곱셈 알고리듬(algorithm)은, 최악의 경우에서, 두 개의 정사각 n×n 행렬의 곱을 계산하기 위해 스칼라의 $n^{3}$ 곱셈과 $(n-1)n^{2}$ 덧셈이 필요합니다. 따라서 그것의 계산 복잡도(computational complexity)는 스칼라 연산이 일정한 시간을 취하는 계산의 모델(model of computation)에서 $O(n^{3})$입니다.

다소 놀랍게도, 이 복잡성은 $O(n^{\log _{2}7})\approx O(n^{2.8074})$의 복잡도를 갖는 현재 슈트라센의 알고리듬(Strassen's algorithm)이라고 불리는 알고리듬을 제공한 폴카 슈트라센(Volker Strassen)에 의해 1969년에 보여준 것처럼 최적은 아닙니다. 슈트라센의 알고리듬은 성능을 더욱 향상시키기 위해 병렬화될 수 있습니다. 2020년 12월 당시, 최고의 행렬 곱셈 알고리듬은 Josh Alman과 Virginia Vassilevska Williams에 의한 것이고 복잡도 O(n^2.3728596)를 가집니다. 행렬 곱셈이 n^{2 + o(1)} 시간에 수행될 수 있는지 여부는 알려져 있지 않습니다. 행렬을 또 다른 행렬과 곱하기 위해 행렬의 $n^{2}$ 원소를 읽어야 하기 때문에 이것이 최적일 것입니다.

행렬 곱셈이 많은 알고리듬의 기초를 형성하고, 행렬에 대한 많은 연산이 (곱셈 상수까지) 행렬 곱셈과 같은 복잡도를 가지기 때문에, 행렬 곱셈의 계산 복잡도는 수치 선형 대수(numerical linear algebra)와 이론적 컴퓨터 과학(theoretical computer science) 전반에 걸쳐 나타납니다.

Generalizations

다른 유형의 행렬의 곱은 다음을 포함합니다:

• 블록 행렬 곱셈
• Cracovian product, A ∧ B = B^TA으로 정의됩니다.
• 프로베니우스 안의 곱(Frobenius inner product), 벡터로 고려된 행렬의 점 곱(dot product), 또는, 동등하게 아다마르 곱(Hadamard product)의 엔트리의 합.
• 같은 크기의 두 행렬의 아다마르 곱(Hadamard product), 결과적으로 같은 크기의 행렬을 초래하며, 이는 엔트리-별-엔트리 곱입니다.
• 크로네커 곱(Kronecker product) 또는 텐서 곱(tensor product), 이전 것의 임의의 크기의 일반화.
• Khatri-Rao product 및 Face-splitting product
• 밖의 곱(Outer product), 역시 두 열 행렬의 이원적 곱(dyadic product) 또는 텐서 곱(tensor product)이라고 불리며, 이는 $\mathbf {a} \mathbf {b} ^{\mathsf {T}}$입니다.
• 스칼라 곱셈(Scalar multiplication)

See also

• Matrix calculus, for the interaction of matrix multiplication with operations from calculus