行列の積 — 知識ノート

{(A B)}_{i j} = \sum_{k} A_{i k} B_{k j}

なぜこの定義なのか#

写像の合成に一致させるため。

$A : ℝ^{n} \to ℝ^{m}$ 、 $B : ℝ^{p} \to ℝ^{n}$ のとき、 $A (B x)$ を計算すると上の式が出る。つまり行列の積は「 $B$ してから $A$ する」という合成そのもの。

この定義から性質も導かれる。

これは不便な性質ではなく、物理的な内容を持つ。量子力学では観測量が行列（エルミート行列）で表され、 2 つの観測量が可換でないことが同時に確定できないことを意味する。不確定性原理はこの非可換性の帰結。

素朴な計算は $𝒪 (n^{3})$ 。 Strassen のアルゴリズムは $𝒪 (n^{2.807})$ で、理論上はさらに小さい指数も知られているが、定数が大きく実用範囲は限られる。

実際の高速化は、計算量を減らすよりも キャッシュに載せることで達成される（ブロック化）。 BLAS ライブラリの性能差はここから来る。

Gene H. Golub, Charles F. Van Loan. Matrix Computations, 4th ed. Johns Hopkins University Press, 2013. https://www.press.jhu.edu/books/title/10678/matrix-computations
Gilbert Strang. Introduction to Linear Algebra, 6th ed. Wellesley-Cambridge Press, 2023. 講義は MIT OCW 18.06 で公開 https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010/