サイト訪問者の皆様へ。お願いですから、サイト運営者の下記記事をお読みください。読んで下されば、「日本人の危機」であることが、明確です。


韓国人遺伝子の異常性へ


ウェブページが、訪問される確率=ページランク=定常分布ベクトルですが、同時にペロンベクトルとも言います。(確率ベクトルとも呼ばれる)

ペロン・フロベニウスの定理


一般に、ペロン・フロベニウスの定理は、次の内容とされています。

非負の行列Aが、既約であれば、

①絶対値最大の固有値は、正で、かつ、実数である。(r>0)。
②絶対値最大の固有値は、Aの固有方程式の単純根である。(rは、単純固有値である。)
③絶対値最大の固有値に対応する固有ベクトルの成分は、全て正であるか、又は全て負である。 (注)

(注)
③に関して同定理に関するウェブ上の 英文の解説では、多くの場合、表現上、「全て正である」となっているでしょうが、逆に、「全て負である」も当然成立します。
(基本的には、同じことですが、このウェブサイトの趣旨からして、誤解のないように入れておきました。)
詳しく言えば、[A - λ 1E]という最大固有値に対応する固有ベクトル計算対象行列の右下がりの対角要素は、必ず全て負になります。(そうでないと、[A - λ 1E]の他の要素は、定義上、全て正ですので、固有ベクトルがでないことは、すぐわかるはずです。結果、算出した固有ベクトルは、成分が全て正・負いずれもありえます。

以下、次の線形代数の標準テキストより、引用します。

Carl Dean. Meyer, 「Matrix Analysis and Applied Linear Algebra」 The Society for Industrial and Applied Mathematics, Philadelphia, 2000より。
(ページ数は、Adobe Reader 8による。)
(下線・赤字・は、私が勝手に入れたものであり、原文にはありません。)

線形代数のテキスト入手 →


(P681)
Perron-Frobenius Theorem

非負の行列Aが、既約であれば、
If An×n >0 is irreducible, then each of the following is true.

①絶対値最大の固有値は、正で、かつ、実数である。

* r = ρ (A) ∈ σ (A) and r > 0. (8.3.6) 

(注)r=絶対値最大の固有値=主固有値>0
①σ (A) = {λ1, λ2, . . . , λs}、つまり、λ1>λ2・・・>λs。互いに異なる固有値の集合。P490
②ρ(A)は、絶対値最大の固有値の数の集合。P497
ρ(A) = max|λ| is called the spectral radius of A.
λ∈σ(A)


②絶対値最大の固有値は、Aの固有方程式の単純根である。(rは、単純固有値である。)
* alg multA (r) = 1. (8.3.7)

(注) algebraic multiplicityの略。最大固有値の代数的重複度=1。

③絶対値最大の固有値に対応する固有ベクトルの成分は、全て正である。(又は全て負である。)
*There exists an eigenvector x > 0 such that Ax = rx. (8.3.8)

④ノルム1(L 1ノルム)の正で単一の固有ベクトルをペロンベクトルと呼び、行列Aの固有値にかかわらず、非負の固有ベクトル(=p)は、pとそのスカラー倍しかない。
* The unique vector defined by Ap = rp, p > 0, and ||p|| 1= 1, (8.3.9) is called the Perron vector.
 There are no nonnegative eigenvectors for A except for positive multiples of p, regardless of the eigenvalue
(注)
・L 1ノルムとは、単にベクトルの成分の絶対値の合計のことです。

・Aのノルム1の正の固有ベクトル(=p)は、確率ベクトルと呼ばれる場合もあります。( 英文ウキペディアの同定理の項目ご参照)

同書P674の証明を引用します。

No Other Positive Eigenvectors

There are no nonnegative eigenvectors for An×n > 0 other than the Perron vector p and its positive multiples. (8.2.10)

Proof.
If (λ, y) is an eigenpair for A such that y ≧0, and if x > 0 is the Perron vector for A T, then x Ty > 0 by (8.2.2),
so
ρ (A)X T= X TA  ⇒ ρ (A)X Ty = X TAy = λX Ty ⇒ ρ (A) = λ.
 
(注)
①ρ (A) x T= x TA は、λX=AX  の通常の固有ベクトル定義(結果は、列ベクトル=列ベクトル)を 行ベクトル=行ベクトルになるように記述したもの。ただし、ρ (A)は、λのうちの絶対値最大の固有値のこと。普通に書けばλ 1。要するにλ 1X=AX に他ならない。
②ρ (A)X Ty = X TAy は、単に①の両辺にyを乗じたもの。。
③X TAy = λX Ty は、λX=AX  の通常の固有ベクトル定義を①のように行ベクトル=行ベクトルになるように記述し、その両辺にyを乗じたもの。(結果は、行列=行列)
④以上から、ρ (A) X Ty = λ X Ty なので、 ρ (A) = λ

つまり、 y ≧ 0 を満たす固有ペアは、絶対値最大の固有値との固有ペアしかないこととなります。しかし、ゼロベクトル以外のベクトルを求めるのが、固有ベクトルの定義そのものですので、結果として、Aの固有値にかかわらず、成分が全て正であるAの固有(確率)ベクトル即ちペロンベクトルは、”1個しかない”となります。

ページランクは、グーグル行列のL 1ノルム(合計が1)の固有ベクトルそのものです。つまり、ページランクは、"ペロンベクトル"に他ならないというのが、 英米の数学者の見解です。 この他、一般的用語で表現すれば、ページランク=確率ベクトル、ページランク=定常分布ベクトル等々いろいろあるでしょう。
 
なお、A のペロンベクトルを右ペロンベクトル、上記を左ペロンベクトルと呼びます。従って、グーグル行列を列形式で記述すれば、ページランクは、右ペロンベクトル、下記引用2のように行形式で記述すれば、ページランクは、左ペロンベクトルとなります。

(出発点である隣接行列を転置云々する必要性など全くなく、最終的に行ベクトル→列ベクトルとしても全く同じです。英米の数学者の場合、グーグル行列を、行形式で記述するほうがむしろ多い ようです。

2.ペロン・フロベニウスの定理とページランク 線形代数の基礎知識を有しておられる方は、ページランクがグーグル行列の主固有ベクトルであることが、お分かりでしょう。
固有ベクトルは、テキスト的には、まず、det |A - λE | = 0 の固有方程式を解いて、λ(固有値)を求め、 次に[A - λE][Xn]=0 の同次連立方程式を解いて、それぞれのλに対応する固有ベクトルを求めます。(Eは、単位行列。)

従って、固有値との関係は?パワー法で求めるとどうなるのか?との疑問が、生じます。

この点について、結論的に言えば、英米の数学者によれば、グーグル行列の主固有値(最大固有値)は、1 であり、かつ、グーグル行列は、既約(=強連結)であることから、上記に詳説したように、ペロン・フロベニウスの定理を適用し、主固有値は、重複せず、ページランクベクトル(=ペロンベクトル)の一意性が証明されるとされています。
(注)handbook of linear algebra(編集者:Kenneth H. Rosen)456頁(Adobe Reader 版)より。①グラフが強連結②行列が既約 の2つは同値です。

線形代数のハンドブック →


具体的には、
①他のページへのリンクを全く行っていないウェブページについては、他ページへのリンクがあるとみなして、1/N (Nは、対象の総ページ数)を割り当てる。
②次に、少なくとも1個以上の他ページへのリンクを有するウェブページについて、同様に、他の全てのウェブページへのリンクがあるとみなして、α/Nを割り当てる。
(A→A=自ページから自ページについても同様にα/Nを割り当てる。αは、固定値であれば、0.15です。)

①②より、グーグル行列は、強連結=既約となり、ペロン・フロベニウスの定理から、ページランクベクトルの一意性が導き出せるとされています。 (上記を証明したとするウェブページの該当部分を下記引用に紹介しておきます。)

③さらに、下記引用によれば、②からして、グーグル行列は、primitive matrix(原始行列)となり、パワー法によって、定常分布ベクトル・確率ベクトル(=ページランク)を求めうることが、 証明されるのだそうです。なお、パワー法により、主固有ベクトルへ収束することは、既によく知られています。handbook of linear algebra(編集者:Kenneth H. Rosen) Adobe Reader 版682頁より。ウェブ上であれば、Wiki の英文の ペロンーフロベニウスの定理ご参照)

なお、上記内容のほぼ全ては、実質的には、上記線形代数テキストの執筆者Carl Dean. Meyer (Google's PageRank and Beyond, 邦訳Google PageRankの数理 ―最強検索エンジンのランキング手法を求めての執筆者の1人)が明らかにしたと考えます。 3.例

①言語の問題を考慮すれば、計算対象のウェブページ(=頂点)が強連結であるというのは、前頁において書いたように本当に異様です。ウェブサイトを使用言語毎に小行列として処理している可能性が高いでしょうが、実際にgoogleがどのように処理しているのかについては、日本人なら、誰しも一番興味のある点ですが、全く不明です。
②dangling linkの処理方法が、特許文書と異なっています。dangling link は、バックリンクのみで発リンクが0のため、本来は、ページランク計算上、数値に全く影響を及ぼしません。このため、 特許文書 では、1回目の計算では無視し、計算後に数値を割り当てするとしています。例えば、0.15/Nの数値が付与されるはずです。(Nは、対象の総ページ数)一方、数学者による理論上の解明では、数値計算に含まれることとなってしまいます。

1.5個のウェブページのみから構成されるウェブ世界を想定した場合の実際のリンク関係。下記引用2より。
(ページEは、発リンクがなく、Cからのバックリンクのみ有している。)
A B C D E
A 0 1 1/2 1/3 0
B 1/2 0 0 1/3 0
C 0 0 0 1/3 0
D 1/2 0 0 0 0
E 0 0 1/2 0 0

2.dangling link を下図のように修正。(E→Eについても1/nを割り当てる。)

A B C D E
A 0 1 1/2 1/3 1/5
B 1/2 0 0 1/3 1/5
C 0 0 0 1/3 1/5
D 1/2 0 0 0 1/5
E 0 0 1/2 0 1/5

3. 上記2について、英米の学者間でいうところのグーグル行列。

Calculating Web Page Authority Using the PageRank Algorithm 等々ご参照。
強連結(既約)となり、ページランクベクトル(主固有値1)は一意的に定まるとしています。

α=0.15の固定値としているため、0.15/5で3/100。
A B C D E
A 3/100 22/25 91/200 47/150 1/5
B 91/200 3/100 3/100 47/15 1/5
C 3/100 3/100 3/1000 47/15 1/5
D 91/200 3/100 3/100 3/100 1/5
E 3/100 3/100 91/200 3/100 1/5
合計 1 1 1 1 1

4.御参考

*グーグル行列(注①)の主固有値=1を証明したとするウェブページ。
なお、証明としていますが、意味がないと考えます?。グーグル行列を行形式(下記引用2)で記述しても、列形式で記述しても同じことでしょう。

THE $25,000,000,000 EIGENVECTOR THE LINEAR ALGEBRA BEHIND GOOGLEより引用。

More generally, the matrix A for any web must have 1 as an eigenvalue if the web in question has no dangling nodes (pages with no outgoing links). To see this, first note that for a general web of n pages formula (2.1) gives rise to a matrix A with Aij = 1/nj if page j links to page i, Aij = 0 otherwise. The jth column of A then contains nj non-zero entries, each equal to 1/nj , and the column thus sums to 1. This motivates the following definition, used in the study of Markov chains: 

Definition 2.1. A square matrix is called a column-stochastic matrix if all of its entries are nonnegative and the entries in each column sum to one.

The matrix A for a web with no dangling nodes is column-stochastic. We now prove 

Proposition 1. Every column-stochastic matrix has 1 as an eigenvalue.

Proof. Let A be an n×n column-stochastic matrix and let e denote an n dimensional column vector with all entries equal to 1. Recall that A and its transpose A have the same eigenvalues. Since A is column-stochastic it is easy to see that A Te = e, so that 1 is an eigenvalue for A Tand hence for A.

*ページランクベクトルが、単一である旨を証明したとするウェブページ。(実体上は、単なる上記線形代数のテキストの引用では?)
Calculating Web Page Authority Using the PageRank Algorithm より引用。

①下記引用原文中[8]は、上記③で転載した線形代数のテキストです。
②下記引用原文中Gは、上記のような要素に0を全く含まないグーグル行列

6 Proof of Uniqueness and Convergence

6.1 The Spectral Radius and Perron Root

We will now prove conclusively that, by its construction, the Google matrix will have a unique PageRank vector to which we can converge. First, we define the spectrum (set of distinct eigenvalues) of A as σ(A), and the spectral radius of a square matrix A as ρ(A) = max |λ|[8]. We now examine the Perron-Frobenius Theorem, which applies to nonnegative, irreducible square matrices A. Borrowing from [8], the Perron-Frobenius Theorem tells us that:

・ r =ρ (A) is the Perron root, r > 0 and r ∈σ (A).
・ The algebraic multiplicity of r is 1.
・ There exists a positive x > 0 such that Ax = rx.
・ There is a unique Perron vector such that:
  Ap = rp.
・ p > 0.
・ ||p|| 1= 1 (where ||p|| 1represents the L 1-Norm of the vector p, such that ||X|| 1= ∑|Xr|.
・ There are no other nonnegative eigenvectors for A except for positive multiples of p.

Furthermore, we can apply Perron’s Theorem to A, which requires that A be positive with r =ρ(A) .
Perron’s Theorem gives us that “r is the only eigenvalue on the spectral circle of A” .

Notice the crucial facts that ρ(G) is the only eigenvalue on the spectral circle of G and that the
algebraic multiplicity of ρ(G) is one, by the Perron and Perron-Frobenius theories. We have established
that r = ρ(G) is the dominant eigenvalue of G.

6.2 Primitivity, Stationary Distribution, and Eigenvectors

Now that we have established these facts, we conclude that G is a primitive matrix, defined as a “nonnegative irreducible matrix A having only one eigenvalue, r = (A), on its spectral circle” [8]. If we know that P is primitive (as G is), we know that lim P k(k→∞) exists [8].

(証明部分省略。)
Thus, we conclude that the PageRank vector, the left Perron vector, and the stationary distribution vector of G are one and the same, and so finding the PageRank vector of G is equivalent to finding the dominant right eigenvector of G T, or the dominant left eigenvector (left Perron vector) of G.


5.その他基礎的補足

線形代数の標準的テキスト(Carl Dean. Meyer, 「Matrix Analysis and Applied Linear Algebra」 The Society for Industrial and Applied Mathematics, Philadelphia, 2000) より。(ページ数は、Adobe Reader 8による。)
①順列行列(permutation matrix)

定義: 要素が全て1又は0のn×n行列であって、PP =I となる行列。(ここで、I は、単位行列。つまり、P -1=P  が成立する要素が全て1又は0のn×n行列。)

例:
0 1 0
0 0 1
1 0 0
×
1 2 3
4 5 6
7 8 9
4 5 6
7 8 9
1 2 3

(注)なお、P APは、Aの行と列を同時に変更することを意味します。(P -1=P t ですので、要するに相似です。)

②既約行列(irreducible matrix)


(例)T n×n X =b とし、Tが、順列行列(permutation matrix)により、

の形式で各小行列へ分割できれば、Tは可約(reducible)である。ただし、Aは、r×r、Cは、n-r×n-r の正方行列。

、bが同様に

X1
2
1
2
としうれば、 T n×n X =bは、AX 1+BX 2=b 1、CX 2=b 2としえ、行列の計算は、容易となる。(後者でX2を求めれば、前者は、AX=Bの形になる。)


1. det T=detA・det Cが成立します。
2. 固有値についても、1. からして(det T=λ 1×λ 2・・・λ なので)、Tの固有多項式をTλとし、A・Cも同様にAλ、Cλとすれば、Tλ=Aλ・Cλも成立します。
等々、上記のような変換は、文字通り、行列をreduceすることを意味します。それで、行列Tを順列行列でreduceできない場合、Tは、irreducible行列(既約の行列)です。

irreducible行列(既約の行列)は、一般に次の通り定義されます。

定義: AP=
0
となる 順列行列(permutation matrix)が存在しない行列。(可約でない行列) ただし、Xは、r×r、Zは、n-r×n-r の正方行列。