Google のページランクグラフ上のランダムウォークと

(1)

グラフ上のランダムウォークと

Google

のページランク

内藤久資

名古屋大学多元数理科学研究科

２０１１年度数学アゴラ夏季集中コース２０１１年８月

(2011/08/12

改訂版

)

(2)

Introduction はじめに

コンピュータやインターネットで使われている数学コンピュータやプログラムの基本論理：

ラムダ計算・数理論理学画像・動画・音声などの処理：

フーリエ変換（解析学）・符号理論（代数学）

３Ｄグラフィックス：

アフィン幾何学・射影幾何学・微分幾何学コンピュータネットワーク：

グラフ理論・確率論・暗号（整数論・代数学）

この他にもいろいろ

(3)

Introduction はじめに

今回の数学アゴラでは夏の数学アゴラ

ランダムウォークと

Google

ページランク秋の数学アゴラ

線形代数と３Ｄグラフィックス

(4)

Introduction 話の計画

想定している予備知識

おおよそ高校２年程度の数学

ある程度知っていると仮定していること

◮ 連立一次方程式・二次方程式・複素数

◮ 平面ベクトル・数列・確率知っていると望ましいこと

◮ 空間ベクトル・行列・一次変換

◮ 三角関数・和の記号（Σ）

◮ 数列の収束

(5)

Plan of Talk

１日目

◮ Googleページランクとは何か(Section 2)

◮ 連立一次方程式と線形代数(Section 3.1〜 3.3) ２日目

◮ 連立一次方程式と線形代数(Section 3.4〜 3.5)

◮ 行列の固有値と固有ベクトル(Section 3.6〜3.8) ３日目

◮ グラフとランダムウォーク(Section 4.1〜 4.6) ４日目

◮ Googleページランクとその計算(Section 5)

(6)

この話の目標

以下の中身を「数学」として理解すること

◮ Googleのページランクはどのような考え方の下に決まってい

るか？

◮ その考え方の基礎になっている数学はどのようなものか？

◮ 実際にページランクを計算する際に問題となることは何か？

(7)

Googleページランクとは？

Google _{ページランクとは？}

(8)

Googleページランク

Google

ページランクとは何か？

(Section 1.1)

「

Google

検索」を実現している技術

◮ インターネット上に存在するウェブページのデータを収集する

◮ ウェブページのデータから「キーワード」を抜き出しデータベースに保存する

◮ キーワードに一致するウェブページの情報をデータベースから検索する

◮ キーワードに一致したウェブページを

「重要なものを上位にして」表示する

「重要なものを上位に表示」＝「ページランクの順位で表示」

(9)

Googleページランク

Google

ページランクとは何か？

(Section 2)

「ページランク」とは

◮ 検索結果のウェブページの情報の重要度をきめる尺度

◮ Googleの研究者であるS.Brinと L.Pageによって定義された

(1999年)

◮ 「L.Pageによるランク付け」という言葉の意味もある

「重要度」は以下の２つの考え方による

◮ 多くのページからリンクされているページは「重要なページ」

◮ 重要なページからリンクされているページは「重要なページ」

すべてのウェブページに「重要度」という数値を計算する

(10)

問題のモデル化

ページランクのモデル化

(Section 2.1)

ページランクのように数学的に曖昧な問題には

「モデル化」ということを行う必要がある

「問題のモデル化」とは

...

◮ 問題の本質的な部分を抜き出して

◮ 数学の言葉に書き直す

◮ 細かいことは後からモデルを修正することで対応するなので

,

細かいことは気にせず

,

「うまく記述できる」数学的なモデルを探すことが重要

(11)

(Section 2.1)

ウェブページの中身

◮ ウェブページは「HyperText Mark up Language」と呼ばれる仕様で記述されている

◮ HTMLの中には「Hyper Link」と呼ばれる他のページへのリンク情報が書いてあるそこで

....

◮ 各ページを「１つの点」とおきかえる

◮ ページAにページB へのリンクがあるとき

「A からB への矢印」をつける

◮ これをすべてのページに適用する

(12)

(Section 2.1)

世界に３つのページ

v

₁

, v

₂

, v

₃ のみが存在し

,

v

1 からは

v

2

, v

3 へ

, v

2 からは

v

3 へ

, v

3 からは

v

1 へリンクがあるとき

このリンクをあらわす図は以下のようになる

. v

1

v

₂

v

₃

(Example 2.1.1, P.5)

このような「頂点と向きの付いた辺の組」を

「グラフ」（「有向グラフ」）と呼ぶ

.

(Definition 2.1.2, P. 5)

(13)

(Section 2.1)

ページランクのモデル化の第１ステップ：

「インターネット上のウェブデータ全体のリンク構造を

（有向）グラフと考える」

ページランクの定義

(Definition 2.1.3, P. 6)

ページ

v

i のランク

r(v

i

)

を次の式で定義する

r(v

_i

) = X

vj∈B_vi

r(v

_j

)

|v

_j

| (2.1)

（ただし

B

_v_i は

v

_i を始点とする辺の集合）

「すべてのページに対するページランクの値の組

{r(v

_i

)}

を

式

(2.1)

が成り立つように定義する」という意味である

.

(14)

(Section 2.1)

Example 2.1.6

のグラフから決まるページランクの式



 



 



r

₁

= r

₃

, r

₂

= 1

2 r

₁

, r

₃

= 1

2 r

₁

+ r

₂

(2.2)

(Example 2.1.6, P. 7)

これは

,

未知数

{r

₁

, r

₂

, r

₃

}

に対する連立一次方程式連立一次方程式

(2.2)

の解

r

1

= k, r

2

= k/2, r

3

= k

(15)

(Section 2.1)

Example

の連立一次方程式

(2.2)

は



 



 



r

1

− r

3

= 0,

− 1

2 r

₁

+ r

₂

= 0,

− 1

2 r

₁

− r

₂

+ r

₃

= 0

(2.3)

の形をしているので

(0, 0, 0)

は明らかに解となるなので

(0, 0, 0)

以外の解を探す必要がある

(16)

(Section 2.1)

これでページランクを以下のようにモデル化できた

◮ インターネット上のウェブデータ全体のリンク構造を有向グラフと考え

◮ 連立一次方程式(2.1)の解としてページランクを定義する

(17)

問題の確率的なモデル化

ページランクの確率的なモデル化

(Section 2.2)

ページランクのもう一つのモデル化としてユーザの滞在確率に基づくモデル化ができる

ある時刻

t = n

でのインターネットの滞在ユーザのうちページ

v

_i に滞在しているユーザの割合を

p

_i

(n)

とおくページ

v

_i に滞在しているユーザは

次の時刻

t = n + 1

にはリンクをたどって他のページに移動する

ユーザがページ内のどのリンクをクリックするかは等確率と仮定する

(18)

(Section 2.2)

長時間にわたって

,

このプロセスを繰り返したときの各ページのユーザの滞在確率

p(v

i

) = p

i

= lim

n→∞

p

i

(n)

をページ

v

i のページランクと定義する

.

つまり

{p

i

(n)}

から

{p

i

(n + 1)}

をきめる式は

p

_i

(n + 1) = X

vj∈B_vi

1 |v

_j

| p

_j

(n) (2.4)

で与えられる

.

(19)

(Section 2.2) Example 2.1.1

の場合



 



 



p

1

(n + 1) = p

3

(n), p

₂

(n + 1) = 1

2 p

₁

(n), p

₃

(n + 1) = 1

2 p

₁

(n) + p

₂

(n)

(2.5)

p

₁

(0) = 1, p

₂

(0) = p

₃

(0) = 0

の時

t 1 2 3 4 5 6 7 8 9 · · ·

p1 0 1/2 1/2 1/4 1/2 3/8 3/8 7/16 3/8 → 2/5 p2 1/2 0 1/4 1/2 1/8 1/4 3/16 3/16 7/32 → 1/5 p3 1/2 1/2 1/4 1/2 3/8 3/8 7/16 3/8 13/32 → 2/5

長時間経過したときの滞在確率

(p

₁

, p

₂

, p

₃

) = (2/5, 1/5, 2/5)

は

Example 2.1.6

の連立一次方程式の解になる

(20)

(Section 2.2) Theorem 2.2.4 (P. 9)

数列

{p

i

(n)}

を漸化式

(2.4)

で定義する

.

すべての

i

について

p

i

(n)

の

n → ∞

としたときの極限

p

_i が存在すると仮定すれば

,

極限

{p

_i

}

は

p

_i

= X

vj∈B_vi

1 |v

_j

| p

_j

(2.6)

をみたす

つまり

,

この定理の仮定の下では

両方のモデルによる定義式

(2.6), (2.1)

は同じ要するに「どっちのモデルで考えてもよい」

(21)

モデル化のまとめ

ページランクのモデル化のまとめ

(Section 2.3)

インターネット上のウェブデータ全体のリンク構造を

（有向）グラフと考え

◮ 各ページのリンク情報をあらわす連立一次方程式の解をページランクとする

◮ ユーザの滞在確率をページランクとする

のいずれかのモデルを考えればよいことがわかる

いずれのモデルであっても次のような問題を考察する必要がある

(22)

モデル化のまとめ

ページランクのモデルに関する問題

(Section 2.3)

これらのモデルを考えるために適切な数学の道具は何か？

第一のモデルについて：

◮ この連立一次方程式は,必ず解を持つのか？

◮ 解を持つとしたら,その解はただ一つに限るのか？

第二のモデルについて：

◮ 長時間経過したときに,滞在確率は,必ずある一定の値に収束するのか？

◮ それは初期条件（t

= 0

での滞在確率）の与え方に依存するのか？

◮ 「長時間」とはどのくらいの時間（計算ステップ数）を意味するのか？

これらの計算プロセスは

,

どのくらいの時間がかかるのか？

数万〜数十億ページを含むデータに対して計算可能なのか？

(23)

連立一次方程式と線形代数

(24)

連立一次方程式と線形代数連立一次方程式

連立一次方程式

(Section 3.1)

ここでは連立一次方程式

( ax + by = x

₁

,

cx + dy = y

₁

, (3.1)

の解について調べよう

本当は

,

より一般の連立一次方程式を調べたいのだけど

...



 



 



a

₁₁

x

₁

+ a

₁₂

x

₂

+ · · · + a

_1N

x

_N

= a

₁

, a

₂₁

x

₁

+ a

₂₂

x

₂

+ · · · + a

_2N

x

_N

= a

₂

,

.. .

a

_N₁

x

₁

+ a

_N2

x

₂

+ · · · + a

_{N N}

x

_N

= a

_N

,

(25)

(Section 3.1)

(3.1)

の解について

,

高校では次のようにならう（はず）

1 直線ax

+

by

=

x1,cx

+

dy

=

y1 が相異る２直線であり,平行でない場合には,２直線の共有点はxy-平面上の１点となり,

その点が(3.1)の解となる. 特に,解は次のように書ける.

x

=

by¹−dx¹

ad−bc , y

=

ay¹−cx¹ ad−bc

2 直線ax

+

by

=

x1,cx

+

dy

=

y1 が同一の直線となる場合には,その同一の直線ax

+

by

=

x1 上のすべての点が(3.1)の解となる.

3 直線ax

+

by

=

x¹,cx

+

dy

=

y¹ が平行な相異る２直線である場合には,この２直線の共有点は存在しないので, (3.1)の解は存在しない.

(26)

(Section 3.1)

前ページの事実を次のことを使って書き換える

.

◮ 「ax

+

by

=

x1, cx

+

dy

=

y1が平行」

⇐⇒「ad−bc

= 0」

◮ 「ax

+

by

=

x¹, cx

+

dy

=

y¹が同一の直線」

⇐⇒「a

:

b

:

x¹

=

c

:

d

:

y¹」

(3.1)

の解の存在は次のように分類できる

1 ad−bc6= 0ならば, (3.1)はただひとつの解を持つ

2 ad−bc= 0かつby¹−dx¹

= 0

(またはay¹−cx¹

= 0）なら

ば,ax

+

by

=

x¹ をみたすすべての

(x, y)

が (3.1)の解となる.

3 ad−bc= 0かつby1−dx16= 0 (または ay1−cx16= 0)ならば, (3.1)の解は存在しない.

(27)

(Section 3.1)

重要なこと

「解がただひとつに決まる」

⇐⇒

「

ad − bc 6= 0

」連立一次方程式を「写像」と考える

x y

7→

ax + by cx + dy

xy-

平面上の点

(x, y)

を

(ax + by, cx + dy)

へ「移動」したとき

(ax + by, cx + dy ) = (x

1

, y

1

)

となる点

(x, y)

が見つかる

⇐⇒ (x, y)

は

(3.1)

の解

このとき

ad − bc 6= 0

という条件は何を意味するのか？

(28)

連立一次方程式と線形代数数ベクトル空間

ベクトル

(Section 3.2)

「ベクトル」とは

N

個の実数

{x

_i

}

^N_i=1 を縦に並べたもの

x =





 x

₁

.. . x

N







x = (x

_i

)

と簡単に書いてしまうこともある

(Definition 3.2.1, P. 13)

各

x

_i を

x

の第

i

成分と呼ぶ

(29)

数ベクトル空間

(Section 3.2)

N

成分の列ベクトル全体の集合

R

^N

=



 

  x =





 x

1

.. . x

_N





 : x

_i

∈ R



 

 

を

N

次元数ベクトル空間と呼ぶ

(Definition 3.2.2, P. 13)

R

^N _の元で

,

すべての成分が

0

であるベクトルを零ベクトル

0

_と書く

(Definition 3.2.4, P. 13)

(30)

(Section 3.2)

２次元数ベクトル空間

R

² _の元と

xy-

平面上の点とは１対１対応がある

◮ xy-平面上の座標

(x, y)

を持つ点とベクトルx

=

x y

は１対１に対応する３次元数ベクトル空間

R

³ _の元と

xyz-

空間内の点は１対１に対応する

N

次元数ベクトル空間

R

^N _は

座標平面・座標空間を一般化した概念

(31)

ベクトルの和とスカラー倍

(Section 3.2)

R

^N _{の２つのベクトル}

x, y ∈ R

^N _{に対して和}

x + y

x =





 x

₁

.. . x

N





 , y =





 y

₁

.. . y

N





 = ⇒ x + y =







x

₁

+ y

₁

.. . x

N

+ y

N







a ∈ R , x ∈ R

^N _に対して

x

の

a

倍（スカラー倍）

x =





 x

₁

.. . x

_N





 = ⇒ ax =





 ax

₁

.. . ax

_N







(Definition 3.2.6, P. 14)

(32)

ベクトル空間とは

(Section 3.2)

ベクトル空間とは

◮ 和とスカラー倍が定義できて

◮ 零ベクトルと呼ばれる特別な元が存在する集合のこと数ベクトル空間と

座標平面・座標空間を同一視することによって座標平面・座標空間に演算が定義できるようになった

(33)

ベクトル空間の部分空間

(Section 3.2)

R

^N _{の部分集合}

W

が部分空間であるとは

W

が以下の３つの条件をみたすこと

1 零ベクトルはW に含まれる. すなわち,0∈W である.

2 W の任意の２つの元x,y∈W に対してx

+

w∈W をみたす.

3 W の任意の元x∈W と任意のa∈Rに対してax∈W をみたす.

R

² _{の部分空間とは}

xy-

平面上の原点を通る直線のこと

R

³ _{の部分空間とは}

xyz-

空間内の原点を通る直線または原点を通る平面のこと

(34)

ベクトル空間の部分空間の例

(Section 3.2, Example 3.2.9) x ∈ R

² _に対して

W = {ax : a ∈ R }

は

xy-

平面上で

,

原点を通り

,

方向ベクトルが

x

となる直線

◮ x

= 1

2

ならばW

=

a

2a

（直線y

= 2x

上の点全体）

x, y ∈ R

³ _（

x

は

y

のスカラー倍でない）に対して

W = {ax + by : a, b ∈ R }

は

xyz-

座標空間内で

,

原点を通り

, x, y

を含む平面

◮ x

=





1 1 0



, y

=





0 1 1



ならばW

=









 a a

+

b











（平面x−y

+

z

= 0

上の点全体）

(35)

ベクトル空間・部分空間の次元

(Section 3.2)

我々が普通に思っている次元

◮ 「１点」＝「0次元」

◮ 「直線」＝「1次元」

◮ 「平面」＝「2次元」

◮ 「空間」＝「3次元」

「次元」＝「自由に動き回れる方向」

(36)

(Section 3.2)

R

^N _の中の

k

本のベクトルの組

{x

₁

, . . . x

_k

}

が一次独立

a

₁

x

₁

+ · · · + a

_k

x

_k

= 0 = ⇒ a

₁

= · · · = a

_k

= 0

が成り立つこと

◮ 一次独立でないとき一次従属という

(Definition 3.2.11, P. 15)

２つのベクトル

{x, y}

が平行でない

⇐⇒ {x, y}

は一次独立

(37)

(Section 3.2, Example 3.2.13)

ベクトルの組

{x, y, z}

が一次従属であると仮定する

ax + by + cz = 0

かつ

a, b, c

のうち少なくとも一つは

0

でない

◮ a6= 0と仮定すると,x

=

−^b_ay−^c_az

◮ よって,ベクトルxはyと z を含む平面上の点をあらわす

y z

x

(38)

(Section 3.2, Example 3.2.14) x =

1 2

, y = 1

−1

：一次独立

x = 1

2 , y = −2

−4

：一次従属

(y + 2x = 0 )

x =



 1 1 0



, y =



 0 1 1





_{：一次独立}

x =



 1 1 0



, y =



 0 1 1



, z =



 1

−1 1





_{：一次独立}

x =



 1 1 0



, y =



 0 1 1



, z =



 2 3 1





：一次従属

(2x + y − z = 0 )

(39)

(Section 3.2)

数ベクトル空間またはその部分空間

V

の次元が

k (dim V = k)

◮ V の中から一次独立なk 個のベクトルの組を選べる

◮ V の任意のk

+ 1

個のベクトルは一次従属

(Definition 3.2.15, P. 17)

これで我々がおもっている「自由に動ける方向の自由度」

と一致した次元になる

dim R

^N

= N

なので

, R

^N _の中から

N

個のベクトルの組

{x

₁

, . . . , x

_N

}

で一次独立なものを選ぶことができる

(40)

ベクトル空間・部分空間の基底

(Section 3.2) dim V = k

のとき

一次独立な

V

のベクトル

k

個からなる組を基底と呼ぶ

(Definition 3.2.19, 18)

R

^N _において

e

₁

=





 1 0 .. . 0







, · · · , e

_N

=





 0 .. . 0 1







∈ R

^N

は基底になる：

R

^N _{の標準基底}

(41)

(Section 3.2)

dim V = k

であって

, {x

₁

, . . . , x

_k

}

が基底であるとき

◮ すべてのx∈V は x

=

a¹x1

+

· · ·

+

akxk

と書くことができる

◮ 一次独立なベクトルの組の上のような和で書くことを一次結合であらわすという

(42)

(Section 3.2) R

² _{の基底の例：}

(Example 3.2.21, P. 18)

◮ e¹

= 1

0

,e²

= 0

1

：標準基底

◮ x1

= 1

1

,x2

= 1

−1

◮ y1

= 1

0

,y2

= 1

1

このほかにも無数の基底の取り方がある

x =

2 3

を上のそれぞれの基底の一次結合で書いてみる

x = 2e

1

+ 3e

2

= 5 2 x

₁

− 1

2 x

₂

= −y

1

+ 3y

2

(Example 3.2.24, P. 18)

(43)

ベクトルのノルム

(Section 3.2)

R

^N _{のベクトル}

x

のノルム

kxk

とは

1 x∈R^N に対して,kxk は非負実数をきめる

2 x∈R^N,k∈Rに対して,kkxk

=

|k| kxkが成り立つ

3 x,y∈R^N に対して,kx

+

yk ≤ kxk

+

kykが成り立つ

4 kxk

= 0

⇐⇒x

=

0が成り立つ

(Definition 3.2.25, P. 19)

通常我々が使う「ベクトルの長さ」

,

「ベクトルの間の角度」

,

「２点間の距離」をきめている

p x

²

+ y

² のなかから

「ベクトルの長さ」がもつ性質だけを抜き出したもの

(44)

ベクトルのノルム

(Section 3.2)

よく利用されるノルムの例

(Example 3.2.26, P. 19) kxk

₁

= |x

₁

| + · · · + |x

_N

|,

kxk

₂

= p

|x

₁

|

²

+ · · · + |x

_N

|

²

, kxk

_∞

= max

i=1,...,N

|x

_i

|

1

−1 1

−1

1

−1 1

−1

1

−1 1

−1

kxk1= 1 kxk2= 1 kxk∞= 1

(45)

連立一次方程式と線形代数行列と連立一次方程式

行列

(Section 3.3, Definition 3.3.1) N × N

行列（

N

次正方行列）

A =







a

₁₁

a

₁₂

· · · a

_1N

a

₂₁

a

₂₂

· · · a

_2N

.. . .. . . .. .. . a

_N₁

a

_n2

· · · a

_{N N}







= a

₁

. . . a

_N

=





 a

₁

.. . a

_N







a

_ij ：

A

の

(i, j)

成分

前から

k

列目の列ベクトル

a

_k

=





 a

_1k

.. . a

_{N k}







^を第

k

列前から

ℓ

行目の行ベクトル

a

_ℓ

= a

_1ℓ

· · · a

_{N ℓ}

を第

ℓ

行簡単に

A = (a

ij

)

と書いちゃうこともある

(46)

行列

(Section 3.3, Definition 3.3.3) A = (a

ij

)

の

a

ii の部分：対角成分

E =







1 · · · 0 .. . . .. ...

0 · · · 1







^単位行列

O =







0 · · · 0 .. . . .. ...

0 · · · 0







^零行列

(47)

行列の和とスカラー倍

(Section 3.3, Definition 3.3.4)

N × N

行列

A = (a

_ij

), B = (b

_ij

)

に対して

,

和

A + B

を

A + B = (a

_ij

+ b

_ij

)

k ∈ R , N × N

行列

A = (a

_ij

)

に対して

,

スカラー倍

kA

を

kA = (ka

_ij

)

A = 1 2

3 4

, B = 3 1

2 5

のとき

A + B = 4 3

4 9

, 3A =

3 6 9 12

(48)

行列とベクトルの積

(Section 3.3)

（縦ベクトル）

x = (x

_i

) ∈ R

^N _と

N × N

行列

A = (a

ij

)

の積

Ax

を

Ax =

N

X

k=1

a

_ik

x

_k

!

結果は

R

^N _{の縦ベクトル}

(Definition 3.3.5, P. 21) A =

1 2 3 4

, x =

2 3

のとき

Ax = 8

18 A = a b

c d

, x = x

y

のとき

Ax =

ax + by

cx + dy

(49)

行列と行列の積

(Section 3.3)

N × N

行列

A = (a

_ij

), B = (b

_ij

)

の積

AB

を

AB =

N

X

k=1

a

_ik

b

_kj

!

結果は

N × N

行列

(Definition 3.3.6, P. 21) A =

a b c d

, B =

x y w z

のとき

AB =

ax + bw ay + bz cx + dw cy + dz

, BA =

ax + cy bx + dy aw + cz bw + dz

A = 1 2

3 4

, B = 2 3

4 5

のとき

AB =

10 13 22 29

BA =

11 16

19 28

(50)

行列

(Section 3.3)

N × N

行列

A = (a

_ij

), B = (b

_ij

)

の積

AB

は

B = b

₁

· · · b

_N

と縦ベクトルで書いたとき

AB = Ab

₁

· · · Ab

_N

として

N

個の「行列×ベクトル」の計算をしていること

(Remark 3.3.12, P. 22)

N × N

行列

A = (a

_ij

)

に対して

その転置行列

A

^T を

A

^T

= (a

_ji

)

と定義する

（行と列を入れ替えた行列のこと）

(Definition 3.3.7, P. 21) A =

a b c d

のとき

A

^T

= a c

b d

(51)

連立一次方程式を行列で書く

(Section 3.3, Example 3.3.13)

( ax + by = x

₁

,

cx + dy = y

1

, (3.1)

は

A = a b

c d

, x = x

y

, b = x

₁

y

₁

とおくと

Ax = b

と単純な形で書くことができる

(52)

連立一次方程式と線形代数線形写像

線形写像

(Section 3.4)

N × N

行列

A = (a

ij

)

が定める線形写像（一次変換）

R

^N

∋ x 7→ Ax ∈ R

^N のこと

(Definition 3.4.1, P. 23)

線形写像は次の性質を持つ

.

1 A0

=

0.

2 任意のx,y∈R^N,λ,µ∈Rに対して, A(λx

+

µy) =λAx

+

µAy が成り立つ.

(Proposition 3.4.2, P. 23)

(53)

線形写像の例

(Section 3.4, Example 3.4.4) A =

1 2 3 4

のとき

Ae

₁

= 1 2

3 4 1 0

= 1

3 , Ae

₂

= 1 2

3 4 0 1

= 2

4

よって

, Ax = 1 2

3 4 2 3

= 8

18

基底

{x

_i

}

を取ったとき

,

行列

A

から定まる線形写像の行き先は

,

基底の行き先

{Ax

_i

}

で完全に記述できる

(Remark 3.4.5, P. 25)

単位行列

E

は

Ex = x

となる線形写像をきめる零行列

O

は

Ox = 0

となる線形写像をきめる

(54)

線形写像の例

(Section 3.4, Example 3.4.7)

行列

A =

−1 0 0 1

が定める線形写像は

, x 7→ −x, y 7→ y

であるので

, y

軸に関する折り返し

A =

1 0 0 −1

が定める線形写像は

x

軸に関する折り返し原点を通る直線に関する折り返しは線形写像

x Ax

(55)

線形写像の例

(Section 3.4, Example 3.4.8)

原点を中心とする角度

θ

の回転は行列

A =

cos θ − sin θ sin θ cos θ

できまる線形写像

x Ax

θ

(56)

逆行列

(Section 3.4)

N × N

行列

A

に対して

,

AA

⁻¹

= A

⁻¹

A = E

をみたす

N × N

行列

A

⁻¹ が存在すれば

A

⁻¹ を

A

の逆行列と呼ぶ

(Definition 3.4.9, P. 26)

A

に逆行列が存在するとき

, A

は正則とよばれる

(57)

逆行列

(Section 3.4) A =

a b c d

, A

⁻¹

=

x y z w

とおいて計算してみる

AA

⁻¹

=

ax + bz ay + bw cx + dz cy + dw

= 1 0

0 1

◮ ad−bc6= 0ならば A⁻¹

=

x y z w

= 1

ad−bc

a −b

−c d

◮ ad−bc

= 0

の時には逆行列が存在しない

(Example 3.4.10, P. 26)

(58)

連立一次方程式の解の存在と逆行列

(Section 3.4)

「連立一次方程式がただひとつの解を持つための条件」

⇐⇒

「

A

が逆行列を持つための条件」

となっていることがわかった

N × N

行列

A

が逆行列を持てば

Ax = b

にはただひとつの解

x = A

⁻¹

b

が存在する

(Theorem 3.4.14, P. 27)

(59)

連立一次方程式の解の存在と逆行列

(Section 3.4, Example 3.4.15) ( x + 2y = 3,

3x + 4y = 4 1 2

3 4 x y

= 3

4

この行列

1 2

3 4

には逆行列が存在する

x y

=

−2 1

3 2

−

¹₂

1 2 3 4

x y

=

−2 1

3 2

−

¹₂

3 4

= −2

5 2

(60)

ページランクをきめる連立一次方程式

(Section 3.4)

ページランクを計算する際の連立一次方程式

r(v

_i

) = X

vj∈B_vi

r(v

_j

)

|v

_j

| (2.1)

は

Ax = x

の形をしている

この連立一次方程式は

,

両辺に逆行列を左からかけても解を得ることはできないページランクに関係する連立一次方程式を解くためには

,

線形写像に関するより詳しい情報が必要

(61)

連立一次方程式と線形代数行列式

逆行列を持つための条件と行列式

(Section 3.5) 2 × 2

行列

A =

a b c d

について以下の４条件は同値

1 Aが正則である. （Aには逆行列A⁻¹が存在する.）

2 ad−bc6= 0

3 Aを２つの列ベクトルa1

=

a

c

,a2

=

b

d

を使って A

= (a

¹a2

)

と書いたとき,{a¹,a2}が一次独立である.

4 Aを２つの行ベクトルa1

=

a b

,a2

=

c dを使って A

=

a1

a2

と書いたとき,{a¹,a²}が一次独立である.

(Theorem 3.5.1, P. 28)

(62)

行列式

(Section 3.5) 2 × 2

行列

A =

a b c d

に対して

,

その行列式

det A

を

det A = ad − bc

で定義する

(Definition 3.5.2, P. 28) N × N

行列の場合の行列式

◮

3

×

3

行列の場合

det

A

=

a11a22a33

+

a12a23a31

+

a13a21a32

−a¹³a²²a³¹−a¹²a²¹a³³−a¹¹a²³a³²

（３次式になっている）

◮ N×N 行列の場合には,aij に関するN 次式のN

!

項の和

(Remark 3.5.3, P. 28)

(63)

逆行列を持つための条件と行列式

(Section 3.5)

N × N

行列

A = (a

_ij

)

に対して

,

以下の４条件は同値

2

det

A6= 0

3 AをN 本の列ベクトルai

=





 a¹i

... aN i





を使って

A

= (a

¹. . .aN

)

と書いたとき,{a¹, . . . ,aN}が一次独立

4 AをN 本の行ベクトルaj

=

aj1 · · · ajNを使って A

=





 a1

... aN





と書いたとき,{a1, . . . ,aN}が一次独立

(Theorem 3.5.4, P. 29)

(64)

行列式の性質

(Section 3.5)

行列式は以下の性質をみたす

.

1

det

E

= 1

2

(det

A)(detB) = (detAB)

3

det

A^T

= det

A

(Theorem 3.5.6, P. 29)

(65)

行列のランク

(Section 3.5)

N × N

行列

A

を

N

本の列ベクトル

{a

_k

}

^N_k=1 を使って

A = a

₁

· · · a

_N

と書いたとき

, {a

_k

}

^N_k=1 の中の

一次独立なベクトルの本数の最大の値を

A

のランクと呼ぶ

(Definition 3.5.7, P. 29)

N × N

行列

A

に対して

,

以下の条件は同値

2

rank

A

=

N である.

(Theorem 3.5.8, P. 29)

(66)

行列のランクと線形写像

(Section 3.5) N × N

行列

A

がきめる線形写像を

f

_A

: R

^N

−→ R

^N

, x 7→ Ax

と書くことにしよう

このとき次が成り立つ

◮

rank

A

=

N ならば(detA6= 0ならば) f_A

(

R^N

) =

R^N が成り立つ

◮

rank

A< N ならば(detA

= 0

ならば) f_A

(

R^N

)

⊂R^N （真に部分空間）が成り立つ

つまり

det A = 0

のとき

Ax = b

が解を持つか否かは

b ∈ f

_A

( R

^N

) or b 6∈ f

_A

( R

^N

)

で状況が異なる

(67)

次元定理

(Section 3.5)

「像」と「核」の定義

◮ N×N 行列Aが定める線形写像f_A に対して

f_A

(

R^N

)

をf_A の像と呼び

Im

f_A または

Im

Aであらわす

◮ {x∈R^N

:

f_A

(x) =

0}

=

{x∈R^N

:

A(x) =0} をf_A の核と呼び,

ker

f_Aまたは

ker

Aであらわす

(Definition 3.5.9, P. 30)

N × N

行列

A

に対して

,

次が成り立つ

.

1

dim Im

A

= rank

A,

2 N−

dim ker

A

= dim Im

A. （「次元定理」）

3

det

A6= 0 ならば

dim Im

A

=

N,

dim ker

A

= 0.

(Theorem 3.5.11, P. 30)

(68)

連立一次方程式の可解性

(Section 3.5)

Ax = b

の可解性は以下のように分類できる

1 Aが正則ならば,任意のb∈R^N に対して, ただひとつの解x

=

A⁻¹bが存在する.

2 Aが正則でないとき.

2.1 b6∈ImA_ならば,_{解は存在しない}. 2.2 b∈ImA_ならば,_{解が存在する}.

一つの解をx0 とおいたとき,_任意のy∈kerA_に対して, x=x0+y_{も解となり},_{任意の２解の差は}kerA_に入る.

(Theorem 3.5.13, P. 31)

(69)

連立一次方程式の可解性（

2 × 2

行列の場合）

(Section 3.5)

連立一次方程式^{a b}_{c d} ^x_y⁼^x_y¹

1

の可解性

1 ad−bc6= 0ならば,任意の b∈R² に対して, ただひとつの解x

=

A⁻¹bが存在する.

2 ad−bc

= 0

ならば 2.1

„a c

« と

„x¹ y1

«

が平行でないならば解は存在しない. 2.2

„a c

« と

„x1

y1

«

が平行でならば解が存在する. 解x0 が一つでも見つかれば,_{その他の解}xは x=x0+k

„ b

−a

«

と書ける.

(Corollary 3.5.14, P. 31) a

c

∈ Im A, b

−a

∈ ker A

であることに注意しよう

(70)

連立一次方程式の可解性（

2 × 2

行列の場合）

(Section 3.5)

ImA kerA (x1, y1)

ImA kerA

(x1, y1)

このような時には解は存在しないこのような時には解は存在する

ImA kerA

a+d6= 1の時 a+d= 1の時

(cf. Example 3.5.15) (cf. Example 3.5.16)

(71)

2 × 2

行列の場合

(Section 3.5, Example 3.5.15) 2 1

−2 −1 x y

= a

b

の解を調べてみる

◮

det

A

= 0

◮

ker

A

= span

−1

2

,

Im

A

= span

1

−1

◮ b

=

a

b

∈

Im

Aの時（a

=

−bの時）にのみ解が存在する

◮ x

=

a

−a

+

t −1

2

と書ける

これは

ker

Aを表している直線

2x +

y

= 0

に平行で,

(a,

−a)を通る直線

a = b = 0

と取ったとき

Ax = 0

_に

0

_{でない解が存在する} その解は

1

次元（

= dim ker A

）分存在している

(72)

行列の固有値

Google のページランク グラフ上のランダムウォークと

Google

(2011/08/12

)

Google

Plan of Talk

Google ページランクとは？

Google

(Section 1.1)

Google

Google

(Section 2)

(Section 2.1)

...

,

,

(Section 2.1)

....

(Section 2.1)

v

, v

, v

,

v

v

, v

, v

v

, v

v

. v

v

v

(Example 2.1.1, P.5)

.

(Definition 2.1.2, P. 5)

(Section 2.1)

(Definition 2.1.3, P. 6)

v

r(v

)

r(v

) = X

r(v

)

|v

| (2.1)

B

v

{r(v

)}

(2.1)

.

(Section 2.1)

Example 2.1.6



 

 



 

 



r

= r

, r

= 1

2 r

, r

= 1

2 r

+ r

(2.2)

(Example 2.1.6, P. 7)

,

{r

, r

, r

}

(2.2)

r

Google のページランクグラフ上のランダムウォークと

Google _{ページランクとは？}