ホップの定理(Hopf’s theorem)-行列

ページランクなどの、本質的にマルコフ連鎖に関連するもの(要は、べき乗法)の収束するかしないかの判定法として、ペロン・フロベニウスの定理(Perron-Frobenius theorem)があります。

しかし、この定理が言及するのは、あくまで\(n \rightarrow \infty\)の極限のみであり、収束の速さについては述べません。

べき乗法の収束の速さについて、行列の固有値の絶対値の大きさが本質的に関わって来ることはそこらへんにいくらでも書いてありますし、ちょっと考えればわかることなのでここには書きませんが、以下に示すHopfの定理を用いれば正行列に対し、べき乗法の収束の速さの下限を求めることができます。(べき乗法と固有値にについては、Wikipediaにも書いてあります。)

直観的に言えば、マルコフ過程の遷移行列が疎になる(0成分が多くなる)ほど収束が早いか遅いか判定しづらくなると言うことを述べたのが、以下、ホップの定理(Hopf’s theorem)です。

(\(\kappa \rightarrow \infty\)を考えてみてください。つまり残念ながら、定理の適用可能な行列のクラスは、厳密に正な正方行列に限られます。)

 

ホップの定理(Hopf’s theorem)

正方行列\(M\)の全ての要素が正定値の時、\(M\)の最大固有値\(\lambda_0\)と他の任意の固有値\(\lambda\)は、

\[|\lambda|\leq\frac{\kappa-1}{\kappa+1}\lambda_0 \]

ここで、\(\kappa\)は

\[\displaystyle \kappa=\max_{i,j,k}\frac{M_{ik}}{M_{jk}}\]

 

結構重要な定理だと思うので、日本語でまとめました。ペロン・フロベニウスの定理の証明について知っている方は、以下の定理1,定理4の部分だけ見るだけでもいいと思います。

ちなみに、ホップはもともと、一般に正の積分作用素についてこの定理を証明したようですが、ここでは正行列に注目して考えます。

量子アニーリングの数学的基礎 森田 悟史 西森秀稔 (Mathemathical Foundation of Quantum Annealing)という論文を参考にしています。(日本人が書いた英語の論文を、日本人が見ると言う…)


\(M\)を、厳密に正な(すべての成分が正の)\(m \times m\)行列とする。これを\(M>0\)と書く。

同様に、\(M \geq 0\)は、全ての成分が非負であることを意味する。

ベクトルにも同じ記法を用い、\(\boldsymbol{v} >0\)は\(\boldsymbol{v}\)の全成分が正であることを意味する。

\(M\)の厳密な正定値性は、以下と同値。

\(M\boldsymbol{v}>0 \ \ \ \ if\ \ \ \ \boldsymbol{v} \geq 0,\boldsymbol{v} \neq \boldsymbol{0} \tag{1}\)

 

あらゆる実ベクトル\(\boldsymbol{v}\)と正ベクトル\(\boldsymbol{p}>0\)は、以下を満たす。

\[\displaystyle \min_{i} \frac{v_i}{p_i} \leq \min_i \frac{(M \boldsymbol{v})_i}{(M \boldsymbol{p})_i} \leq \max_i \frac{(M \boldsymbol{v})_i}{(M \boldsymbol{p})_i} \leq \max_i \frac{v_i}{p_i}\]

ならば、

\[(M \boldsymbol{v})_i-( \min _i \frac{v_i}{p_i})(M \boldsymbol{p})_i  =\sum _{j=1}^m M_{ij} [v_j -(\min _i \frac{v_i}{p_i})p_j] \geq 0\]

\(\max\)の方も同様。

 

以下の記号を用いる。

\[\displaystyle \underset{i} {osc} \frac{v_i}{p_i}=\max _i \frac{v_i}{p_i}-\min_i \frac{v_i}{p_i}\]

これは振幅(oscillation)と呼ばれる。

複素ベクトルに対しては、以下の様に定義する。

\[\displaystyle \underset{i}{osc}\ v_i=\sup_{|\eta|=1}\underset{i}{osc}\ Re(\eta v_i)\]

あらゆる複素数\(c\)に対し、

\[\underset{i}{osc}\ v_i=|c|\underset{i}{osc}\ v_i\]

であることがわかる。 

 もし\({osc}_i\ v_i=0\)であるならば、\(v_i\)は\(i\)に依らないことも簡単にわかる。

 

行列\(M\)に対し、以下の仮定を置く。

\[\forall i,j,k\ \ ,\exists \kappa ,\ \frac{M_{ik}}{M_{jk}}\leq  \kappa\]

以下の様に書き換えることもできる。

\[\forall i,j, \boldsymbol{v}\ (\boldsymbol{v}\geq 0,\ \boldsymbol{v} \neq 0),\ \ \frac{(M\boldsymbol{v})_i}{(M\boldsymbol{v})_j}\leq \kappa,\ \  \tag{2} \]


定理1.

もし\(M\)が 条件(1),(2)を満たすならば、あらゆる\(\boldsymbol{p}>0\)と複素ベクトル\(\boldsymbol{v}\)に対し、以下が成り立つ。

 

\[\underset{i}{osc}\  \frac{(M\boldsymbol{v})_i}{(M\boldsymbol{p})_i} \leq \frac{\kappa-1}{\kappa+1} \underset{i}{osc}\  \frac{v_i}{p_i} \tag{3}\]


証)まず、実ベクトル\(\boldsymbol{v}\)について考える。\(i,j,\boldsymbol{p}>0\)を固定し、実数\(X_k\)を以下に定義する。

\[\displaystyle \frac{(M\boldsymbol{v})_i}{(M\boldsymbol{p})_i}-\frac{(M\boldsymbol{v})_j}{(M\boldsymbol{p})_j}=\sum_{k=1}^{m} X_k(v_k)\]

\(X_k=X_k (i,j,\boldsymbol{p})\)の正確な表式は知る必要はない。

\(\boldsymbol{v}=a\boldsymbol{p}\)のとき、上式の左辺は消えるから、

\[\displaystyle \frac{(M\boldsymbol{v})_i}{(M\boldsymbol{p})_i}-\frac{(M\boldsymbol{v})_j}{(M\boldsymbol{p})_j}=\sum_{k=1}^{m} X_k(v_k-ap_k) \tag{4}\]

ここで

\[\displaystyle a=\min_i\frac{v_i}{p_i},b=\max_i \frac{v_i}{p_i}\]

のように選ぶと、

\(v_k-ap_k=(b-a)p_k-(bp_k-v_k)\)であるから、\(v_k-ap_k\)は\(v_k=ap_k\)で最小値\(0,v_k=bp_k\)で最大値\((b-a)p_k\)をとる。

それゆえ(4)式は、

\[\boldsymbol{v}=a\boldsymbol{p}^- +b\boldsymbol{p}^+=a\boldsymbol{p}+(b-a)\boldsymbol{p}^+\]

で最大値をとる。

(論文中(222)式の\(a\boldsymbol{p}^- -b\boldsymbol{p}^+\)は間違い)

ここで、

\[p_i^- =p_i(X_i\leq0),0(X_i>0)\]

\[p_i^+ =0(X_i \leq 0),p_i(X_i>0)\]

のように定義した。

結果、

\[\displaystyle \frac{(M\boldsymbol{v})_i}{(M\boldsymbol{p})_i}-\frac{(M\boldsymbol{v})_j}{(M\boldsymbol{p})_j} \leq \left[\displaystyle \frac{(M\boldsymbol{p}^+)_i}{(M\boldsymbol{p})_i}-\frac{(M\boldsymbol{p}^+)_j}{(M\boldsymbol{p})_j}\right](b-a) \tag{5}\]

が得られる。

仮定より\(M>0\)かつ\(\boldsymbol{p}>0\)であるから、

\[M\boldsymbol{p}^- \geq 0,\ \ M\boldsymbol{p}^+ \geq 0,\ \ M\boldsymbol{p}^- +M\boldsymbol{p}^+ >0\]

さらに、\(\boldsymbol{p}^- =0\)或いは\(\boldsymbol{p}^+ =0\)であるとき、\(\boldsymbol{p}^+=\boldsymbol{p}\)または\(0\)となるから、右辺の括弧内が消えてしまう。

よって、\(M\boldsymbol{p}^->0\)かつ\(M\boldsymbol{p}^+ >0\)であるとして議論を進めてよい。(5)式は、以下の様に書き直せる。

\[\displaystyle \frac{(M\boldsymbol{v})_i}{(M\boldsymbol{p})_i}-\frac{(M\boldsymbol{v})_j}{(M\boldsymbol{p})_j} \leq \frac{1}{1+t}-\frac{1}{1+t’},t\equiv \frac{(M\boldsymbol{p}^-)_i}{(M\boldsymbol{p}^+)_i},t’\equiv \frac{(M\boldsymbol{p}^+)_i}{(M\boldsymbol{p}^-)_i}\]

式(2)より、\(t\)と\(t’\)は\(\kappa^{-1}\)から\(\kappa\)で抑えられるから、\(t’ \leq \kappa^2 t\)であることがわかる。

(論文中,\(t’ \leq \kappa t^2\)は間違い)

\[\frac{(M\boldsymbol{v})_i}{(M\boldsymbol{p})_i}-\frac{(M\boldsymbol{v})_j}{(M\boldsymbol{p})_j} \leq \frac{1}{1+t}-\frac{1}{1+\kappa^2 t}\]

\(t>0\)において、上式の右辺は\(t=\kappa^{-1}\)において最大値\(\frac{\kappa-1}{\kappa+1}\)をとる。

最終的に、以下を得る。

\[\frac{(M\boldsymbol{v})_i}{(M\boldsymbol{p})_i}-\frac{(M\boldsymbol{v})_j}{(M\boldsymbol{p})_j} \leq \frac{\kappa-1}{\kappa+1} \underset{i}{osc}\ \frac{v_i}{p_i}\]

複素ベクトル\(\boldsymbol{v}\)に対しては、\(M\ Re (\eta \boldsymbol{v})=Re (\eta M \boldsymbol{v})\)が成り立つから、\(v_i\)を\(Re(\eta v_i)\)と置き換え、\(|\eta|=1\)の条件の下、両辺のsupをとることで以下を得る。

 \[\underset{i}{osc}\ Re\left(\eta\frac{(M\boldsymbol{v})_i}{(M\boldsymbol{p})_i}\right) \leq \frac{\kappa-1}{\kappa+1} \underset{i}{osc}\ Re\left(\eta\frac{v_i}{p_i}\right)\]


この定理を固有値問題に適用する。

\[M\boldsymbol{v}=\lambda \boldsymbol{v} \tag{6}\]

ペロン・フロベニウスの定理により、非負な正行列\(M\geq 0\)に対し、他のあらゆる固有値\(\lambda\)に関して、\(|\lambda|\leq \lambda_0\)となる。この結果は厳密に正な行列\(M>0\)にも使え、以下の定理を示す。


定理2

式(1),(2)の仮定の下、固有値問題(6)は正の解\(\lambda=\lambda_0>0\),\(\boldsymbol{v}=\boldsymbol{q}>0\)を持ち、さらにどんな\(\boldsymbol{p}(\boldsymbol{p}\geq 0,\boldsymbol{p}\neq 0)\)に対しても、

\[\boldsymbol{q}_n=\frac{M^n\boldsymbol{p}}{(M^n\boldsymbol{p})_k}\]

は\(k\)が固定された下、\(\exists \boldsymbol{q}\)に収束する。


証)

非負で0ではないベクトル\(\boldsymbol{p},\boldsymbol{\bar{p}}\)を考えよう。また、以下の様に定義する。

\[\boldsymbol{p}_{n+1}=M\boldsymbol{p}_n,\ \ \boldsymbol{\bar{p}}_{n+1}=M\boldsymbol{\bar{p}}_n,\ \ \boldsymbol{p}_0=\boldsymbol{p},\ \ \boldsymbol{\bar{p}}_0=\boldsymbol{\bar{p}}\]

仮定(1)から、\(\boldsymbol{p},\boldsymbol{\bar{p}}_n\)はともに、正である。定理1を繰り返し適用することにより、\(n>1\)で以下を得る。

\[\underset{i}{osc}\ \frac{\bar{p}_{n,i}}{p_{n,i}}\leq \left(\frac{\kappa-1}{\kappa+1}\right)^{n-1}\underset{i}{osc}\ \frac{\bar{p}_{1,i}}{p_{1,i}}\ tag{7}\]

 ここで、\(p_{n,i}\equiv(\boldsymbol{p}_n)_i\)という記法を使った。結果として

\[\exists \lambda>0,\forall i,\lim _{n\rightarrow \infty}\frac{\bar{p}_{n,i}}{p_{n,i}}= \lambda \tag{8}\]

がわかる。

ベクトル\(\boldsymbol{p}_n,\boldsymbol{\bar{p}}_n\)を以下の様に規格化する。

\[\boldsymbol{q}_n=\frac{\boldsymbol{p}_n}{p_{n,k}},\ \ \boldsymbol{\bar{q}}_n=\frac{\boldsymbol{\bar{p}}_n}{p_{n,k}}\]

仮定(2)より、

 \[\kappa^{-1}\leq q_{n,i}\leq\kappa,\ \ \kappa^{-1}\leq \bar{q}_{n,i}\leq \kappa \tag{9}\]

が言える。

それゆえ、以下が言える。

\[|\bar{q}_{n,i}-q_{n,i}|=q_{n,i}\frac{p_{n,k}}{\bar{p}_{n,k}} \left|\frac{\bar{p}_{n,i}}{p_{n,i}}-\frac{\bar{p}_{n,k}}{p_{n,k}}\right| \leq \kappa \frac{p_{n,k}}{\bar{p}_{n,k}} \underset{i}{osc}\ \frac{\bar{p}_{n,i}}{p_{n,i}} \tag{10}\]

ここで特に、\(\boldsymbol{\bar{p}}=M\boldsymbol{p}=\boldsymbol{p}_1\)である場合、

\[\boldsymbol{\bar{p}}_n=M\boldsymbol{p}_n=\boldsymbol{p}_{n+1},\ \ \boldsymbol{\bar{q}}_n=\boldsymbol{q}_{n+1}\]

式(7),(8)を用い、(10)により\(\boldsymbol{q}_n\)が\(\boldsymbol{q}\)へと収束することが言える。(9)より、\(\boldsymbol{q}>0\)である。(8)から、

\[\frac{p_{n+1,i}}{p_{n,i}}=\frac{(M\boldsymbol{p}_n)_i}{(\boldsymbol{p}_n)_i}=\frac{(M\boldsymbol{q}_n)_i}{(\boldsymbol{q}_n)_i}\rightarrow \lambda_0\]

 よって、

\[M\boldsymbol{q}=\lambda_0 \boldsymbol{q}\]

となる。定理2は示された。


定理3

同様の仮定の下、固有値問題(6)は\(\lambda=\lambda_0,\boldsymbol{v}=c\boldsymbol{q}\)を除き、正の解をもたない。\(\lambda=\lambda_0\)のとき、(6)は\(\boldsymbol{v}=c\boldsymbol{q}\)を除く解はない。


証)

\(\boldsymbol{v}\geq 0,\boldsymbol{v}\neq 0\)は固有値問題(6)の解とする。仮定(1)より、\(M\boldsymbol{v}>0\)であり、\(\lambda>0\)かつ\(\boldsymbol{v}>0\)なる解を持つ。これを定理2における初期ベクトル\(p\)として用い、定理の最後の部分を適用すると、

\[\frac{M^n\boldsymbol{v}}{(M^n\boldsymbol{v})_k}=\frac{\lambda^n\boldsymbol{v}}{\lambda^n\boldsymbol{v}_k}=\frac{\boldsymbol{v}}{v_k}\]

それゆえ、極限\(\boldsymbol{q}\)は\(\boldsymbol{v}/v_k\)と等しくなり、つまり\(\boldsymbol{v}=c\boldsymbol{q},\lambda=\lambda_0\)である。


定理4

同様の条件の下、固有値問題(6)のあらゆる固有値\(\lambda\neq\lambda_0\)は、以下を満たす。

\[|\lambda|\leq\frac{\kappa-1}{\kappa+1}\lambda_0\]

補足:\((\kappa-1)/(\kappa+1)\)は他の条件がない限り、最良の見積もりである。例えば、

\[M=\begin{pmatrix}\kappa & 1 \\ 1 &\kappa\end{pmatrix}\ \ \kappa>0\]

は固有値\(\lambda_0=\kappa+1,\lambda=\kappa-1\)を持つ。


 証)

次に、定理2の\(\lambda_0>0\)と\(\boldsymbol{q}>0\)なる解と\(M\boldsymbol{v}=\lambda\boldsymbol{v}\)の解を考える。\(\boldsymbol{q},\boldsymbol{v}\)に定理1を適用して、

\[\frac{|\lambda|}{\lambda_0}\underset{i}{osc}\ \frac{v_i}{q_i}=\underset{i}{osc}\ \frac{\lambda v_i}{\lambda_0q_i}=\underset{i}{osc}\ \frac{(M\boldsymbol{v})_i}{(M\boldsymbol{q})_i}\leq\frac{\kappa-1}{\kappa+1}\underset{i}{osc}\ \frac{v_i}{q_i}\]

\(\lambda\neq\lambda_0\)かつ\(\boldsymbol{v}\neq 0\)ならば\(\boldsymbol{v}\)は\(c\boldsymbol{q}\)と等しく成り得ないから、定理を得る。