# アルゴリズムイントロダクション 第3版 - Appendix D: 行列 > 前: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Appendix C 数え上げと確率]] | 書籍: [[アルゴリズムイントロダクション 第3版]] ## 要約 付録Dは行列に関する線形代数の基礎用語を定義する参照資料である。§D.1では行列・ベクトルの表記と、対角行列・単位行列・3重対角行列・上三角行列・下三角行列・置換行列・対称行列という特別な正方行列の種類、および行列和・スカラー積・行列積という基本演算の定義と代数的性質(結合律・分配律、単位行列や零行列の役割、積が一般に非可換であること)を示す。§D.2では逆行列、線形従属・線形独立、階数(ランク)、行列式という行列の基礎的性質を定義し、階数と特異性・ヌルベクトルの関係(定理D.1〜D.5)、および正定値行列の定義と $A^TA$ が正定値になるという定理(定理D.6)を示す。第4章のStrassenのアルゴリズム、第25章の全点対最短路の行列積定式化、第28章の行列演算が前提とする用語の多くが、この付録で定義される。(ch.39) ## 主要概念 - **行列 (matrix)**: 数の長方形の配列。$m \times n$ 型行列 $A = (a_{ij})$ の第 $i$ 行第 $j$ 列の要素を $a_{ij}$ と書く。実数値を要素とする $m \times n$ 型行列の集合を $\mathbb{R}^{m \times n}$ と書く。(付録D §D.1) - **転置 (transpose)**: 行列 $A$ の行と列を入れ換えた行列 $A^T$。(付録D §D.1) - **単位行列 (identity matrix)**: 対角に1が並ぶ $n \times n$ 型対角行列 $I_n$。行列積の単位元であり、$I_mA = AI_n = A$ が成立する。(付録D §D.1) - **置換行列 (permutation matrix)**: 各行各列にちょうど1個の1があり、それ以外の要素がすべて0である行列。ベクトルに掛けると要素を置換する効果を持つ。(付録D §D.1) - **逆行列 (inverse)**: $n \times n$ 型行列 $A$ に対し $AA^{-1} = I_n = A^{-1}A$ を満たす行列 $A^{-1}$。存在すれば一意。逆行列を持つ行列を可逆・正則・非特異、持たない行列を非可逆・特異と呼ぶ。(付録D §D.2) - **線形従属・線形独立 (linearly dependent / independent)**: ベクトル $x_1, \dots, x_n$ が、すべてが同時に0ではない係数 $c_1, \dots, c_n$ で $c_1x_1 + \cdots + c_nx_n = 0$ を満たすとき線形従属、そうでないとき線形独立と言う。(付録D §D.2) - **階数・ランク (rank)**: 行列 $A$ の列の階数(列ランク)と行の階数(行ランク)は常に一致し、これを $A$ の階数と呼ぶ。$A = BC$ を満たす $m \times r$ 型 $B$ と $r \times n$ 型 $C$ が存在する最小の $r$ としても定義できる。正方行列で階数が $n$ ならフルランク(非退化)、$m \times n$ 型行列で階数が $n$ なら列非退化(フル列ランク)と言う。(付録D §D.2) - **ヌルベクトル (null vector)**: 行列 $A$ に対し $Ax = 0$ を満たす非零ベクトル $x$。(付録D §D.2) - **行列式 (determinant)**: 小行列(minor)$A_{[ij]}$ を用いて $\det(A) = \sum_{j=1}^{n} (-1)^{1+j} a_{1j}\det(A_{[1j]})$($n > 1$)と再帰的に定義される。(付録D §D.2) - **正定値 (positive-definite)**: $n \times n$ 行列 $A$ が、すべての非零 $n$ ベクトル $x$ に対して $x^TAx > 0$ を満たすこと。(付録D §D.2) ## 主要な定義と定理 - **定理D.1**: 正方行列が非退化であるための必要十分条件は、それが正則であることである。(付録D §D.2) - **定理D.2 / 系D.3**: 行列 $A$ がフル列ランクであるための必要十分条件はヌルベクトルを持たないこと。正方行列 $A$ が特異であるための必要十分条件はヌルベクトルを持つこと。(付録D §D.2) - **定理D.4(行列式の性質)**: ある行・列が零ベクトルなら $\det(A) = 0$、1つの行・列を $\lambda$ 倍すると行列式も $\lambda$ 倍、1つの行を別の行に加えても行列式は不変、$\det(A) = \det(A^T)$、2つの行・列を入れ換えると行列式に $-1$ がかかる。さらに任意の正方行列 $A, B$ に対し $\det(AB) = \det(A)\det(B)$ が成立する。(付録D §D.2) - **定理D.5**: $n \times n$ 型行列 $A$ が特異であるための必要十分条件は $\det(A) = 0$ である。(付録D §D.2) - **定理D.6**: $A$ を任意のフルランクの行列とするとき、$A^TA$ は正定値である。証明は $x^T(A^TA)x = \|Ax\|^2 \geq 0$ とフル列ランク性(定理D.2)から $Ax = 0 \Rightarrow x = 0$ を導く。第28.3節で正定値行列の性質をさらに深く扱う。(付録D §D.2) - **SQUARE-MATRIX-MULTIPLY**(第4.2節、本付録から参照): 2つの $n \times n$ 型行列の積を式(D.2)に従って直接計算する手続き。$n^3$ 回の掛け算と $n^2(n-1)$ 回の足し算を要し、実行時間は $\Theta(n^3)$。(付録D §D.1) ## 関連 - 関連章: [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 4 分割統治]] / [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 25 全点対最短路]] / [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 28 行列演算]] ## 出典 - T. コルメン ほか, 『アルゴリズムイントロダクション 第3版 総合版』, 近代科学社, 2013, 付録D.