ドミノタイリングの数え上げ ： 線形代数の組合せ論への応用として

平成

27年

度

学 位 論 文

ドミノタイ リングの数え上げ

― 線形代数の組合せ論への応用 と して一

兵 庫 教 育 大 学 大 学 院 教 育 内容・方 法 開 発 専 攻 自 然 系 教 育 分 野

M141491

学 校 教 育 研 究 科 認 識 形 成 系 教 育 コ ー ス

(数

学 ) 吉 岡 弘 和

目 次

第

1章

問題提起

1.1

ドミノタイ

1.2

ドミノタイ 第

2章

線形代数

2.1

ベ ク トル空間

リングとは

７ ７ ８   ・５ ・５ ２０ ２５   ２９ ２９ ３５ ４０ ４ ． ４４   ４８ ４８ ５ ． ５２ ５５ ５９   ６４ ６４ ６８ ７ ． ７７ ８２ リングの数 え方

2.2

線形写像

2.3

固有値・ 第

3章

3.1 3.2 3.3 3.4 3.5 第

4章

4.1 4.2 4.3 4.4 4.5 第

5章

5.1 5.2 5。3 5.4 5.5 固有 ベ ク トル 線形漸化式の一般論 定数係数線形漸化式 固有値が重解 となる とき 線形

3項

間漸化式 実数列 についての線形

3項

間漸化式 D2■_,D3,れ の一般解

Kasteleyn行

列 グ ラフの表記 。名称 グ ラフと ドミノタイ リング との関係 Kasteleyn行列 マ ッチ ングの 回転 εの条件

.…

Dれ_,電 の値 を与 える一般式 Gれ_,れ に対 す る行 列 κ Kasteleyn行

_{列の固有値}

σ_{2れ ,れ} の場合 G2π_-1,2あ の場合

2れ

の具体例

参考文献 謝辞 ２     ５     ６ ８     ８

は じめ に

問題 と目的

本論文では次 の問題 について扱 う。 問題 :π ×η長方形 に1×

2長

方形_(ド ミノ_)を敷 き詰め る方法 は何通 り あるか。

・ 図 1:4×

5長

方形 の ドミノタイ リングの一例 ドミノタイ リングの数え上 げ問題である。数 え上 げについて

,中

学校第

2学

年 では樹形 図な どを利用 して起 こ り得 る場合 を順序 よく整理 し

,漏

れや重複 な しに数 え上 げることによって確率 を求める場面で扱 っている。 また

,高

校数学では

,数

学

A「

場合の数 と確率」で数 え上 げの原則や

,順

列・組合せ及びその総数 の求め方 について理解 させ る とともに

,そ

れ ら を具体 的な場面 に活用 で きるようにす ることを目的 に扱 っている。 本論文の問題 は れ を小 さな数 に固定すれば

,適

当な単位正方形 に着 目 して分類 。整理す ることで

,高

校生にも理解 で きるような素朴な数 え上 げ の問題 となる。例 えば

,2×

η長方形 に ドミノを敷 き詰める方法であれば, 2× η長方形の左上端の単位正方形 に着 目す ると

,こ

の単位正方形 を覆 う ドミノの配置 は

2通

りに場合分 けす ることがで きる。 これ によ り

,2×

η 長方形の ドミノタイ リングの総数 を

%と

お くと

,al=1,α

2=2で

あ り, 三項間漸化式 αれ

=%_1+%_2(π

≧

3)で

表す こ とがで き

,一

般項 を求 めることが可能である。 同様 に π

=3,π

=4に

関す る漸化式 を求め るこ とも可能である。 しか し

,π

=5の

場合 において

,す

で に同様 の手法で は一般項 を求めることが相当困難である。 また

,m=2,π

=3,π

=4の

4 漸化式 に類似性等が見当た らず

,こ

の まま π ×η長方形 の場合へ と一般 化す ることは困難である。

以上の ことか ら

,本

論文ではこの問題 に対 して線形代数 とグラフ理論 を用 いた

,Kasteleynに

よる全 く別 の解法 を考察す る。Kasteleyn行列 は

1960年代にKastebynに よって発見された。

Kasteleynは

この Kattelen

行列を導入 して

,正

方格子 2部 グラフの完全マッチングの数え上げが線

形代数的方法で扱えることを示 した。

Kasteleyn行

列を用いて

,2π

×

2η

長方形の ドミノタイ リングの総数を導 き出す と

, 4'爾ι

tti (80S2面1111+COS2扇

∫

lT)

通 りであるとい う結果が得 られる。数え上げ問題であるから自然数が導

かれるはずの式であるにも関わらず

,三

角関数が使われている点はとて

も興味深い。

線形代数の組合せ論への応用

行列 に関 しては平成

21年

公示 の高等学校学習指導要領 か ら事実上排 除 されている。 しか し

,行

列はベク トル とともに数学のあ らゆる分野で取 り扱われてい る基礎 的な概念 である。 それ は

,数

学 の理論 の方面 ばか り で はな く

,自

然科学

,経

済学

,理

工学 な ど多 くの分野での応用 がな され, その重要性 が非常 に高い。 その一方で

,生

徒 に とって行列 は単 な る数 と は性格 が相 当異 な り

,親

しみがたい概念 で ある と思われ る。 また

,過

去 に私が行列の指導 を行 っていた頃 を振 り返 る と

,そ

の指導の内容 は計算 指導が中心 とな り

,行

列の必要性 や存在理 由な どの指導が十分 に出来ず, 行列が うまく扱 えていなかった ことは否 めない。私 はこの研究 を通 して, 改めて行列の持 つ性質 の有用性 や必要性 を確認 し

,他

の理論 との関わ り も再認識 したい と考 えた。 この ドミノタイ リングの問題 は数 え上 げ とい う素朴 な問題 が行列 を使 って解 けるひ とつの例 である。 また

,大

学数学 と高校数学 との関係性 について この問題 を通 して確認 をす ることも

,こ

の研究 に取 り組 んだ 目的である。

研 究内容の構成

本論文で は

,

ドミノタイ リング問題 に対 して線 形代数 とグラフ理論 を 用 いた解法 を解説 す る。 ドミノタイ リング とは ドミノを縦 または横 に重 な らない ように並べて

,m×

_{π長方形 に隙間な く敷 き詰めることである。} 本研究で はちπ ×η長方形の各単位正方形の重心 に自 と黒の頂点 をおき,

縦横に頂点を線分で結んだグラフ

(2部

グラフ

)を

考える。すると

,

ドミ

ノタイリングはグラフにおいて ドミノの頂点を結んだ辺の集まり

_(図 2,

図 3)で 決まる。図3の 太線のように

,辺

の集まりのうち

,各

頂点に

1つ

ずつ辺が接続 しているものを完全マッチングという。こうしたグラフ理

論の基本的内容については

,第

4章

で述べる。

Ｏ ｉ ｌ ● ｌ ｅ ‘ Ｔ ｌ １ ０ ー ９ １ ６ ー ● 一 ０ 三 ｔ ｓ ● ― 。 … “ … 図

3:2部

グ ラフの完全 マ ッ 図

2:ド

ミノタイ リング チ ング

このように

_;

ドミノタイ リングの問題を

2部

グラフの完全マッチング

の数え上げ問題にすることで,Kasteleyn行列 κ の行列式を利用するこ

とが出来る。■の 不astebyn行 列を翠解するために

,第

2章

では一次独

立

,ベ

ク トル空間の生成

,次

元 といったベク トル空間に関する基本概念

について述べる。 また

,固

有値 と行列式の関係についても基本的な内容

について述べる。また

,第

3章

では

Kasteleyn行

列の行列式の計算等で利

用するため

,数

列に関する定数係数線形漸化式の一般論について述べる。

Kattebyn行

列とは

2部

グラフの各辺に

+1か

-1を

対応させる写像ε

:

グラフの辺 →

_{±1)を

考えて

,こ

のεを用いたⅣ文Ⅳ行列のことであ

る。このε

(瓦

し

)の

符号のつけ方が

Kalsteleyn行

列を決定づける。この各

辺への符号のつ け方 を工夫す ることで

,π

×η長方形の ドミノタイ リン グの総数 Dれ_,π を

Kの

行列式 を用 いて Dπ_,電

_=ldetκ

l と表す ことが出来 るのである。 このことについては第

4章

で詳 しく述べ る。実際

,こ

の εの符号のつ け方は

,グ

ラフの各単位正方形の

4辺

の うち

6 εの値 が

-1と

な るのが奇数 となれ ば よい。 この説 明 には

2部

グ ラフにお け る完全 マ ッチ ングは 「マ ッチ ングの 回転 」 とい う操 作 を通 じて互 い に 移 りあ うとい うこ とが重 要 とな る。 この こ とは

2つ

の完 全 マ ッチ ングの 違 い を「交互 閉路 」 と呼 ばれ るもので表現 す る こ とに よって説 明 され る。 本論文 で は

,2π

×2η長方形 の ドミノタイ リングの総数 D2π_,加 お よび, π ×2η長 方形_{(π は奇数 )の ドミノタイ リングの総数}Dπ_,2れ を与 える一般

式を求めている。また

,最

後には

cos昔

や

COS昔

など

cOsが

計算できる値

第

1章

問題提起

1。

1

ドミノタイリング

｀

とは

本論文で は

,m×

π長方形 の ドミノタイ リングの方法 は何通 りあるか を考 える。 ここで

,自

然数 π,れ に対 して

,π

×η｀長方形 とは

,縦

の長 さ が π

,横

の長 さが ηの長方形 であ って

, 1辺

の長 さが

1の

単位正方形 に 格子状 に分割 されたものを指す。 また

,π

×η長方形の ドミノタイ リン グ とは1×

2長

方形 (以下1×

2長

方形 の ことを ドミノと呼ぶ

)を

縦 また は横 に重 な らない ように並べて

,π

×π長方形 に隙間な く敷 き詰めるこ とである。図1.1に 4×

5長

方形の ドミノタイ リングの一例 を示す。 図 1.1:4×

5長

方形 の ドミノタイ リング 初 め に次 の問題 を考 えた い。 問題

1.1.1図

1.2の よ うな 3×

5長

方形 の ドミノタイ リングはで きるか。 図 1.2:ド ミノタイ リング はで きるか

第

1章

問題提起 この問題 の答 えは 「で きな い」 で あ る。 ドミノタイ リング をす るため には 3×

5長

方形 の

15個

の単位 正 方形 に ドミノを隙間 な く敷 き詰 め る必 要 が あ る。 しか し

,奇

数 個 の単 位 正 方形 に ドミノを敷 き詰 め る こ とは不 可能 だか らで あ る。 よって

,次

の よ うな定理 が成 り立 つ。 定理

1.1.2π

×η長 方形 の ドミノタイ リングが可能 で あ るた めの必要 十 分条件 は

,π

また は ηが偶 数 で あ る こ とで あ る。 証 明 ドミノタイ リング可能 で あ る とす る と

,面

積 ππは偶数 でな けれ ば な らない か ら

,π

また は ηが偶 数 で あ る。逆 に

,mま

た は ηが偶 数 で あ れ ば

,

ドミノタイ リング可能 で あ る こ とは明 らかで あ る。

□ 1。

2

ドミノタイリングの数え方

ドミノタイ リングの数 え方 を具体 的な例 を用 いて説明す る。2×

4長

_方 形の ドミノタイ リングは図1。

3に

示す ように

5通

りである。 この うち_(4), (5)は別の種類 として数 えあげる。 この ように

,π

×π長方形 の ドミノタ イ リングの種類 を数 える際 には

,m×

π長方形 の回転や左右 の反転で重 なるタイ リングも別 の ドミノタイ リング として

,す

べての種類の総数 を 求めるこ ととす る。

田

mm

…

…

図 1.&2× 4長 方形の ドミノタイリング

以下

,π

×η長方形

(π

またはπは偶数

)の

ドミノタイリングの総数を

,m,。

と表す。一般のれ

,π

に対して

,Dπ

,2を

求める手とを解説するのが

本論文の目的であるが

,準

備なしに結論へ至ることは難 しい。そこでま

ずは

,π

を小さな数に固定して

,各

れに対して

Dれ_,れ

_{を漸化式により求め}

る方法を考える。

f5) 14)

第

1章

問題提起 定理

1.2.12×

η長方形 に対す る ドミノタイ リングの総数D2,れ を αηとす る と,α

l=1,α

2=2で

あ り

,ま

た次の式が成 り立つ。 απ==απ_1「■απ_{=2 (η ≧:3)} (1.1) 証 明 α

_l=1,α

2=2は

明 らかである。2× _{η長方形 の左上端の単位正方} 形 に着 目す る と

,こ

の単位正方形 を覆 う ドミノの配置 は

2通

りに場合分 けす ることがで きる。図1.4に示 す ように

,左

上端 に ドミノを縦 に配置 し た場合

,

ドミノタイ リングの総数 はa7n_1に等 しい。 また

,図

1.5に示 す よ うに

,左

上端 に ドミノを横 に配置 した場合

,そ

の下 に点線 で示 した ド

ミノを配置せぎるを得ないので

,こ

の場合のタイリングの総数はαれ

_2に

等 しい。つまり

,漸

化式。ぉ

=%_1+α

η

_2が成立する。

" 哺 ●・ ●● 図 1.4:ド ミノを縦 に配 置 図 1.5:ド ミノを横 に配 置 ここで示 された漸化式を用いて求めた α

2の

値 を表 1.1に示す。 表 1.1:D2,π D2,π

は

,漸

化式や表で分かるようにフイボナッチ数列である

_:D2,れ

の

一般項については第

3章

で紹介する。

定理

1.2.2

α

_π

_=D3,π

とおく。また

,3×

π長方形の左上

1つ

の単位正方

形を除いた領域

_(図 1.6)に

_{対する ドミノタイリングの総数を硫 とすると}

,

α

_l=0,α

_2=3,bl〒

1,b2=0で

あ り

,ま

た次の漸化式が成 り立つ。

απ

=a7n_2+2硫

_1 硫

=α

η

_1+硫

_2(η

≧3) □ ? ら η 1 2 3 4 5 6 7 8 9 10 α π 1 2 3 5 8 13 21 34 55 89 (1.2)

第

1章

問題提起 図 1.6:硫 の タイ リングの領域

― 証明 α

_l=0,α

2=3,bl=1,b2=0は

容易 に確 かめ られ る。 3×η長方形の左上端の単位正方形 に着 目す る と

,

ドミノの配 置 は

2通

りに場合分 けす ることがで きる。図1.7に示す ように

,左

上端 に ドミノを 縦 に配置 した場合

,そ

の下 に点線 で示 した ドミノを配置せ ぎるを得 ない ので

,こ

の場合の タイ リングの総数 は 嶋_1に等 しい。 また

,図

1.8に示す ように

,左

上端 に ドミノを横 に配置 した場合

,そ

のす ぐ下 に ドミノを横 に配置すれば

,そ

の下 に点線で示 した ドミノを配置せ ぎるを得ないので, タイ リングの総数 は απ_2に等 しい

6左

上端 に ドミノを横 に配 置 したす ぐ 下 に ドミノを縦 に配置すれば

,タ

イ リングの総数 は 転_1に等 しい。つ ま り

,漸

化式 αれ

=α

れ

_2+2硫

_1が

成立す る。 図 1.■ 左上端 に ドミノを縦 に配置

図

1.&左

上端に ドミノを横に配置

次に

,図

1.6に

_{示 した 臨 は左端の単位正方形に着目すると}

_,

ドミノの

配置は

2通

りに場合分けすることができる。図

1.9に

示すように

,左

端に

10

一

＼

第

1章

問題提起 ドミノを縦 に配置 した場合

,タ

イ リングの総数 は απ

_1に

等 しい。 また, 図1.10に示す ように

,左

端 に ドミノを横 に配置 した場合

,そ

の下 と上 に 点線で示 した ドミノを横 に配置せ ざるを得 ないので

,タ

イ リングの総数 は 鋭-2に等 しい。つ ま り

,漸

化式 られ

=α

π

_1+硫

_2が

成立す る。

□ 図 1。

)硫

:ド ミノを縦 に配 置 図 1。

lQ硫

:ド ミノを横 に配置 ここで示 された漸化式_(1.2)を用いて求めた αれ

,場

の値 を表1.2に示す。 表 1.2:D3,π 定理 1.2.3 απ=D41π とお く。また,4×η長方形の左上の縦

2つ

の単位正 方形 を除いた領域(図 1.11)に対す る ドミノタイ リングの総数 を 硫

,4×

η 長方形 の左上端

1つ

と左下端

1つ

の単位正方形 を除いた領域 _(図 1.12)に 対す る ドミノタイ リングの総数 を ら

,と

す ると

,al=1,α

2=5,bl=1,

b2 2,Q_1,

(1.3) １ ■ つ エ エ り 成

脚



也

 

０

あ

り

_，

い

い

い

で   一 一   〓   〓

︻

催

η １ ■ ₂ 3 4 5 6 7 ₈ 9 10 α π 0 3 0 １ ■ _{0 41 0 153 0 571} 硫 １ ■ 0 4 0 15 0 56 0 209 0 図 1.11:場 の タイ リング領域 図

1.12:%の

タイ リング領域

第

1章

問題提起 証 明 α

_l=1,α

2=5,bl=1,b2=2,cl=1,c2=1は

_{容易 に確 かめ} られ る。 4×_{η長方形の左上端の単位正方形 に着 目すると}

_,

_{ドミノの配置 は}

2通

りに場合分 けす ることがで きる。 図1.13に示す ように

,左

上端 に ドミノ を縦 に配置 した場合

,タ

イ リングの総数 は 硫 に等 しい。 また

,図

1.14に 示 す よ うに

,左

上端 に ドミノを横 に配置 した場合

,そ

のす ぐ左下 に ドミ ノを縦 に配置すれば

,そ

の下 に点線 で示 した ドミノを配置せ ぎるを得な いので

_,タ

イ リングの総数 はcπ_1に等 しい。す ぐ下 に

2つ

の ドミノを横 に配置すれば

,そ

の下 に点線で示 した ドミノを配置せ ぎるを得ないので, タイ リングの総数 は αη_2に等 しい。す ぐ下 に

1つ

の ドミノを横 に配置 し てす ぐ下 に ドミノを縦 に配置すれば

,タ

イ リングの総数 は 硫_1に等 しい。 つ ま り

,漸

イビ式

%=%_2+bη

-1+銑

_1+bれ が成立す る。 図 1.13:左 上端 に ドミノを縦 に配置 図 1.1生 左上端 に ドミノを横 に配置 次 に

,図

1.11に_{示 した 硫 は左端の単位正方形 に着 目すると}

_,図

1.15に 12

第

1章

問題提起 示す ように

,左

端 に ドミノを縦 に配置 した場合

,タ

イ リングの総数 は απ_1 に等 しい。左端 に ドミノを横 に配置 した場合

,点

線 で示 した ドミノを配 置せ ぎるを得 ないので

,タ

イ リングの総数 は 硫_1に等 しい。つ ま り

,漸

化式 硫

=α

π

_1+硫

_1が

成立す る。 Eヨ 1.15: bπ また

,図

1.12に_{示 した ら は左端の単位正方形 に着 目すると}

,図

1.16に 示す ように

,左

端 に ドミノを縦 に配置 した場合

,タ

イ リングの総数 は απ_1 に等 しい。左端 に ドミノを横 に配置 した場合

,点

線 で示 した ドミノを配 置せ ぎるを得 ないので

,タ

イ リングの総数 は ら_2に等 しい。・つまり

,漸

化式

%=%_1+%-2が

成立す る。 図

1.16:%

□ ここで示 された漸化式(1.3)を用いて求めた απ

,硫

,ら

の値 を表1.3に 示す。 表 1.&D4,れ η 1 2 3 4 5 6 7 8 9 10 % 1 5 11 36 95 281 781 2245 6336 18061 硫 １ ■ ₂ 7 18 .54 149 430 1211 3456 9792 % 1・ 6 12 42 107 323 888 2568 7224 13

第

1章

問題提起 第

1章

では

,Dれ

,れ の うちの

mを

固定 して,D2,π ,D3,π およびD4,れ を ηについての数列 とみて漸化式 を考 えて きた。第

3章

でみるように

,こ

れ らのD2,π_{,D3,π ,D4,れ} に関す る漸化式 は一般項 を求め ることが可能であ

る。 しかし

,m=5の

場合において

,す

で

IF同

様の手法では

,5,れ

の一般

項 を求めることが相当困難である。また

,D2,れ ,D3,η ,D4,π

の漸化式に

類似性等が見当たらず

,こ

のまま

Dれ_,η

の場合へと一般化することは困難

である。

以上のことから

,本

論文ではこの問題に対 して線形代数 とグラフ理論

を用いた,Kasteleynに よる全 く別の解法を考察する。そのために

,第

2

章では一次独立や一次従属

,基

底や次元等の

,ベ

ク トル空間に関する基

礎的な概念について述べる。また

,固

有値 と行列式の関係および

,η

次正

方行列の固有値の個数について述べる。第 3章 では数列における定数係

数線形漸化式の一般論について述べて

,D2,π

および

D3,π

の一般解を求め

る。その後

,第 4章

以降で本論文のテーマである

Kasteleyn行

列を用いた

Dm,π

の値を与える一般式について述べる。

14

15

第

2章

線形代数

2。

1

ベ ク トル空間

以下

,集

合

Kは

実数全体の集合

Rか

複素数全体 の集合

Cと

す る。 また, Kπ とは η個の

Kの

要素の組の集合

,つ

ま り

,Kの

要素 αl,.… ,αれを用 い て_(αl,.…

,%)と

表 され るもの全体 のなす集合である。 ここで

Kの

要素 の組 をベ ク トル といい

,紙

面の都合上, (αl,…・,α とい うよ うに

,横

また は縦 に並べ た形 で表 され るが

,こ

れ らは どち らも 同 じもので あ る。特 に,(0,… 。,0)を

0と

表 し

,零

ベ ク トリレとい う。 この節で は

,一

次独 立

,一

次従属

,ベ

ク トル空間 の生成

,次

元 とい った ベ ク トル空間 に関す る基本的概念 について述べ る。 定義

2.1.1集

合Kπ において

_,次

の

2種

類 の演算 を考 え る。 1.Kπ のベ ク トル

"=(″

1,・ …,″n)と ν=(νl,.…

,%)に

対 して

,こ

れ らの和 を

"+υ

=(″

1+ν

l,.… ,■η tt νη) と定 め る。 2.Kれ

_{のベクトル π=(″}

1,・

…

,″

π

)と

Kの

要素 たに対して

,た

と

"の

積を

たπ=(ん″_1,…。_,λ″ ") と定 め る。 これ を

"の

ス カラー倍 とい う。

第

2章

線形代数

16

定義 2.1.2Kれ の空でない部分集合 ″ が

,次

を満 たす とき

,7を

K上

のベ ク トル空間 とい う。´

1.″

の任意 のベ ク トル π,υ に対 して

,"十

_{υが ″ の要素である。}

2.″

の任意 のベ ク トル

"と

Kの

任意 の要素 たに対 して,た

"が

″ の 要素である。 特 に

,lK=Rの

ときは ″ を実ベ ク トル空間

,K=Cの

ときは ″ を複素 ベ ク トル空間 とい う。 例 2.1.3Kれ は

K上

のベ ク トル空間である。 また

,零

ベ ク トルのみか ら なる集合

_{0}も

K上

のベ ク トル空間である。 一般 に

,Kれ

のベ ク トル αl,.…

,Omの

スカ ラー倍 の和

C101+―

・

_+%.Om(Cl,…

。

,%∈

K)

を αl,.… ,α

mの

K上

の一次結合 とい う。 一次結合 に関 して次の定理が成 り立つ。

定理 2.1.4 Kπ のベ ク トル αl,.…

,amに

対 して,ol,.・

.,amの

K上

の一

次結合全体 の集合 を

″

_={C101+…

十

%α

π

lCl,・

…,%∈ K}

とお くと″ はKれ 内のベ ク トル空間 をなす。 証明 ″ のベ ク トル π,υ に対 して π

_=C101+・

…

+%α m(Cl,一

,端

∈

K)

ν=Jlall十・…

+輛

π (al,.… ,αれ ∈

K)

とす る と

"+ν

=(Cl+α

l)o.+…

・+((‰ +dm)al協 とな り

"+υ

は

7の

要素 で あ る。 また

,″

のベ ク トル π

,Kの

要素 の た に対 して λ

"=た

clol+…

・

+た

Cm%

とな り ん

"は

″ の要 素 で あ る。 したが って

,7は

K"内

のベ ク トル 空間 で ある。

□

第

2章

線形代 数

17

定義 2.1.5 Kπ 内のベ ク トル空間 ″ と

,″

内のベ ク トル αl,… .,αれに対 して

″

={C101+・

・

・十

%α

π

191,...,端

∈K}

である とき,ol,.…

_,omは

Kを

係数 として ″ を生成す る といい ″″

=(01,…

。,αm) と表す。 定義 2.1.6 Kη のベ ク トル αl,.… ,αれに対 して Clα_l+。 …十

%β

7m=0(Cl,.…

,端

∈

K)な

らば

cl=…

.=%=o

が成 り立つ とき,01,.… ,απは

K上

一次独立である とい う。 定義 2.1.7 Kη のベ ク トル αl,.… ,απが

次

独立でない とき

,す

なわち, 少な くとも

1つ

は

oで

ないcl,.…

_,端

∈

Kに

対 して C101+・ …

+Cttam=0

が成 り立つ とき,01,.… ,0れ は

K上

一次従属であるとい う。 一次独立に関 して次の基本性質が成 り立つ。 定理 2.1.8Kれ のベ ク トル01,。 _…,αれが

次

独 立な らば

,そ

の一部分 も 一次独立である。特 に

,各

αを(を

=1,…

。,π)￨ま零 ベ ク トルではない。

証明

α

l,.…,Cれ

の一部分

aを_{11..,o,T(1≦}

づ

1<…

・

<tr≦

m)に

対して

:

Q10,1+…

・十

Qra`r=0

とす る。 この左辺 に π 一

r個

の零 ベ ク トル 0%(プ は '1,.… ,づ

r以

外

)を

加 える と

,π

個 のベ ク トル01,。 _…

,Omの

一次結 合 が零 ベ ク トル にな る。 し

たがって

,al,.… ,a鳥

の一次独立性より

,一

次結合の係数のスカラーはす

べて

0に

なる。よって

,Ql,.… ,Qrも

0で あり。すなわち

,0.1,.… ,° '7は

一次独立である。

また

,こ

のことより

,特

に

_,各

_{αぅも一次独立となる。}

_1個

のベク トル

αが一次独立であるのは

,α

_{≠0の ときであるから}

Q≠

0で

ある。

□

ｍ α で                 α_２

わ

社

 

 

 

 

た傷

０ す         ∈ ≠ と         ｂ_２

る。



ｂｌ∈＜



 

 

。ｂ・

_ψ

，

 

 

 

 

れ

き             る   っ         り り

誨

 

訓

 

 

け

い

 

 

電

蹴

第

2章

線 形代 数

18

定理 2.1.9Kれ のベ ク トル αl,…

.,Omお

よび,bl,.… ,り に対 して,bl,.…

,L

は一次独立であ り

,か

つ,bl,.… ,毎 ∈(01,…

.,Om)な

らば

,r≦

π である。 また

,こ

の とき αl,。 …,αれの中の適 当な

r個

(仮に,ol,.… ,arとす る₎ をbl,.…_,brで置 き換 えて

・ (01,・ …,απ

)=(bl,…

.,い,ar+1,.… ,απ)

b2=αlbl+あ

α2+・ …十 αmalπ

と表せる。

bl,b2の

一次独立性より,b2≠ α

_lblで

_{あるから,ぁ}

_,… .,鋭

の

うち少なくとも

1つ

は

0で

_{ない。仮にあ≠}

0と

すると

α

2==( 分

)bl+去

b21( 劣

)03+…

・

十

(一 :昔

)bm

つ ま り (01,02・ …:α

m)=(bl,02・

…,αm)=(bl:b2,03,。 …,alm) 以下

,同

じ操作 を繰 り返 して

,o3を

b3で

,04を

b4で ,… 。

,と

順 に置 き 換 えてい くことを考 える。 この とき

,も

し

r>mな

らば

,端

を

bmで

置 き換 えた ところで

｀ (01,.… ,αm)=(bl,・ …,bm) を得 るので

,LⅢ

l∈ (bl,.… ,bれ)とな り bれ

_+1=λ

_lbl十・…+λ_πbπ

第

2章

線 形代数

19

と表せ る。 これ はbl,.…

_{,現 ,端}

_+1の一次独 立性 に矛盾 す る。つ ま り

,r≦

%で

あ る。 よって (al,.… ,αm)=(bl,・…,り,ar+1,.… ,αm) が成 り立 つ。

□ 次 に基底 と次元 について定義 して

,Kπ

の基底 を構 成 す るベ ク トル の個 数 につ いて述 べ る。 定義 2.1.10 Kη 内のベ ク トル空間 ″ を考 える。″ 内のベ ク トル αl,。 …,αれ が次 を満 たす とき,ol,.…

,Cmを

″ の

_(K上

の

_)基

底 とい う。 1.ol,1… ,αれ は

Kを

係 数 として

7を

生成 す る。 2.αl,… .,aれ は

K上

一次独 立 で あ る。 例 2.1.1■ Kれ の要素 el=(1,0,… 。_,0) e2=(0,1,… 。_,0) Cη _{=(0,… 。,0,1)} をKπ の基 本ベ ク トル とい う。 基 本 ベ ク トルel,.… _,cれ がKπ の基底 で あ る こ とは容 易 に確 かめ られ る。 定理

2.1.12Kれ

のベク トル αl,… .,αれが基底 な らばKれ の任意のベ ク ト ル

"は

ol,… .,αれの一次結合 として

,た

だ

1通

りに表 され る。 証明 基底 の定義 によ り,ol,.… _,armはKれ を生成す るか ら

,任

意 の “∈ Kπ は

"=91ol+…

・十

%β

π (cl,…。

,端

∈

K)と

表 され る。仮 に,

"=C101+…

。

+ら

2a暁

=αlol+…

・

+塩

αれ (al,… .,d蹴 ∈、

K)

と

2通

りに表 された とす る。 この とき

第

2章

線形代数 とな り

,α

l,…

.,Omは

一次独立であることか ら,

Q一

銑

=0(を

=1,…

.,π₎ が得 られ る。つ ま り

,Q=銑

(づ

=1,…

。

,m)で

あ り表示 は一意的である。 □ 定理 2.1。13 Kπ 内のベク トル空間 ″ について

,7の

K上

の基底 を構成 す るベ ク トルの個数 は基底 によ らず一定である。 証明 ol,。 _…,Crお よび,bl,.… ,bsをベ ク トル空間 ″ の

2組

の基底 とす る。bl,.… _,bsが一次独立であ り

,か

つbl,.…_{,b3∈ (al,.…}

_,Cr)=″

で あるか ら定理2.1.9よ りs≦

rで

ある。

一方,ol,.… ,arが一次独立であ り

,か

つol,.… _{,ar∈ (bl,…} 。

_,bs)=″

であるか ら定理2.1.9よ りr≦

sで

ある。 したが って

,r=sで

ある。 □ 定義 2.1.14 Kπ 内のベ ク トル空間 ″ の

K上

の基底 を構成す るベ ク トル の個数 を ″ の

K上

の次元 とい う。″ の次元が

mの

とき

,″

はK tt m 次元のベ ク トル空間であるといい

dimK″

_=π

と表す。特 にKれ の基本ベ ク トルel,.… _,eれ はKπ の

1つ

の基底であるか ら

,構

成す るベ ク トルの個数 は れであ り dimK Kπ

=π

である。 2。

2

線形写像

定義

2.2.17と

″ を

K上

のベクトル空間とし

,∫

を

yか

ら″ への写像

とする。アの任意の要素

",υ

,お

よび任意のた∈

Kに

対して

,写

像∫が

次の2式 を満たすとき

,写

像∫を

K上

の線形写像という。

∫("+ν )=∫

(")+∫

(υ)

∫

(た

_")=た

ノ

(■) 20

第 2章

線形代数

21

定理

2.2.2ノ

が

Kπ

から

Kπ

への線形写像のとき

,あ

るα

_″∈

Kが

あって

,

任意の″

1,.… ,″

π∈

lKに

対 して

,次

の式が成 り立つ。

証明

α

_l,.… ,α

れを∫による基本ベク トル

el,.… ,cη

の像 として

∫

(el)=a71

ノ

(Cη)=alπ

とおく。また,Kれ の任意のベク トル

"=(■

1,・

…

,%)は

,Kり の基底であ

る基本ベク トル

el,.… ,cれ

を用いて

, π

_=π

_lel+…

。

+″

nen

と一意的に表される。このとき

,線

形写像∫によるπ

=(″1,…

。

,″

η

)∈ Kπ

の像は

ヽ ｌ ︲ ︲ ′ ノ ¨   一     ＋       ¨ ．_︰   一 一 一   一 一       一 一           〓 π ∫ □ ‐

_となる。

２２   ∫ り よ こ ２ ２ ２ 理 定 写     十     ＋   ¨     一

へ

の

線

形

饉

伊

Ｍ

 

ｌ

〓

 

〓

れ

 

ｔ

舜

 

義２

_．

げ

第   定 は

と表される。このとき

とおくと

∫

(2)=A"

となる。このスをノを表す行列という。また逆に

,ノ

を

_4が

表す線形写

像という。

定義

2.2.4ノ

が

Kη

から

Kれ

への線形写像であるとき

, Im∫

_={∫

_(a)∈

Kmlα ∈

Kη_}

｀

_Kerノ

_={α

_∈

_Knl∫

(a)=0}

をそれぞれ∫の像

,∫

の核という。

Im∫

,Ker∫

がベクトル空間となるこ

とは容易 に確 かめ られ る。 列式 を det五

_=￨ス

_￨=

α_{ll ...} αlπ απl ... αη " な どと表す。 なお

,行

列式の定義 は既知 として扱 う。詳 しくは例 えば₁₂₁ を参照の こと。

第

2章

線形代数 並べ た行 列 を

と表す。

定理

2.2.5Kれ

から

K鯰

への線形写像ノを考える。またノを表す行列をス

とおく。このとき

,∫

に関する次の5つ の条件は互いに同値である。

1.∫

は単射でない。

2.Ker∫

_≠

_{0} 3.∫

は全射でない。

4.ス の行列式detス

=o

5.ス _=(ol・ ..αη)とす る とき

,01,.…

,α_πは

次

従属である。 証明 以下

,1と

2と

5の

同値性 を示す。3と

4の

同値性 お よび

,1,2,5と

3,4の同値性 は

,行

列の基本変形等 を使 って説明 され るが

,長

くなるので ｀ 省略す る。例 えばp]を参照 されたい。 1と

2の

_{同値性を示す。ノは単射でないとすると}

_,あ

る

",υ

∈

Kれ

に対

して

∫し

)=∫

し

)

かつ

"≠

ν

である。よって

, ,

ノ(a)_∫

(ν

)=0

ノ

("一

υ

)=0

つまり,"― υ≠

0は

Ker∫

に属する。逆に

_,Ker∫

_≠

_{0}と

すると

,oで

ないπ∈

Kれ

に対して

∫

(")=0

∫

(0)=0

また,電個 の縦 ベ ア﹂ 横 を

５

∈ ヽ ｌ ︲ ︲ ︲ ′ ノ

％

 

。・

 

端

／ １ ︲ ︲ ｌ ＼ ヽ ｌ ︲ ︲ ′ ノ 〓

％



 

 

 

_鮎

・

︰

 

嚇

ハ﹁

・ ︲

_﹁

・ ′

_り

 吐

 ・︰

 喘

／ ｆ ｉ ︲ ｌ ＼ ／ ｆ ︲ ︲ ｌ ＼ 〓 一 一         ＞ η

Ｑ

 

 

 

 

 

 

α

レ             ・ ｋ ｒ                   ｌ ０ ク           く

第

2章

線形代数

24

よつて

,∫

_(")=バ

0)な

ので

,∫

は単射でない。

次に

2と

5の

同値性を示す。

Ker∫

_≠

_{0}と

すると

,0で

ない

Kerノ

の元

"が

存在する。 この

"に

ついて

∫

(・

)=0 (2.1)

∫

(・

)=ス

π

″_{101+・… 十 ″鯰απ}

=0

と く お と ヽ １ ︲ ｌ ノ

ａ

・

︰

 

ち

／ ′ ︲ ︲ １ ヽ 〓 π て し と れ α α 〓 五 方 一 つ 工 立 り 成 カ

０

 

 

 

 

 

コ

 

れ

↓ ｏ 紛 ヽ ｌ π

∩

Ⅲ

ぶ

︱

脚

ル

０

１

・

・

＋

α

︰

¨

一 一         一 一         〓

さ

れ



る

_。

 

り

_，

_れ

ま

た

﹄

︻

表     な あ 逆 ¨ と         と で     ”

第

2章

線形代数

である。よって

_"=

ノし

)=0か

つ

_"≠

0

25 □

ことが分かる。

ヽヽ、 ．．．．_． ． ．・・_・・ ・ ・ ，日 ，コ●_・・ ・ ′ ′ ′ ”′_︵ ¨_︶           ・

︱

動

とお くと (2.2)の 式変形 を逆 にた どる こ とで, 定理2.2.5は次の固有値 ・固有ベ ク トルの節で利用す る。 2。

3

固有値 口固有ベ ク トル

以下

,複

素数 を成分 とす る行列やベク トル を扱 う。つ ま り

,断

らない限 リベ ク トル空間 は

C上

のベ ク トル空間である。 定義

2.3.1複

素数 を成分 とす る η次正方行列 ス と λ∈

Cに

対 し

,あ

る

"∈

Cπし ≠

0)が

存在 し, ス

"=λ

"

を満たす とき,λ をスの固有値 とい う。 また

,固

有値 λに対 し

,ス

π

=λ

π を満たす

0で

ない

"を

スの固有値 λに対す る固有ベ ク トル とい う。なお,

"が

ス の固有値 λに対す る固有 ベ ク トルであるな らば

,"の

スカ ラー倍 もまた_{(0でない限 り)同 じ固有値の固有ベク トルであることに注意する。}

定理 2.3.2複素数を成分とするπ次正方行列スに対し

,λ

∈

Cが

■の固

有値であるための必要十分条件は

,det“

―λ

E)=0と

なることである。

証明 λ∈

Cが

スの固有値であることと

,0で

ないある

"に

対 して ス

"=

λπ となることは同値 である。 それ は また

,(■

― λ

E)"=0で

あ るこ と と同値であ り

,行

列(五 一人

oが

表 す線形写像 によってCれ の要素 π≠

0

が

0に

対応 していることである。つ ま り

,定

理2.2.5の 2と

5の

同値 よ り, det(ス ー人

E)=0で

ある。

□ 定理 2。3.3η 次実正方行列 スにおいて

,ス

の固有値 λが実数の ときは,λ に対す る固有ベ ク トル として実ベ ク トル

"が

存在す る。

証明

定理

2.3.2よ

り

_,detに

一人

E)=0で

ある。このとき

,“

―λ

E)は

実行列なので

,に

一人

E)が

表す

Rπ

から

Rπ

への線形写像∫が考えられ

る。定理

2.2.5よ

り

,ノ

は単射でない。よっては一人

E)"=0と

なる実ベ

クトル

第

2章

線形代数

26

定義 2.3.4η 次正方行列 ス に対 して

,未

知数 λに関す る方程 式 det(五 一人

E)=0

を スの固有方程式 とい う。 定理

2.3.5複

素数 を成分 とするπ次正方行列 スの相異なる固有値 λl,.… ,λた∈

Cに

対す る固有ベ ク トル "1,…_,πたは

C上

一次独立である。 証明 この仮定のも とで "1,.… ,π.(づ

=1,…

.,λ)が一次独立があること を自然数 りについて数学的帰納法で示す。 1).づ

=1の

とき

"i≠

0な

ので

,cl"1=0と

すれ ば

cl=oと

な り

, 1

つのベ ク トル πlは一次独立である。 したがって

, `=1の

とき命 題 は成 り立つ。 2).づ

=π

_{(1≦ π ≦ ん}

-1)の

とき

,"1,…

。,"π は

次

独立である と 仮定す る。 づ

_=π

■1の とき,cl,.… ,端 ,%Ⅲl∈

Cに

対 し Cl"1+・ …+C稀 “

m+C抗

+lπ為

+1=0 (2.3)

とお く。 両辺 に左 か らス をか ける と c14"1+・ …

+%五 %+C抗

_+1■

%+1=0

clλl■1+・ …

+%λ

m鶴

+%+lλ

m+β

れ

+1=0 (2.4)

を得 る。 一 方,(2.3)に λπ+1をか ける と clλ

m+1"1+・

…十

%λ

_π

_+βm十

_%2+lλπ

_+β

_れ

+1=0 (2.5)

とな り

,(2.5)か

_{ら (2.4)を ひいて} Cl鰺

π

_+i一

人

1)“1+。

…+%バ λ

π

+1 入

れ

)"π

=0

を得 る。 この とき

,"1,…

。_,"れ は

次

独立なので

′

Cl(λ

_m+1-λ

l)=・

…

=ち

_よλ

m+1-λ

m)=0

であ る。 また

,固

有値 は互 い に異 な るため

Cl=…

・

=%=0

｀

第

2章

線形代数

27

とな る。 これ と_(2.3)よ りQπ+1“れ

+1=0で

あ り

%叶

1=0と

なる。 よって

,■

1,… .,"π

+1は

一次独立である。 したがって

,=m+1の

ときも命題 は成 り立つ。

1),2)よ

りづ

=た

の ときも命題 が成 り立つ。 □ 定理 2.3.6η 次正方行列 スの固有値 は

,複

素数の範囲で高々η個存在する。 証 明 λOを スの固有値 とすると,λ。は固有方程式detに一人

E)=0の

解 である。 この スの固有方程式 は行列式の定義 よ りλの η次方程 式である。 ここで ス の固有方程 式が仮 に複素数 の範 囲で η

+1個

の解 を持 てば

,因

数定理 よ リスの固有方程 式が λの 場

+1次

以上の方程 式 とな り矛盾 する。 よって

,ス

の固有値 は

,複

素数の範 囲で高 々η個存在す る。

□

定義 2.3.7複 素数係数の多項式 ∫

(π)に

ついて

,ノ(″

)=0が

α∈

Cを

解

に持つとする。すると

,ノ(■)は

少なくとも

1回 (■

―α

)で

割 り切れるため

∫

(″

)=(″ 一α

)30(″

)(S≧

1)

と表せる。∫

(″)は

有限次だから

,sは

いくらでも大きくはできない。よって

∫

(″

)=(″ 一α

)30(″

)(S≧

1)か

つ 0(α

)≠ 0

となる自然数 sが存在する。このときの

sを

解 αの重複度という。

定義

2.3。

8複

素数係数の多項式∫

_(″)の

解のすべてをλ

_l,λ2,…

。

_,λrと

し

,

それぞれの重複度を

sl,.… _,Srと

する。このとき∫

_(■)は

重複度を込めて

Sl+・

…

+Sr個

の解をもつという。このとき

,∫_(・)は

ノ

(″

)=(″ 一人

1)'1・

…

(″

一人

r)Srg(・

)(′

(″)は

多項式

)

と表せる。ここで

,(■)が

定数でないとすると

,代

数学の基本定理により

,(″)も

また解をもち

,新

たな∫

(″)の

解が存在して矛盾するから

g(■)は

定数

(α

とおく

)で

あり

, .

∫

(・

)=α

(″

一人

1)31.… (″

一人

r)Sr

と表される。このとき

,λ lを sl個,λ 2を s2個,…

。

,λrを sr個

書き並べたリ

ス トがα

l,α2,・

…

,α

πであるとき

,∫(″)の

解は重解度を込めてα

l,α2,∴

。

,α

π

であるという。

第

2章

線形代数

28

定義2.3.8か ら

,次

の定理 が成 り立つ ことは明 らかである。 定理 2.3.9π 次正方行列 ス の固有値 は重複度 を込めて η個存在す る。 定理 2.3.10η次正方行列 スの固有値 を重複度 を込めて λl,λ2,…・,λπ∈

C

とす る とき

,次

の式が成 り立つ。 λlλ2・ …λπ

=det五

証明

η次正方行列

Aに

対して固有方程式

det“

―λ

O=0の

解を重複度

を込 めて λl,λ2,・ …,λη とすれ ば

,定

数 αを用 いて det(■ ― λ

E)=α

_(λ ―λl)(λ 一 人2)°…(λ ―λπ) とな る。ληの係 数 を比較 す る と α=(-1)れ が得 られ det(ス ーλ

E)=(-1)η

_(λ ―λl)(λ ―λ2)… °(λ 一人π) =(λl― λ)(λ2二 λ)… °(λη一 人) イ サ は

10祠

サ AIA2・・・為 とな る。 この式 は 人に関す る恒等 式で あ るか ら λ

=0と

お くと λlλ2・ …λη

=det 4

が得 られ る。

□

29

第

3章

線形漸化式の一般論

第

3章

で は数列 における定数係数線形漸化式の一般論 について述べて, D2,π およびD3,れ の一般解 を求め る。 また

,定

数係数線形漸化式の一般論 については第

5章

のKasteleyn行列の行列式の計算で も利用す る。

3.1

定数 係 数 線 形 漸 化 式

以下

,数

列

{αn}と

は

{α l,α2,…

・

}と

いうようにα

lを

初項とするものと

する。

定義

3.1.1複

素数列

{α

π

}に

関する

,次

の形のπ

+1項

間の漸化式を定

数 係数線形漸 化 式 とい う。 αη

=PメL_1+…

。十 民ηαπ

_m(Pl,…

。

_,端

∈

C,端

_≠0) 以下

,定

数係 数線 形漸 化 式 を単 に線形漸 化式 とい う。

定理

3.1.2線

形漸化式α

π

=Pl%_1+…

・十島ρη_m(Pl,… ・

,鳥

∈

C,端

_≠

0)を

満たす

2つ

の数列

_{{%},{硫 }に}

対して

{ん

α

π

},{%+硫

} も同 じ線形漸化式 を満たす。 ただ し,た ∈

Cは

定数 である。

証明 {%}が与えられた漸化式を満たすとき

,漸

化式の両辺をた倍すると

んα売

=Plん

απ

_1+…

・十 鳥れたαη_π

となり

,{た

α

π

}も

同じ線形漸化式を満たす。また

,{硫

}も

与えられた漸

化式 を満たす として, 硫

=Pl硫

_1+…

・

+島

ι硫

_m

第

3章

線形漸化式の一般論

とすると

,{α

π

_)と {硫

}の

満たす式の和は

(απ tt bη

)=Pl(α

η

_1+硫

_1)+…

。十島 (αη

_m十

硫_π)

となり

,{α

η

+硫

}も

同じ線形漸化式を満たす。

□

定理

3.1.3数

列

_{α

月

}が

線形漸化式α

η

=Plα

π

_1+… +鳥

ρπ

_π _(Pl,…

。

_,端

C,端

_≠

0)を

満たすとき

,任

意の自然数ηについて

30 αη+π απ+m-1 : %+2 arπ₊₁

PI P2 -・

f猛二

_lf為

1 0

_{。… …}

. 0

0 0 αれ十れ-1 αη+π-2 : απ+1 απ が成 り立つ。 証明 行列で表 された式の右辺 を計算す る と Plα

_η

_+π_1+。

…

+ILα

_η

αη+π-1 αη+2 απ+1 とな り

,左

辺 のベ ク トル と成 分 が等 しい。 よって

,与

え られ た式 は成 り 立 つ。

□

系

3.1.4数

列

{α

π

}が

線形漸化式α

れ

=Plα

η

_1+…

+昇

ρπ

_m(Pl,…

.,端

∈

C,島

_≠

0)を

満たすとき

,4=lo l

・

・

・

PI P2

…・ 島

-11%

1 0

。_{… …}

. 0

が成 り立つ。

第

3章

線 証 明 定理 定理 3.1.5 ■

=

の固有 方程 となる。 証明 定義 よ り

,固

有方程 式は未知数 πに関 して 31 □ ある。 で

一般論

朔

列

の 一 

 

朗

 

桁

却

 

的

 

訪

ば 脚 Ｅ 鳥 ０   ・ １ ・ イ       Ｉ       Ｋ

潮

 

・

︲

・

３

畝

・

・

０

・

︰

出

励 ３ ．︲   ｍ ″ ︱︱ ︱︱ し 劇 耽 ０ ０ ⋮ ０ ″ 一

∈

C,端

_≠

0)

=0

と表 され る。 行 列 式 の定 義 に従 って計 算 す る と det(″

E―

■)=(″ 一Pl)″

m_1-(一

P2)( 1)π

m_2+.…

｀

+(-1)m_2(二

f猛_1)(-1)π 2″

+(_1)π

1(一J机_)(-1)π 1 =″れ一

Pレ

π1二

P2Zm-2_…

。

_端

_1,一 端

=0

とな る。 つ ま り固有 方程 式 は ππ

=Pl″

π1+。 …

+島

とな る。

□ 定義

3.1.6線

形 漸 化 式 απ

=Plα

η

_1+…

。

+鳥

ρπ_π _(Pl,… ,」‰ ∈

C,端

≠

0)に

対 して

,未

知数 ″に関す る方程 式 ″π

=Pl″

m_1+・ …

+島

_、 を線形漸 化式 の固有方程 式 とい う。 det(″

E一

■

₎₌

″

Pl P2 P3

…。

f机

_1

-l o O .…

….

0 -l

π

.…

_…. 三

°・

.-1

″

0

。…

.…

0 -1

島 _1 0 1 32 耽 ∈ は λ (3.1) ” ・ヽヽ １１ １１ １１ １１ １︰ ′′ ′ ｒ ” ⋮ λ ｌ 饂 ρ ｌ ｌ ヽ

第 3章

線形漸化式の一般論

定理 3.1.7線 形漸化式 α

π

=Plα

π

_1+…

・十鳥ρれ

_π

C,端

_{≠ 0)の 固有方程式の解の 1つ を λ∈}

Cと

する

_￨

´



 

 

 

辟

_﹂

 

﹄

に         証 ハ ｗ     ”   件

鳥

０

１

・

_・

_．

一

■

１

０

・

︰

０

である。 つ ま り λπれ

=Plzm+…

。

+鳥

p″1 λ″π

_1=″

れ λ″れ

-2=″

π-1 λ″

_2=″

3 λ″

_1=″

2 ″

_,=λ

_{' 1(づ}

_=1,…

。

_,m)

となる。 ここで

第

3章

線形漸化式の一般論 とお くと

,上

の式の うち (3.1)以外 は明 らかに成 り立つ。 有 方程式の解 であるこ とか ら λπ

=Plλ

π 1+・ …

+η

嵩_λ

+FL

であ り,(3.1)も成立す る。

_?ま

り 33 また,λ が固 ヽ １ ︲ ︲ ︲ ′ ノ

け

⋮

λ

ｌ

λ ／ ｆ ｉ ｌ ト ー ヽ 〓 “ は固有 ベ ク トル で あ る。 定理

3.1.8線

形漸化式 αη

=Plα

π

_1+…

・

+鳥

メ "_れ の固有 方程 式の解 が

,互

いに異なる π 個 の解 λl,.… ,λれをもつ とき

,線

形漸化式 をみたす 任意 の数列{arn}は

,あ

る

o,…

。

,銘

∈

Cを

用 いて

α

η

=σ

lλ

l"+…

・

+Cmλ

ml

と表 され る。 証 明 線形漸化式の固有方程式 ″

m=Pl″

π

1+…

・

+ら

の解 を λl,.∴ ,λπ とす る。す る と

,定

理3.1.7よ り

,固

有値 λl,.… ,入れに対す る

,

PI P2

_{…・ 島}

-1』

‰

1 0

_{。… …}

. 0

0 1

・_・

_.

_三 三 ・・. ・・

. o o

O

。∴

0 1 0

の 固有 ベ ク トル はそれぞれ となる。 これ らの ス の固有ベ ク トル は定理2.3.5よ り

C上

一次独立であ る。 よって

,ス

の固有 ベ ク トル は π 個 の一次独立な

Cmの

ベ ク トルであ

４ ３ ヽ ｌ ︲ ︲ ＝ ｌ ノ ¨         よ                         ＋ ・           よ る れ さ ３   か               な                                                             表 第   る                 と                                                                         と □ が成 り立つ。

第

3章

線形漸化式の一般論 3。

2

固有値が重解 となるとき

定理3.1.8では線形漸化式の固有方程式がすべて異なる解 をもつ ときを 扱 った。 この節で は固有方程 式が重解 を持 つ ときを扱 う。実多項 式の解 が重解度 たとなるための条件 を与 える次 の定理は よく知 られて お り

,高

校 の数学の知識 でも証 明で きる。

定理 3.2.1実 数係数の多項式 ∫

(■)に

対して

,∫(・

)が実数 αを重複度 ん

の重解に持つための必要十分条件は

,次

の式が成 り立つことである。

{郊

8琳

件≒十⇒

ここで は複素数 を用 いた固有方程式 を考 えてお り

,上

の定理 を複素数 に拡張 したい。複素係数の多項式でも解析学的な微分 は考 え られるが

,準

備 が大変である し

,ま

た

,解

析 的性質 はここでは必要 はない。 そ こで形 式的微分 とい う概念 を用 いて考 える。

定義 3.2.2複素係数多項式∫

(■

)=2′

十

%_1■

π

1+…

_°

十

p。

に対して

, Dノ_(″

_)=町

_L″

π1+(η -1)λ

_1″

π

2+…

。

+ン

2Z+pl

と定める。

D∫_(■)を

_ノ

_(″)の

形式的微分という。また

,多

項式 ∫

(π)に

対

して

,そ

の形式微分をとる操作をた回行ったものを∫

(■)の

た階形式的微

分といい,Dた ノ

(■)と

書く。

定理 3.2.3複素係数多項式∫

(■),g(″)に

対して

,以

下が成 り立つ。

1・ D(∫_(″)+g(・

))=D∫

_(・

)+Dg(・

₎ 2.D(α

_∫

_(・

_))=α

_(D∫(・

_{))(α ∈}

_Cは

定数

)

3.D(が ×ノ

_)=(D″

を

_)Xノ

+″

_`X(Dノ

_)(り,プ

は非負整数

)

4.2(ノ

_(・)g(″

_))=(D∫

_(・))g(・

_)+∫

_(・)(Dg(・

_{)) _}

5.Dλ_{(∫ (″)g(″}

_))=Σ

_担。

ん

_C(D:∫

_(″))(Dたう

θ

(・)) 。_(π 一λ+1)(″ 一α_)れ λ _(ん

<m)

) 35

第

3章

線形漸化式の一般論

36

証明

定義通り計算すれば確かめられる。詳しくは

p]を

_{参照されたい。}

□

以下において

,多

項式の形式的微分に数を代入することを考える。そ

の際

,多

_{項式 ∫}

(″)と

α∈

Cに

ついて

Dを

∫

(α)と

表記するときは

,∫(″)の

を階形式的微分に″=α を代入した値を表す。

_(つ

まり

,初

めにノ

(■)の

形

式的微分を求め

,そ

の後に″=α を代入する。

)

定理 3.2.4複 素係数多項式 ∫

(■)に

対 して

,∫(″

)が複素数 αを重複度 た

の重解に持つための必要十分条件は

,形

式的微分

Dに

関して

,次

の式が

成 り立つことである。

{:鵜

已

10=嘔

λ

⇒

(3.2) (3.3)

証明

複素係数多項式∫

(″)が

複素数αを重複度んの重解に持つとすれば

∫

(″

)=(″

一α

)ん

の

(・

)か

つ

の

(α)≠ 0

となる。∫

(■)の

を階形式的微分を考えると

D。

_バπ

₎

=Σ

_]・GDJ{(・

―α

)た}D' JO(■

)(j=1,…

。

,た

-1)

J=0 =(Z一 α_)たD'0(″ )+`Dl{(π 一 α_)た}Dを 10(■_)+… ・_{+Dう {(π}一 α_)た}0(・) (3.4) とな る。 ここで で       は

し 

 養

  

り立っ。

_岬

Ｄ     か       成 一 だ       が し

第

3章

線形漸化式の一般論

37

が成 り立つ。 逆 に,(3.2),(3.3)が成 り立つ と仮定す る。 この とき,∫(・)を (″ ―α)た で割 った商 をo(″

),余

りをR(″

_)=α

lZた

1+α

2メ

2+…

.+αたとすれば

、 ∫(″

)=(″

一a)た0(″

)+R(″

) (3.5)

と表 させ る。_(3.5)の両辺の づ階形式的微分 を考 える と Dう_∫(・

)=Σ

]づGDι{(″ -9)た}D` JO(π

)+Dづ

R(・

) (3.6)

J=0 とな る。 (3.2)を 仮定 したので,(3.6)よ り D.R(α

_)=0(づ

=1,…

・,ん

=1)

とな る。 よって R(・

)=0

つまり

,∫_{(")は (π}

一α

_)ん

で割 り切れ

,∫_(″

_)=(・

―α

)・0(π)と

なる。一

方

,(3.3)も

仮定 しているので

Dた

_ノ

_(α

_)=λ

!0(α_{)≠ 0}

より,o(α

)≠

0で ∫

(″)は (″

一α

)た

+1で は割 り切れない。

□

複素係数多項式 ∫

(3)に

ついて

,∫(■

)=0の

解の重複度を調べるための

定理である定理

3.2.4が

準備できたので,こ れを用いて固有方程式が重解

をもつ場合について述べる。

以下

,″

の多項式

_{Q(■ )を}

,%(■

_)=″

πとおく。

定理 3.2.5複素数 民

(島

=1,… 。

,π)に

ついて

,線

形漸化式

%=Plα

π

_1+…

・

+民

η

α

れ

_π _(た

だし

,端

_≠

0) (3.7)

列 数 の 個                 ・ ん                   科 の                       叶 次                 ｐ ２

つとき，



   

  ¨

主 Ｄ   。                     ′ ・ ︲ 、

の

重

_﹄

解

︲

こ

 

 

ば



い

た の       一．   一       η

か

_﹂

鰈

瞬

砕

﹂

_肥

有 ｌ

錮

響

第

3章

線形漸化式の一般論 証明 線形漸化式(3.7)の固有方程 式

″π

_=Pレ

π

1+・

…

+島

が 入を重複度 たの重解 として持つとする。ここで

,

∫

(″

)=Plπ

π

1+。

…十島

とおくと

,定

理

3.2.4よ

りλは

%ズ

λ)=ノ

(λ )

Dl%(λ

_)=D∫

_{(λ )}

D2%(λ

_)=,2∫

_{(λ )}

D卜

1%(λ

_)=Dた

1∫_{(λ )} 38 (3.8) を満 たす。0≦ _{π ≦ ηの とき}

,%(″

_)=偽

_π_{(・)cm(″)な}ので づ=0,1,.… ,た

-1に

対 して

,(次

の式 で はQ(″)等の(″)を 省 いて書 く)

,0%=D.(%_π

_%)

￨

=Σ

ぅ

Q(D2 t功

(D′

%)

′=0

は恒等式である。数列

{α

9}を

α

∬

)=Dを

%(λ )と

おくと

,π

>π

となるη

に対 して

α

_∬

)=Dを

_硫

(λ )

=Σ

づ

Q(ノ

→

%―

協

ひ

D(ノ

%0))

′=0

第

3章

線形漸化式の一般論 となる。_(3.8)よ り

α

_9=Σ

_を

_の

_(ノ

→年π

_ttD(ノ

_∫

pD

J=0 0

=Σ

を

_{Q(D' Jら}

_れ_{似 ))(■}

Dセ

猛

_10)十

鳥 ノ %_2(λ

)+… +島

DJCO(λ)) ′=0 0

=■

_Σを

_Q(ノ

プ

ら

_π_ttD(D′

%_1鰺

D

J=0 2

+鳥

_Σ

:Q(プ

′%一

π

ひ

Dに

ブ

%_20))

ブ=0

+…

・

十島Σを

OCプ

′

銑―

π

ttDcプ

の

0))

′

=0

°

=PID2(偽

_π_{%_1)(λ)} 十P2D'(%―れ%_2)(λ)

+…

・ 十 島 D2(%_πCo)(λ₎

=Plα

_21+P2422+…

°

十島司ユれ

となる。よって

{α

∬

)}が

線形漸化式

(3.7)を

満たす。づ

=0,…

。

,た

-1を

代

入すると

, 謂

)=DOば

λ

_)=λ

π

覇P=Dl%(λ

)〒

η

矛

1

α

″

)=D2%(λ

)=η

(η-1)λ

η

2

α

静

-1)・ Dλ-1%(λ

_)=π

_(π

-1)…

。

_(η

一た

+2)λ

協

十

た

+1 が成 り立つ。

□ 定理3.2.5を用いる と

,線

形漸化式の固有方程式が重解 を持つ場合 も含 めて線形漸化式の一般論が得 られ る。 だが

,全

ての場合 を表記 す る と煩 雑 なので

,線

形

3項

間漸化式の場合 を次節 にまとめる。 39

第

3章

線形漸化式の一般論 3。

3

線形

3項

間漸化式

定理 3.3.lP,9∈

Cを

定数として

,線

形

3項

間漸化式

α

π

=pan_1+9α

η

_2(g≠

o) (3.9)

を満たす数列

{α

η

}に

ついて次の式が成り立つ。

1.固

有方程 式 ″

2=p″

+gが

相違 なる

2つ

の解 α,β ∈

Cを

もつ とき, 線形漸化式 を表す任意の数列 は

Q,o∈

Cを

用 いて απ

=Clα

鯰十C2βη

(3.10)

と表 され る。

2.固

有方程式 ″

2=p″

+α が重解 α∈

Cを

もつ とき

,線

形漸化式 を表 す任意 の数列 は

Q,o∈

Cを

用 いて αη

=θ

lαπ

+c2π

απ

(3.11)

と表 され る。 証明

1.線

形

3項

間漸化式 απ

=pα

π

_1+9α

π

_2の

固有方程式 λ

2_pλ

_9=0

の異なる2解 がα

,β

とすると

,定

理

3.1.8よ

り

,あ

る

o,Q∈

Cを

用いて

′

.

α

_η

=θ

lα

π

tt C2β

π

が成 り立つ。

2.線

形

3項

間漸化式

_{%=pan_1+α}

α

_犠

_2の 固有方程式

'λ

2=pλ

_g=0(g≠

0)

の解が重複度 2の 重解 αを持つとき

,α

_{≠oで あ り}

,定

理

3.2.5よ

り

,次

の数列は

_(3.9)の

解 となる。

{ :∫

:lin_1 .

40