行列の乗法

数学において、行列の対から別の行列を作り出す二項演算としての**行列の乗法**（ぎょうれつのじょうほう）は、実数や複素数などの数が初等的な四則演算でいうところの乗法を持つことと対照的に、そのような「数の配列」の間の乗法として必ずしも一意的な演算を指しうるものではない。

そのような意味では、一般に「行列の乗法」は幾つかの異なる二項演算を総称するものと考えることができる。行列の乗法の持つ重要な特徴には、与えられた行列の行および列の数（行列の型やサイズあるいは次元と呼ばれるもの）が関係して、得られる行列の成分がどのように特定されるかが述べられるということが挙げられる。

例えば、ベクトルの場合と同様に、任意の行列に対してスカラーを掛けるという操作が、その行列の全ての成分に同じ数を掛けるという方法で与えられる。また、の場合と同様に、同じサイズの行列に対して成分ごとの乗法を入れることによって定まる行列の積はアダマール積と呼ばれる。それ以外にも、二つの行列のクロネッカー積は区分行列として得られる。

このようにさまざまな乗法が定義できるという事情の中にあっても、しかし最も重要な行列の乗法は連立一次方程式やベクトルの一次変換に関するもので、応用数学や工学へも広く応用がある。これは通例、**行列の積**（ぎょうれつのせき、）と呼ばれるもので、 が  行列で、 が  行列ならば、それらの行列の積  が  行列として与えられ、その成分は  の各行の  個の成分がそれぞれ順番に  の各列の  個の成分と掛け合わされる形で与えられる（後述）。

この通常の積は可換ではないが、結合的かつ行列の加法に対して分配的である。この行列の積に関する単位元（数において  を掛けることに相当するもの）は単位行列であり、正方行列は逆行列（数における逆数に相当）を持ち得る。行列の積に関して行列式は乗法的である。一次変換や行列群あるいは群の表現などの理論を考える上において行列の積は重要な演算となる。

行列のサイズが大きくなれば、二つあるいはそれ以上の行列の積の計算を定義に従って行うには、非常に膨大な時間が掛かるようになってしまうため、効果的に行列の積を計算できるアルゴリズムが考えられてきた。

## スカラー倍

行列に付随するもっとも単純な形の乗法としてスカラー乗法が挙げられる（これはクロネッカー積の特別の場合になっている）。

行列  のスカラー  による**左スカラー倍**（）は、
:  \lambda A = (\lambda a_{ij})
で与えられる  と同じサイズの行列  となる。つまり、
:  \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}\ 

同様に、行列  のスカラー  による**右スカラー倍**（）は
: 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}
で定義される。

基礎とする環が（例えば実または複素数体のような）可換環ならば、左及び右スカラー倍の概念は一致して、単に**スカラー倍**と呼ばれる。より一般の環では（四元数体のように）非可換であるから左右が異なれば異なる乗法である。

## 通常の行列の積
### 二つの行列の積
まずは二つの行列を掛け合わせることを考える（任意個数への一般化は後述）。

 行列  と  行列  を

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

とするとき、これらの**行列の積** （通例、乗法記号は特に用いずに併置で表す）は、
各  成分  が  の第  行に横に並ぶ成分  と  の第  列に縦に並ぶ成分  を  に亙って足し合わせた和
:  c_{ij} = \sum_{k=1}^m a_{ik}b_{kj}
で与えられる  行列
: 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} 
である。従って、積  が定義されるのは  の列の本数と  の行の本数が一致している場合に限られる（今の場合は  本）。

### 多数の行列の積

二つ以上の個数の行列に対しても、それらの連続する各対に関してサイズの条件が満たされるならば、行列の積を定義することができる。

-個の行列  がそれぞれサイズ  であるとき（ここで  は何れも単に正整数であって、これらの下付き添数はそれぞれどの行列に対応するのかを示す以上の意味は無い）、これら行列の積
:  \prod_{i=1}^n A_i = A_1A_2\cdots A_n = (a_{ij}^{(1)})(a_{ij}^{(2)})\cdots(a_{ij}^{(n)})
は  行列であり、その任意の -成分は
:  \sum_{i_1=1}^{s_1}\sum_{i_2=1}^{s_2}\cdots\sum_{i_{n-1}=1}^{s_{n-1}} a_{i_0,i_1}^{(1)} a_{i_1,i_2}^{(2)} \cdots a_{i_{n-1},i_n}^{(n)}
で与えられる。

### 行列の冪
**正方**行列に関しては、行の本数と列の本数が常に等しいから、通常の数と同様に自分自身を繰り返し掛けることができて、この行列の積の特別の場合としての反復乗積は**行列の[[冪]]**（）を定義することができる。行の本数と列の本数が一致しない一般の**矩形**行列では冪を考えることができない。即ち、 行列  と正整数  に対して
: A^k = \underset{k \text{ times}}{AA\cdots A} 

冪の逆として行列の冪根を考えたり、また冪級数として行列の指数函数やその逆写像として行列の対数函数などを定義したりすることもできる。

## その他の乗法
二つの行列に対して定義されるその他の乗法を以下にいくつか挙げる。実は通常の乗法よりも定義としては単純なものもいくつかある。

### アダマール積

同じサイズの二つの行列に対し、**アダマール積**（）、**要素ごとの積**（）、**点ごとの積**（）、**成分ごとの積**（）あるいは**シューア積**（）などと呼ばれる積を定義することができる。同じサイズの二つの行列 ,  のアダマール積  はもとと同じサイズの行列で、その -成分は  の -成分と  の -成分との積で与えられる。つまり、
:  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 = \sum_{i,j} a_{ij} b_{ij} = \operatorname{vec}({}^t\! A) \operatorname{vec}(B) = \operatorname{tr}({}^t\! A B) = \operatorname{tr}(A\,{}^t\!B)
となる。ただし "" は行列の蹟であり、"" は行列の一列化である。この内積からフロベニウスノルムが誘導される。

### クロネッカー積

二つの行列 ,  のサイズがそれぞれ ,  であるとき、これらがどのようなサイズであったとしても（サイズに関する制約条件なしに）、この二つの行列の**クロネッカー積**（）は
: 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}
で与えられるサイズ  の行列である。これはより一般のテンソル積を行列に対して適用したものになっている。

## 注

## 参考文献

* Henry Cohn, Robert Kleinberg, Balazs Szegedy, and Chris Umans. Group-theoretic Algorithms for Matrix Multiplication. . *Proceedings of the 46th Annual Symposium on Foundations of Computer Science*, 23–25 October 2005, Pittsburgh, PA, IEEE Computer Society, pp.&nbsp;379–388.
* Henry Cohn, Chris Umans. A Group-theoretic Approach to Fast Matrix Multiplication. . *Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science*, 11–14 October 2003, Cambridge, MA, IEEE Computer Society, pp.&nbsp;438–449.
* Coppersmith, D., Winograd S., *Matrix multiplication via arithmetic progressions*, J. Symbolic Comput. 9, p.&nbsp;251-280, 1990.
* 
* Knuth, D.E., *[[The Art of Computer Programming]] Volume 2: Seminumerical Algorithms*. Addison-Wesley Professional; 3 edition (November 14, 1997). ISBN 978-0-201-89684-8. pp.&nbsp;501.
* .
* Ran Raz. On the complexity of matrix product. In Proceedings of the thirty-fourth annual ACM symposium on Theory of computing. ACM Press, 2002. .
* Robinson, Sara, *Toward an Optimal Algorithm for Matrix Multiplication,* SIAM News 38(9), November 2005. PDF
* Strassen, Volker, *Gaussian Elimination is not Optimal*, Numer. Math. 13, p.&nbsp;354-356, 1969.
* 
* Vassilevska Williams, Virginia, *Multiplying matrices faster than Coppersmith-Winograd*, Manuscript, May 2012. PDF

## 関連項目

* 写像の合成
* 関係の合成