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

情報系に役立ちそうな応用数理をゆるめにメモします

グラム行列についての定理を証明する

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


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

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

レイリー商についての定理を証明する - エンジニアを目指す浪人のブログ

行列のランクプリンシプルの定義をまとめる - エンジニアを目指す浪人のブログ

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


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

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

{\displaystyle \;\;\; 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をほぼ引用したものです(和訳し,証明には説明を追加しています).{\displaystyle \left\| \cdot \right\| = \langle \cdot , \cdot \rangle^{1/2} } です.

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

証明.
(a) {\displaystyle G } はエルミート行列であることを示す.

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

{\displaystyle \;\;\;\;\;  =  \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 }

{\displaystyle \;\;\;\;\;  =  \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 }

{\displaystyle \;\;\;\;\;  =  \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} }

{\displaystyle \;\;\;\;\; = G }

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

{\displaystyle \;\;\; 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} }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;  = \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}  }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;  = \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}  }

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

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

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


以上,グラム行列についての定理とその証明を示しました.


参考文献
[1] Horn, R.A., and Johnson, C.R. (2013), Matrix Analysis(Second Edition), Cambridge University Press.
[2] Wikipedia Inner product space のページ https://en.wikipedia.org/wiki/Inner_product_space
[3] Wolfram MathWorld Inner Product のページ http://mathworld.wolfram.com/InnerProduct.html