エンジニアを目指す浪人のブログ

勉強を進めていて，グラム行列(Gram matrix)というものを知りました．少し調べてみて，Horn and Johnson(2013)にある記述がわかりやすかったので，その定理と証明をメモすることにしました．

問題を設定するため，いくつか準備をします．

張る部分空間，ランクプリンシプル，正定値，半正定値の定義は以下の過去記事にあります．またこれらの過去記事で得た結果(の一部)を本記事で用います．

半正定値行列が正定値であるための必要十分条件は正則であることを証明する - エンジニアを目指す浪人のブログ

以上の設定のもとで，本記事の目的に進みます．

$v_1,\ldots,v_m$ を内積 $\langle \cdot , \cdot \rangle$ の内積空間 $V$ (文献[2]にあります)上のベクトルとします． $\langle \cdot , \cdot \rangle$ は通常の内積 $\langle x,y \rangle = y^* x$ です(性質は文献[3]にあります)． $m \times m$ グラム行列とは以下で定義される行列です．

$\;\;\; G　= \begin{bmatrix} \langle v_1,v_1 \rangle & \langle v_2,v_1 \rangle & \cdots & \langle v_m,v_1 \rangle \\ \langle v_1,v_2 \rangle & \langle v_2,v_2 \rangle & \cdots & \langle v_m,v_2 \rangle \\ \vdots & \vdots & \vdots & \vdots \\ \langle v_1,v_m \rangle & \langle v_2,v_m \rangle & \cdots & \langle v_m,v_m \rangle \end{bmatrix}$

このグラム行列の性質についての定理と証明を以下に示します．Horn and Johnson(2013) Theorem 7.2.10をほぼ引用したものです(和訳し，証明には説明を追加しています)． $\left\| \cdot \right\| = \langle \cdot , \cdot \rangle^{1/2}$ です．

定理 7.2.10. $m \times m$ グラム行列 $G$ について，以下が成り立つ．
(a) $G$ はエルミート行列かつ半正定値である．
(b) $G$ は $v_1,\ldots,v_m$ が線形独立であるとき，またそのときに限り正定値である．
(c) $\mathrm{rank} \ G = \mathrm{dim} \ \mathrm{span} \ \{ v_1,\ldots,v_m \}$

証明.
(a) $G$ はエルミート行列であることを示す．

$\;\;\; G^* = (\bar{G})^T$

$\;\;\;\;\; 　= \begin{bmatrix} \overline{\langle v_1 , v_1 \rangle} & \overline{\langle v_2,v_1 \rangle} & \cdots & \overline{\langle v_m,v_1 \rangle} \\ \overline{\langle v_1,v_2 \rangle} & \overline{\langle v_2,v_2 \rangle} & \cdots & \overline{\langle v_m,v_2 \rangle} \\ \vdots & \vdots & \vdots & \vdots \\ \overline{\langle v_1,v_m \rangle} & \overline{\langle v_2,v_m \rangle} & \cdots & \overline{\langle v_m,v_m \rangle} \end{bmatrix}^T$

$\;\;\;\;\; 　= \begin{bmatrix} \langle v_1,v_1 \rangle & \langle v_1,v_2 \rangle & \cdots & \langle v_1,v_m \rangle \\ \langle v_2,v_1 \rangle & \langle v_2,v_2 \rangle & \cdots & \langle v_2,v_m \rangle \\ \vdots & \vdots & \vdots & \vdots \\ \langle v_m,v_1 \rangle & \langle v_m,v_2 \rangle & \cdots & \langle v_m,v_m \rangle \end{bmatrix}^T$

$\;\;\;\;\; 　= \begin{bmatrix} \langle v_1,v_1 \rangle & \langle v_2,v_1 \rangle & \cdots & \langle v_m,v_1 \rangle \\ \langle v_1,v_2 \rangle & \langle v_2,v_2 \rangle & \cdots & \langle v_m,v_2 \rangle \\ \vdots & \vdots & \vdots & \vdots \\ \langle v_1,v_m \rangle & \langle v_2,v_m \rangle & \cdots & \langle v_m,v_m \rangle \end{bmatrix}$

$\;\;\;\;\; = G$

$G$ は半正定値であることを示す． $x = [ x_1 \ \cdots \ x_m ]^T \in \mathbb{C}^m$ とする．

$\;\;\; x^* G x = \begin{bmatrix} \bar{x}_1 & \cdots & \bar{x}_m \end{bmatrix} \begin{bmatrix} \langle v_1 , v_1 \rangle & \langle v_2,v_1 \rangle & \cdots & \langle v_m,v_1 \rangle \\ \langle v_1,v_2 \rangle & \langle v_2,v_2 \rangle & \cdots & \langle v_m,v_2 \rangle \\ \vdots & \vdots & \vdots & \vdots \\ \langle v_1,v_m \rangle & \langle v_2,v_m \rangle & \cdots & \langle v_m,v_m \rangle \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_m \end{bmatrix}$

$\;\;\;\;\;\;\;\;\;\;\;\; = \begin{bmatrix} \bar{x}_1 & \cdots & \bar{x}_m \end{bmatrix} \begin{bmatrix} \langle v_1,v_1 \rangle x_1 + \langle v_2,v_1 \rangle x_2 + \cdots + \langle v_m,v_1 \rangle x_m \\ \langle v_1,v_2 \rangle x_1 + \langle v_2,v_2 \rangle x_2 + \cdots + \langle v_m,v_2 \rangle x_m \\ \vdots \\ \langle v_1,v_m \rangle x_1 + \langle v_2,v_m \rangle x_2 + \cdots + \langle v_m,v_m \rangle x_m \end{bmatrix}$

$\;\;\;\;\;\;\;\;\;\;\;\; = \begin{bmatrix} \bar{x}_1 & \cdots & \bar{x}_m \end{bmatrix} \begin{bmatrix} \sum_{j=1}^m \langle v_j,v_1 \rangle x_j \\ \sum_{j=1}^m \langle v_j,v_2 \rangle x_j \\ \vdots \\ \sum_{j=1}^m \langle v_j,v_m \rangle x_j \end{bmatrix}$

$\;\;\;\;\;\;\;\;\;\;\;\; = \sum_{i=1}^m \sum_{j=1}^m \langle v_j,v_i \rangle \bar{x}_i x_j$
$\;\;\;\;\;\;\;\;\;\;\;\; = \sum_{i=1}^m \sum_{j=1}^m \langle x_j v_j, x_i v_i \rangle$
$\;\;\;\;\;\;\;\;\;\;\;\; = \left\langle \sum_{j=1}^m x_j v_j, \sum_{i=1}^m x_i v_i \right\rangle$
$\;\;\;\;\;\;\;\;\;\;\;\; = \left\| \sum_{i=1}^m x_i v_i \right\| ^2$
$\;\;\;\;\;\;\;\;\;\;\;\; \ge 0 \;\;\;\;\;\;\;\;\;\;\;\;$ (7.2.11)

(b) 不等式(7.2.11)は $\sum_{i=1}^m x_i v_i = 0$ であるとき，またそのときに限り等式となる． $x \neq 0$ かつ $v_1,\ldots,v_m$ が線形独立であるとき，(7.2.11)は等式にはならないので $G$ は正定値である．逆に， $x \neq 0$ についてつねに $x^* G x \gt 0$ が成り立つ，すなわち $x \neq 0$ についてつねに $\left\| \sum_{i=1}^m x_i v_i \right\| \neq 0$ が成り立つとき， $x \neq 0$ についてつねに $\sum_{i=1}^m x_i v_i \neq 0$ であるので $v_1,\ldots,v_m$ は線形独立である．

(c) $r = \mathrm{rank} \ G$ ， $d = \mathrm{dim} \ \mathrm{span} \ \{ v_1,\ldots,v_m \}$ とおく．(a)より $G$ はエルミート行列なので，冒頭の過去記事(ランクプリンシプル)の事実3.より $G$ はランクプリンシプルであり，正則な $r \times r$ 主小行列をもつ．この主小行列もグラム行列となるので，(a)と冒頭の過去記事(半正定値行列)の事実3.よりこの主小行列は正定値である．したがってこの $r \times r$ 主小行列を構成する $v_i$ は(b)より線形独立であり $r \le d$ がいえる．一方， $\{ v_1,\ldots,v_m \}$ のうちの $d$ 個のベクトル $v_i$ は線形独立でありこれらによる $d \times d$ グラム行列は $G$ の主小行列である．この主小行列は(b)より正定値なので冒頭の過去記事(半正定値行列)の事実1.より正則(したがってフルランク)である．このことは $d \le r$ を意味する．以上より $r = d$ を得る．(証明終わり)