日本応用数理学会論文誌第31巻3号　pp

Max-Plus 線形代数とその応用

西田 優樹

∗

同志社大学研究開発推進機構

概要. Max-plus代数とは，加法を演算max，乗法を演算 +で定義した半環である．

Max-plus代数は製造工程計画を起源とし，理論と応用の様々な立場から独立に発展を続

けてきた．本稿ではmax-plus代数上の固有値問題を取り上げ，その基礎事項について計 算方法とともに解説する．また，固有値問題の発展的な理論を最近の研究成果を交えて紹 介する．さらに，離散事象システム及び可積分系への応用にも言及する．

Max-Plus Linear Algebra and Its Applications

Yuki Nishida

∗

Organization for Research Initiatives and Development, Doshisha University

Abstract. The max-plus algebra is a semiring with addition “max” and multiplication

“+”. The study of the max-plus algebra originated from manufacturing and has been de- veloped independently in various fields of theory and application. In the present paper, we focus on the eigenvalue problem over the max-plus algebra and explain the fundamental facts including computational algorithms. We also introduce recent theoretical develop- ments in the eigenvalue problem. Further, we describe applications of the eigenvalue problem to discrete event systems and integrable systems.

1. はじめに

Max-plus代数とは，集合R∪ {−∞} ^に加法a⊕b := max(a,b)と乗法a⊗b := a+bを 定義した半環である．Max-plus代数の起源は1960年代の鉄鋼の製造工程計画にさかの

ぼる [19, 20]．この時点ですでに簡単な線形方程式や固有値問題についていくつかの結

果が得られており，1970 年代にかけて線形代数の理論が整備されていった [21]．また

max-plus代数やそれと同型なmin-plus代数，あるいはそれらをより一般化した代数構造

はパス代数[37]，dioid [38]，トロピカル半環[60]，extremal代数[71]などさまざまな立 場から独立に研究が進められている．ここで，「トロピカル」という名称はブラジルの数学

者I. Simonの研究[64]に敬意を表してつけられたとされており，欧州から見たブラジル

が「トロピカル」であることに由来する．現在では，max-plus代数は制御理論をはじめと する応用の側面と，トロピカル幾何学の一般論を用いた代数幾何学的な側面を中心に，組 み合わせ最適化や可積分系など複数の分野を結びつけながら発展を続けている．Max-plus 代数やその応用に関する英語のサーベイとしては，[1, 13, 36, 63]などを参照されたい．

Max-Plus 線形代数とその応用

西田 優樹

∗

同志社大学研究開発推進機構

概要. Max-plus 代数とは，加法を演算max，乗法を演算 +で定義した半環である．

Max-plus代数は製造工程計画を起源とし，理論と応用の様々な立場から独立に発展を続

けてきた．本稿ではmax-plus代数上の固有値問題を取り上げ，その基礎事項について計 算方法とともに解説する．また，固有値問題の発展的な理論を最近の研究成果を交えて紹 介する．さらに，離散事象システム及び可積分系への応用にも言及する．

Max-Plus Linear Algebra and Its Applications

Yuki Nishida

∗

Organization for Research Initiatives and Development, Doshisha University

Abstract. The max-plus algebra is a semiring with addition “max” and multiplication

“+”. The study of the max-plus algebra originated from manufacturing and has been de- veloped independently in various fields of theory and application. In the present paper, we focus on the eigenvalue problem over the max-plus algebra and explain the fundamental facts including computational algorithms. We also introduce recent theoretical develop- ments in the eigenvalue problem. Further, we describe applications of the eigenvalue problem to discrete event systems and integrable systems.

1. はじめに

Max-plus代数とは，集合R∪ {−∞} ^に加法a⊕b := max(a,b)と乗法a⊗b := a+bを 定義した半環である．Max-plus代数の起源は1960年代の鉄鋼の製造工程計画にさかの

ぼる [19, 20]．この時点ですでに簡単な線形方程式や固有値問題についていくつかの結

果が得られており，1970年代にかけて線形代数の理論が整備されていった [21]．また

max-plus代数やそれと同型なmin-plus代数，あるいはそれらをより一般化した代数構造

はパス代数[37]，dioid [38]，トロピカル半環[60]，extremal代数[71]などさまざまな立 場から独立に研究が進められている．ここで，「トロピカル」という名称はブラジルの数学

者I. Simonの研究[64]に敬意を表してつけられたとされており，欧州から見たブラジル

が「トロピカル」であることに由来する．現在では，max-plus代数は制御理論をはじめと する応用の側面と，トロピカル幾何学の一般論を用いた代数幾何学的な側面を中心に，組 み合わせ最適化や可積分系など複数の分野を結びつけながら発展を続けている．Max-plus 代数やその応用に関する英語のサーベイとしては，[1, 13, 36, 63]などを参照されたい．

Max-plus代数上の線形代数に焦点をあてると，通常の代数系で成り立つ事実の類似

がmax-plus 代数においても成り立つのかという問題が考えられる．行列の恒等式に関

してはこの問題は肯定的に解決されているものが多く，Cayley-Hamilton の定理[61]， Binet-Cauchyの公式[7,33]，Jacobiの恒等式[58]などが知られている．一方で，max-plus 代数上の線形方程式の求解は特別な場合を除いて難しい問題である．実際，A⊗x = b や x = A⊗ x⊕ b といった形の方程式の解法が古くから知られているものの [17, 19]，

max-plus代数上の等式においては移項ができないのでA⊗x⊕b=C⊗x⊕dという一般

形の方程式を簡単な場合に変形できない．このような両側方程式といわれるクラスの線形 方程式については，例えば交互法[24]によって解の1つを求められるものの，行列の次 数に関して多項式時間で解を求めるアルゴリズムは現在のところ知られていない．固有値 問題については，正方行列と重み付きの有向グラフを対応させることで固有値や固有ベク トルを組み合わせ論的に解釈できることが知られている．例えば，行列の最大固有値は グラフの最大平均閉路重みと一致し，また距離行列のある列が固有ベクトルとなる[21]．

Max-plus代数上の固有値問題を通常の代数系の場合と比較した際に，大きく異なる点は

既約なmax-plus行列が固有値を1つしか持たないことである．そのため，行列の対角化

のような通常の線形代数の類似として考えるべきことが議論できていない．この点につい ては，固有値の代わりに固有多項式の根に着目することで解決する試みが進められてい る[57]．

本稿はmax-plus代数上の固有値問題を中心に解説するものであり，以下のように構成

される．まず第2節ではmax-plus代数とその上の行列に関する基礎事項を説明する．第 3節では行列の固有値や固有ベクトル，さらには固有多項式に関する結果をまとめるとと もに，それらの具体的な計算手法を例を交えながら解説する．固有多項式は既約行列に対 しても重複度を込めて行列の次数と同じだけの根を持ち，最大根は最大固有値と一致する が他の根は固有値とはならない．そこで第4節では，固有多項式の固有値でない根が持つ 意味に着目した固有値問題の発展について述べる．また，max-plus代数をトロピカル幾 何学の観点から拡張したsupertropical代数[43–48]も固有値問題に対するアプローチとし て有用であり，これについても第4節で概観する．さらに，第5節ではmax-plus代数上 の固有値問題の応用に触れ，実問題への応用として鉄道の運行スケジューリング，また他 の理論的な分野との関連について超離散可積分系を例に挙げる．最後に第6節で本稿のま とめを行い，max-plus代数上の固有値問題について今後の展望を述べる．

2. Max-plus 代数

2.1 Max-plus 代数における演算

Max-plus代数とは，集合R_max:=R∪ {−∞}^上に2種類の2項演算⊕^と⊗^{をそれぞれ} a⊕b= max(a,b), a⊗b=a+b (a,b∈R_max)

で定義した代数系である．これらの演算は次の性質を持つ．

1. ⊕^{に関する結合則：}

(a⊕b)⊕c=a⊕(b⊕c) (a,b,c∈R_max) 2. ⊕^{に関する交換則：}

a⊕b= b⊕a (a,b∈R_max) 3. ⊕^{に関する単位元}ε:=−∞^の存在：

a⊕ε= ε⊕a=a (a∈R_max) 4. ⊗^{に関する結合則：}

(a⊗b)⊗c=a⊗(b⊗c) (a,b,c∈R_max) 5. ⊗^{に関する単位元}e:= 0の存在：

a⊗e= e⊗a= a (a∈R_max) 6. ⊗^に関するεの吸収性：

a⊗ε=ε⊗a=ε (a∈R_max) 7. ⊗^の⊕^{に対する分配則：}

(a⊕b)⊗c=a⊗c⊕b⊗c (a,b,c∈R_max) a⊗(b⊕c)=a⊗b⊕a⊗c (a,b,c∈R_max)

ここで，演算⊕に関する逆元は存在しないことに注意する．これらの性質より，max-plus 代数R_maxは演算⊕^{を加法，演算}⊗を乗法とする半環の構造を持つ．乗法⊗^{に関する交換} 則が成り立つからR_maxは可換半環であり，また任意のa∈R_maxについてa⊕a = aであ るのでR_maxは冪等半環である．任意のa∈Rは乗法⊗ ^{に関する逆元}−aを持つ．正の整 数kとa∈Rに対してa^⊗k =a⊗a⊗ · · · ⊗a

k回

= kaとし，a^⊗−k =(−a)^⊗k, a^⊗0 =0とする．

次に，R_max の元を成分に持つn次元列ベクトルの全体をRⁿ_maxと表し，また m×n行 列の全体を R^m_max^×n と表す．ベクトル及び行列の演算については通常の代数系と同様に定 義する．すなわち，n 次元列ベクトルはn×1行列とみなし，行列 A = (ai j),B = (bi j) ∈ R^m_max^×n,C= (ci j)∈Rⁿ_max^×ℓ およびスカラーα∈R_maxに対して以下を定める．

1. Max-plus代数上での和 A⊕B∈R^m×n_max：

[A⊕B]i j =a_{i j}⊕b_{i j}

で定義した代数系である．これらの演算は次の性質を持つ．

1. ⊕^{に関する結合則：}

(a⊕b)⊕c=a⊕(b⊕c) (a,b,c∈R_max) 2. ⊕^{に関する交換則：}

a⊕b=b⊕a (a,b∈R_max) 3. ⊕^{に関する単位元}ε:= −∞^の存在：

a⊕ε=ε⊕a=a (a∈R_max) 4. ⊗^{に関する結合則：}

(a⊗b)⊗c=a⊗(b⊗c) (a,b,c∈R_max) 5. ⊗^{に関する単位元}e:=0の存在：

a⊗e=e⊗a= a (a∈R_max) 6. ⊗^に関するεの吸収性：

a⊗ε=ε⊗a=ε (a∈R_max) 7. ⊗^の⊕^{に対する分配則：}

(a⊕b)⊗c=a⊗c⊕b⊗c (a,b,c∈R_max) a⊗(b⊕c)=a⊗b⊕a⊗c (a,b,c∈R_max)

ここで，演算⊕に関する逆元は存在しないことに注意する．これらの性質より，max-plus 代数R_maxは演算⊕^{を加法，演算}⊗を乗法とする半環の構造を持つ．乗法⊗^{に関する交換} 則が成り立つからR_maxは可換半環であり，また任意のa∈R_maxについてa⊕a = aであ るのでR_maxは冪等半環である．任意のa∈Rは乗法⊗^{に関する逆元}−aを持つ．正の整 数kとa∈Rに対してa^⊗k =a⊗a⊗ · · · ⊗a

k回

= kaとし，a^⊗−k =(−a)^⊗k, a^⊗0 =0とする．

次に，R_max の元を成分に持つn次元列ベクトルの全体をRⁿ_maxと表し，また m×n行 列の全体を R^m_max^×n と表す．ベクトル及び行列の演算については通常の代数系と同様に定 義する．すなわち，n次元列ベクトルはn×1行列とみなし，行列 A = (ai j),B = (bi j) ∈ R^m_max^×n,C= (ci j)∈Rⁿ_max^×ℓ およびスカラーα∈R_maxに対して以下を定める．

1. Max-plus代数上での和 A⊕B∈R^m×n_max：

[A⊕B]i j =a_{i j}⊕b_{i j}

2. Max-plus代数上での積 A⊗C∈R^m×_max^ℓ： [A⊗C]i j =

⊕n

k=1

aik⊗ck j

3. Max-plus代数上でのスカラー倍α⊗A∈R^m_max^×n： [α⊗A]i j= α⊗a_{i j}

ただし，[∗]i jは行列の(i, j)成分を表す．この演算の下で，すべての成分が εであるベク トルや行列はそれぞれ零ベクトルおよび零行列となり，ともにE^{で表す．また，対角成} 分がすべて0で他の成分がすべてεであるn次正方行列は単位行列となり，これを E_n で 表す．

Max-plus代数について詳しく述べた英語の教科書をいくつか紹介しよう．Max-plus線

形代数について書かれた初期の教科書として[21]がある．現在使われている標準的な教 科書としては固有値問題と鉄道の運行スケジューリングへの応用が詳しい[42]や，一般 化固有値問題やmax-plus線形計画問題もふくめて網羅的に記述された[14]がある．他に 制御系への応用を中心に述べた[6]，より一般に半環上の線形代数について解説した[39]， トロピカル幾何学の視点が盛り込まれた[53]を参考文献として挙げておく．

2.2 Max-plus 行列とグラフ

Max-plus代数上の固有値問題を考えるうえで，正方行列と重み付きの有向グラフとの

対応が重要な意味を持つ．行列A = (ai j) ∈Rⁿ_max^×n に対して，頂点集合をV = {1,2, . . . ,n}^， 辺集合をE = {(i, j)∈V×V |a_{i j} ε}とする有向グラフを考える．さらに，辺上の重み関 数w: E→ Rをw((i, j))=a_{i j}で定義する．こうして得られる重み付き有向グラフをG(A) で表す．すなわち，G(A)はAを重み付き隣接行列とする有向グラフであるが，Aの成分の うち値が0であるものは重みが0である辺に対応し，成分がεであるときに辺が存在しな いことに注意する．グラフG(A)における頂点の列C =(i0,i₁, . . . ,iℓ)が p= 0,1, . . . , ℓ−1 について(ip,ip+1) ∈ EをみたすときCを（有向）道と呼ぶ．特に，i0 = iℓ であるときC を閉路と呼ぶ．また0≤ p <q ≤ℓ−1についてi_p i_qである閉路を基本閉路と呼ぶ．道 C = (i0,i₁, . . . ,iℓ)に対して長さと重みをそれぞれℓ(C) := ℓ,w(C) := ∑ℓ−1

p=0a_ipip+1 で定義す る．グラフG(A)において頂点を共有しない基本閉路の集まりを多重閉路といい，多重閉 路C^の長さℓ(C)と重みw(C)はそれぞれCを構成する閉路の長さの和と重みの和とする．

便宜上，空集合∅^{は長さと重みがともに}0である多重閉路であるとする．多重閉路は後に 述べる行列の固有多項式の特徴づけにおいて重要な役割を果たす．

グラフを用いたmax-plus行列の特徴づけとして，行列の冪に関する性質を紹介する．

行列A∈Rⁿ_max^×n と非負整数kに対して，Aをk回かけたものをA^⊗kで表す．特に，A^⊗0 = En

とする．このときA^⊗kの(i, j)成分は，グラフG(A)における頂点iから頂点 jへの長さk

の道の重みの最大値に一致する．さらに，グラフG(A)に重みが正である閉路が存在しな いとき

A⁺:= ⊕^∞

k=1

A^⊗k= A⊕A^⊗2⊕ · · · ⊕A^⊗n

であり，A⁺の(i, j)成分はグラフG(A)における頂点iから頂点 jへのすべての道の重み の最大値に一致する．またグラフG(A)に重みが正である閉路が存在しないとき

A^∗ :=⊕^∞

k=0

A^⊗k = E_n⊕A⊕ · · · ⊕A^⊗n−1

であり，A^∗ の(i, j)成分は，i jのときグラフG(A)における頂点iから頂点 jへのすべ ての道の重みの最大値に一致し，i= jのときは0である．行列 A⁺,A^∗をそれぞれKleene plus，Kleene starという．加法演算⊕^をmaxからminにとりかえたmin-plus代数で考え ると，行列A^∗ はグラフG(A)の距離行列を与える．この視点からGondranはmin-plus代 数をパス代数と呼んだ[37]．2つのn次正方行列の積の計算量はO(n³)であるから，定義 に従ってKleene plusやKleene starを計算する場合の計算量はO(n⁴)である．一方，これ らの計算は最短経路問題に対するFloyd-Warshall法[31,69]を用いればO(n³)の計算量で 実行可能である．このように，max-plus行列の種々の計算は既知の組み合わせ最適化問 題に帰着させることで効率的に実行できることが多い．

2.3 行列式

行列A=(ai j)∈Rⁿ_max^×n に対して，行列式を detA=⊕

σ∈S_n

⊗n

k=1

a_kσ(k)

で定義する．ただしSnはn次対称群である．Max-plus代数においては加法の逆元が存在 しないため置換の符号は考慮せず，したがって行列式はパーマネントと同義である．行列 式detAはS_n の各元に対応するn!個の項の最大値であるが，この最大値が2つ以上の置 換で同時に実現されるとき Aは特異であるといい，そうでないとき非特異であるという．

行列式の計算は2部グラフにおける割当問題（重み最大マッチング問題）に帰着させるこ とができる．よってn次正方行列の行列式はハンガリー法[51, 54]のEdmonds-Karp [29]

とTomizawa [68]による改良によってO(n³)の計算量で求められる．

さて行列式に関連して，max-plus代数上の線形方程式について少し説明を与える．行 列A=(ai j)∈R^m_max^×n に対して集合T(A)をすべてのi=1,2, . . . ,mについて以下の条件をみ たすベクトルx=(x1,x₂, . . . ,x_n)^⊤ ∈Rⁿ_maxの全体として定義する：

式a ⊗x ⊕a ⊗x ⊕ · · · ⊕a ⊗ x が2つ以上の項で同時に最大値をとる．

の道の重みの最大値に一致する．さらに，グラフG(A)に重みが正である閉路が存在しな いとき

A⁺ :=⊕^∞

k=1

A^⊗k= A⊕A^⊗2⊕ · · · ⊕A^⊗n

であり，A⁺の(i, j)成分はグラフG(A)における頂点iから頂点 jへのすべての道の重み の最大値に一致する．またグラフG(A)に重みが正である閉路が存在しないとき

A^∗ := ⊕^∞

k=0

A^⊗k = E_n⊕A⊕ · · · ⊕A^⊗n−1

であり，A^∗ の(i, j)成分は，i jのときグラフG(A)における頂点iから頂点 jへのすべ ての道の重みの最大値に一致し，i= jのときは0である．行列 A⁺,A^∗ をそれぞれKleene plus，Kleene starという．加法演算⊕^をmaxからminにとりかえたmin-plus代数で考え ると，行列 A^∗はグラフG(A)の距離行列を与える．この視点からGondranはmin-plus代 数をパス代数と呼んだ[37]．2つのn次正方行列の積の計算量はO(n³)であるから，定義 に従ってKleene plusやKleene starを計算する場合の計算量はO(n⁴)である．一方，これ らの計算は最短経路問題に対するFloyd-Warshall法[31,69]を用いればO(n³)の計算量で 実行可能である．このように，max-plus行列の種々の計算は既知の組み合わせ最適化問 題に帰着させることで効率的に実行できることが多い．

2.3 行列式

行列A=(ai j)∈Rⁿ_max^×n に対して，行列式を detA=⊕

σ∈S_n

⊗n

k=1

a_kσ(k)

で定義する．ただしSnはn次対称群である．Max-plus代数においては加法の逆元が存在 しないため置換の符号は考慮せず，したがって行列式はパーマネントと同義である．行列 式detAはS_n の各元に対応するn!個の項の最大値であるが，この最大値が2つ以上の置 換で同時に実現されるとき Aは特異であるといい，そうでないとき非特異であるという．

行列式の計算は2部グラフにおける割当問題（重み最大マッチング問題）に帰着させるこ とができる．よってn次正方行列の行列式はハンガリー法[51, 54]のEdmonds-Karp [29]

とTomizawa [68]による改良によってO(n³)の計算量で求められる．

さて行列式に関連して，max-plus代数上の線形方程式について少し説明を与える．行 列A=(ai j)∈R^m_max^×n に対して集合T(A)をすべてのi= 1,2, . . . ,mについて以下の条件をみ たすベクトルx= (x1,x₂, . . . ,x_n)^⊤ ∈Rⁿ_maxの全体として定義する：

式a_i1⊗x₁⊕a_i2⊗ x₂ ⊕ · · · ⊕a_in⊗ x_nが2つ以上の項で同時に最大値をとる．

集合T(A)は，通常の線形代数における斉次方程式Ax=0の解空間にあたるものである．

T(A)の元の1つを求める擬多項式時間アルゴリズムは研究されているものの[3, 26, 41]， 一般の行列に対する多項式時間アルゴリズムは現在のところ知られていない．また集合 T(A)全体を求める方法としては二重記述法[4]やCramerの公式を用いた方法[56]があ る．正方行列に限ると，集合T(A)と行列の特異性の関係について以下が成り立つ．

定理2.1 ( [3]) 正方行列 A∈ R^n×n_maxが特異である必要十分条件はT(A) {E}^{となることで} ある．

行列式は行列のランクの定義にも用いられる．行列Aのあるm×m小行列が非特異で あり，またすべての(m+1)×(m+1)小行列が特異であるとき，mをAのトロピカルラン クという．行列のトロピカルランクは Aが生成する行空間や列空間の幾何学的なイメー ジと相性が良いが，それらの次元とは必ずしも一致しない．Max-plus行列の様々なラン クの定義やそれらの関係性については[2, 28]を参照されたい．

3. 固有値問題の基礎

3.1 固有値・固有ベクトルの定義と線形空間

線形代数の中でも特に重要な固有値問題について，max-plus代数上での結果を整理す る．行列 A∈Rⁿ_max^×n に対して，λ∈R_maxとx∈Rⁿ_max\ {E}^が

A⊗x= λ⊗x (3.1)

をみたすとき，λをAの固有値，xをλに属するAの固有ベクトルという．行列Aのλ に属する固有ベクトル全体にE^{を付加した集合を} Aのλに属する固有空間といいU(A, λ) で表す．固有空間U(A, λ)はRⁿ_maxの部分空間であるが，ここでmax-plus代数上の線形空 間について整理しておく．集合Rⁿ_maxの部分集合U が以下の2条件をみたすとき，Uは部 分空間であるという．

1. u⊕v∈U (u,v ∈U)

2. α⊗u∈U (u∈U, α∈R_max)

部分空間Uの部分集合S について，任意のu∈UがS の元の有限線形結合で表されると き，すなわち

u= ⊕

v∈S

α_v⊗v (αv ∈R_max)

と表されてα_v が有限個を除いてεであるとき，S はU の生成系であるという．また，S のどの元uもS \ {u}の元の有限線形結合で表されないとき，S は独立であるという．さ らに部分空間Uの独立な生成系をU の基底という．Max-plus代数においては，有限生成

部分空間の基底は定数倍の違いを除いて一意に決まることが知られている[16]．このこと から基底に含まれるベクトルの数を部分空間の次元という．Max-plus代数においては加 法の逆元が存在しないため線形結合と正結合は区別されず，部分空間は凸錐の性質も併せ 持つ．この方面からの研究には[4, 5, 34]などがある．

3.2 最大固有値と最大平均閉路重み

行列A ∈ Rⁿ_max^×n に付随するグラフG(A)の閉路C について，その平均重みを ave(C) = w(C)/ℓ(C)で定義する．さらに，グラフG(A)における閉路の平均重みの最大値をλ(A)と 表す．ただし，G(A)が閉路を含まないときはλ(A) = εとする．次の結果はmax-plus代 数上の固有値問題において最も基本的なものであり，全成分が有限である行列に対して は初期の論文[20]で示されている．一般のR_max 上の行列については例えば[8]に証明が ある．

定理3.1 行列A ∈ Rⁿ_max^×n は少なくとも 1つの固有値を持ち，最大の固有値はグラフG(A) の最大平均閉路重みλ(A)に一致する．

グラフG(A)が強連結であるとは，任意の2頂点i, jについてiから jへの道が存在す ることをいい，このとき行列Aは既約であるという．後の理論の整合性のため，1×1行 列(ε)は既約であるとする．既約なmax-plus行列の固有値についてはさらに興味深い結 果が得られる．

定理3.2 ( [8]) 既約な行列A∈Rⁿ_max^×n は唯一の固有値λ(A)をもつ．

強連結なグラフG(A)の最大平均閉路重みは

λ(A)= max

i=1,2,...,n min

k=0,1,...,n−1

[A^⊗n⊗e₁]i−[A^⊗k⊗e₁]i

n−k (3.2)

として計算できることが知られている．ただし，e1 は最初の成分のみが0で他の成分が εであるベクトルであり，またベクトルxに対して[x]i はxのi番目の成分を表す．式

(3.2)によるグラフの最大平均閉路重みの計算はKarp [49]によって与えられたもので，そ

の計算量はO(n³)である．また，既約な行列の固有値と固有ベクトルを同時に計算する方 法として以下の冪乗法があり，通常の線形代数の場合と異なりmax-plus代数において冪 乗法は有限回のステップで厳密解を与える．

アルゴリズム3.3 ( [10]) 入力：既約な行列A∈R^n×n_max，出力：Aの固有値λとそれに属する 固有ベクトルx

1. k:= 0としx(0)を任意の非零ベクトルとする．

部分空間の基底は定数倍の違いを除いて一意に決まることが知られている[16]．このこと から基底に含まれるベクトルの数を部分空間の次元という．Max-plus代数においては加 法の逆元が存在しないため線形結合と正結合は区別されず，部分空間は凸錐の性質も併せ 持つ．この方面からの研究には[4, 5, 34]などがある．

3.2 最大固有値と最大平均閉路重み

行列A ∈ Rⁿ_max^×n に付随するグラフG(A)の閉路C について，その平均重みを ave(C) = w(C)/ℓ(C)で定義する．さらに，グラフG(A)における閉路の平均重みの最大値をλ(A)と 表す．ただし，G(A)が閉路を含まないときは λ(A) = εとする．次の結果はmax-plus代 数上の固有値問題において最も基本的なものであり，全成分が有限である行列に対して は初期の論文[20]で示されている．一般のR_max上の行列については例えば[8]に証明が ある．

定理3.1 行列A ∈ Rⁿ_max^×n は少なくとも 1つの固有値を持ち，最大の固有値はグラフG(A) の最大平均閉路重みλ(A)に一致する．

グラフG(A)が強連結であるとは，任意の2頂点i, jについてiから jへの道が存在す ることをいい，このとき行列Aは既約であるという．後の理論の整合性のため，1×1行 列(ε)は既約であるとする．既約なmax-plus行列の固有値についてはさらに興味深い結 果が得られる．

定理3.2 ( [8]) 既約な行列A∈Rⁿ_max^×n は唯一の固有値λ(A)をもつ．

強連結なグラフG(A)の最大平均閉路重みは

λ(A)= max

i=1,2,...,n min

k=0,1,...,n−1

[A^⊗n⊗e₁]i−[A^⊗k⊗e₁]i

n−k (3.2)

として計算できることが知られている．ただし，e1 は最初の成分のみが0で他の成分が εであるベクトルであり，またベクトルxに対して[x]i はxのi番目の成分を表す．式

(3.2)によるグラフの最大平均閉路重みの計算はKarp [49]によって与えられたもので，そ

の計算量はO(n³)である．また，既約な行列の固有値と固有ベクトルを同時に計算する方 法として以下の冪乗法があり，通常の線形代数の場合と異なりmax-plus代数において冪 乗法は有限回のステップで厳密解を与える．

アルゴリズム3.3 ( [10]) 入力：既約な行列A∈R^n×n_max，出力：Aの固有値λとそれに属する 固有ベクトルx

1. k:= 0としx(0)を任意の非零ベクトルとする．

2. x(k+1)=A⊗x(k)とする．もしあるk^′ ≤kとα∈Rが存在してx(k+1)=α⊗x(k^′) と表せるなら3に進む．そうでなければk :=k+1として2を繰り返す．

3. λ:=α/(k+1−k^′)をAの固有値として出力する．

4. x:=⊕k

j=k^′λ^⊗(k−j)⊗x(j)をλに属するAの固有ベクトルとして出力して終了する．

既約とは限らない行列A∈R^n×n_max の最大固有値λ(A)に属する固有空間について考える．

まずλ(A) εのとき，B = (−λ(A))⊗AとするとグラフG(B)は重みが正の閉路を含まな

い．よってB⁺が計算できて

B⊗(En⊕B⁺)= B⁺

である．特に B⁺ の(i,i) 成分が0 であるとき B⁺ のi列目と (En ⊕B⁺)の i列目は一致 するので，B⁺ のi列目は行列 Bの固有値0に属する固有ベクトルである．すなわち B⁺ のi 列目は Aの固有値 λ(A) に属する固有ベクトルである．さて B⁺ の対角成分が 0と なる場合を調べるため，臨界グラフを導入する．行列 Aに付随するグラフG(A)におい

て，閉路C がave(C) = λ(A) をみたすときC を臨界閉路という．臨界閉路上にある頂

点と辺をそれぞれ臨界頂点，臨界辺といいその全体を V^c(A),E^c(A)で表す．有向グラフ G^c(A) :=(V^c(A),E^c(A))を臨界グラフという．さらに，臨界頂点の集合V^c(A)上に

i∼ j ⇔ ^頂点iと頂点 jが臨界グラフG^c(A)における同じ連結成分にある として同値関係∼^{を定める．}

定理3.4 ( [21]) λ(A) ε をみたす行列 A ∈ Rⁿ_max^×n に対して，B = (−λ(A))⊗ A とする．

i ∈ V^c(A) であるとき[B⁺]i は固有値 λ(A) に属する A の固有ベクトルである．ただし，

[B⁺]i は行列B⁺ のi列目を表す．さらに，K をV^c(A)の同値関係∼ ^{に関する完全代表系} とするとき，

{[B⁺]i|i∈K}

は固有空間U(A, λ(A))の基底である．

一方でλ(A) = εであるとき，G(A)に閉路が存在しないからすべての成分が εである列 iが必ず存在する．このとき i番目の成分のみが0で他の成分がεであるベクトル e_i は λ(A)に属する固有ベクトルである．固有空間は以下で特徴づけられる．

定理3.5 ( [8]) 行列 A∈R^n×n_maxがλ(A)=εをみたすとき，

U(A, λ(A))= {(x1,x₂, . . . ,x_n)^⊤∈Rⁿ_max|[A]i E^であるiについて x_i = ε} である．

3.3 行列の全固有値

上述したように既約な行列はちょうど1つの固有値をもつが，既約でない場合は複数の 固有値を持ちうる．この説明のために，まずは行列のFrobenius標準形を導入しよう．置 換σ ∈S_nに対して，行列Pσ =(pi j)∈Rⁿ_max^×n を

p_{i j} =

{0 (j=σ(i)のとき)

ε (それ以外)

で定義する．行列A∈Rⁿ_max^×n に対してある置換σ∈Sn があって，ブロック下三角行列

Pσ⁻¹ ⊗A⊗Pσ=









A11 E · · · E A21 A22 . .. ...

... . .. ... E A_r1 · · · A_rr









のすべての対角ブロックが既約行列であるように変形できる．この行列をAのFrobenius 標準形という．この変形はグラフ理論的には以下のように解釈できる．まずグラフG(A) の頂点集合は，頂点i から頂点 jへの道と頂点 jから頂点 iへの道がともに存在すると きに iと jが同値であるとして，r(≤ n)個の同値類V₁,V₂, . . . ,V_r に分割できる．このと き，各頂点集合Vi が誘導するG(A)の部分グラフGi をG(A)の強連結成分という．グラ フG(A)の頂点の番号を適当に入れ替えることにより，

V1 = {1,2, . . . ,|V1|}, V2 ={|V1|+1,|V1|+2, . . . ,|V1|+|V2|}, . . . .

かつV_i の頂点からV_j の頂点に到達可能なら常に i> jであるようにできる．この入れ替 えで得られたグラフの重み付き隣接行列がAのFrobenius標準形であり，各対角ブロック Aiiは強連結成分Gi の重み付き隣接行列である．行列Aの有限な成分の数をmとすると Frobenius標準形を求める計算量はO(n+m)である[11]．

さて行列Aの固有値をλ，それに属する固有ベクトルをxとすると，置換σ∈Snに対 して

(Pσ⁻¹ ⊗A⊗Pσ)⊗(Pσ⁻¹ ⊗x)= Pσ⁻¹ ⊗A⊗x=λ⊗(Pσ⁻¹ ⊗x)

が成り立つ．よって，λはPσ⁻¹⊗A⊗Pσの固有値でもあり，Pσ⁻¹⊗xはλに属する固有ベ クトルである．よって，固有値および固有ベクトルに関する議論は行列が予めFrobenius 標準形で与えられているとしてよい．

3.3 行列の全固有値

上述したように既約な行列はちょうど1つの固有値をもつが，既約でない場合は複数の 固有値を持ちうる．この説明のために，まずは行列のFrobenius標準形を導入しよう．置 換σ ∈S_n に対して，行列Pσ =(p_{i j})∈Rⁿ_max^×n を

p_{i j} =

{0 (j=σ(i)のとき)

ε (それ以外)

で定義する．行列A∈Rⁿ_max^×n に対してある置換σ∈Sn があって，ブロック下三角行列

Pσ⁻¹ ⊗A⊗Pσ=









A11 E · · · E A21 A22 . .. ...

... . .. ... E A_r1 · · · A_rr









のすべての対角ブロックが既約行列であるように変形できる．この行列をAのFrobenius 標準形という．この変形はグラフ理論的には以下のように解釈できる．まずグラフG(A) の頂点集合は，頂点 iから頂点 jへの道と頂点 jから頂点 iへの道がともに存在すると きに iと jが同値であるとして，r(≤ n)個の同値類V₁,V₂, . . . ,V_r に分割できる．このと き，各頂点集合Vi が誘導するG(A)の部分グラフGi をG(A)の強連結成分という．グラ フG(A)の頂点の番号を適当に入れ替えることにより，

V1 = {1,2, . . . ,|V1|}, V2 = {|V1|+1,|V1|+2, . . . ,|V1|+|V2|}, . . . .

かつV_i の頂点から V_j の頂点に到達可能なら常に i> jであるようにできる．この入れ替 えで得られたグラフの重み付き隣接行列がAのFrobenius標準形であり，各対角ブロック Aiiは強連結成分Gi の重み付き隣接行列である．行列Aの有限な成分の数をmとすると Frobenius標準形を求める計算量はO(n+m)である[11]．

さて行列Aの固有値をλ，それに属する固有ベクトルをxとすると，置換σ∈Snに対 して

(Pσ⁻¹ ⊗A⊗Pσ)⊗(Pσ⁻¹ ⊗x)= Pσ⁻¹ ⊗A⊗x=λ⊗(Pσ⁻¹ ⊗x)

が成り立つ．よって，λはPσ⁻¹⊗A⊗Pσの固有値でもあり，Pσ⁻¹⊗xはλに属する固有ベ クトルである．よって，固有値および固有ベクトルに関する議論は行列が予めFrobenius 標準形で与えられているとしてよい．

Frobenius標準形の行列

A=









A₁₁ E · · · E A₂₁ A₂₂ . .. ...

... . .. ... E Ar1 · · · Arr









(3.3)

に対して，Aii に対応する強連結成分Gi は，λ(Aii) < λ(Aj j)をみたすすべての jについて A_ji = Eであるとき，すなわち，最大平均閉路重みがより大きな強連結成分から到達不可 能なときにspectralであるという．

定理3.6 ( [8]) Frobenius標準系(3.3)で与えられた行列の固有値の全体は {λ(Aii)|1≤ i≤r, G_i はspectral}

である．

次に固有ベクトルについて考える．行列A∈R^n×n_maxの固有値λ εについて，B= (−λ)⊗Aと する．λが最大でない固有値ならグラフG(B)は重み正の閉路を含むので，B⁺ =⊕_∞

k=1B^⊗k は無限和で，正の無限大に発散する成分がある．そうであっても，λ = λ(Aii) である spectralな強連結成分G_i に対応するB⁺ の列はRⁿ_maxのベクトルに収束する．そこで，平 均重みがλに一致する閉路であって，λ = λ(Aii)をみたすspectalな強連結成分Gi に含 まれるものをλ-臨界閉路と呼ぶ．λ = λ(A)であるときはこれは上述の臨界閉路に一致す る．λ-臨界閉路に含まれる頂点の集合V_λ^c(A)と辺の集合E^c_λ(A)からつくられる有向グラフ G^c_λ(A)= (V_λ^c(A),E^c_λ(A))を定義する．さらに，λ-臨界頂点の集合V_λ^c(A)上に

i∼^λ j ⇔ ^頂点iと頂点 jがλ-臨界グラフG^c_λ(A)における同じ連結成分にある として同値関係 ∼^λを定める．これを用いて，固有空間 U(A, λ)の基底を特徴づけること ができる．

定理3.7 ( [15]) Frobenius 標準形(3.3) の行列 A ∈ R^n×n_max の固有値 λ εに対して，B = (−λ)⊗Aとする．i ∈V_λ^c(A)であるとき[B⁺]i は固有値λに属するAの固有ベクトルであ る．さらに，KλをV_λ^c(A)の同値関係∼^λに関する完全代表系とするとき，

{[B⁺]i |i∈Kλ}

は固有空間U(A, λ)の基底である．

グラフG(A)の各強連結成分に対して，高々1つの固有値が決まることに注意すると，任 意に与えられた行列 A∈Rⁿ_max^×n の固有値は高々n個存在し，固定した1つの固有値に属す る固有空間の基底を求めるのにかかる計算量はO(n³)である．

例1 行列

A=











ε 5 2 ε ε ε

3 1 1 ε ε ε

−1 0 4 ε ε ε

2 ε 6 0 ε ε

ε −2 3 1 −3 −1

5 1 ε 0 1 2











について考える．この行列は既約ではないがすでにFrobenuis標準形となっており，頂点 集合がそれぞれ {1,2,3},{4},{5,6}^である 3つの強連結成分G₁,G₂,G₃ に分けられる．こ の分割に対応する対角ブロックはそれぞれ

A₁₁ =





ε 5 2

3 1 1

−1 0 4



, A₂₂ =(0), A₃₃=

(−3 −1

1 2

)

で，各強連結成分の最大平均閉路重みはそれぞれλ(A11) = 4, λ(A22)= 0, λ(A33) = 2であ り，λ(A)= max{λ(A11), λ(A22), λ(A33)}= 4がAの最大固有値である．また強連結成分G3

は他のどの強連結成分からも到達できないのでspectralであるから，λ(A33)=2もAの固 有値である．一方で，強連結成分G2 はG3から到達可能であり，かつλ(A22)< λ(A33)な のでλ(A22)= 0はAの固有値とはならない．

次に，各固有値に属する固有空間の基底を求める．固有値4について，行列(−4)⊗Aの Kleene plusを計算すると

((−4)⊗A)⁺ =











0 1 −2 ε ε ε

−1 0 −3 ε ε ε

−5 −4 0 ε ε ε

−2 −1 2 −4 ε ε

−4 −3 −1 −3 −7 −5 1 2 −1 −4 −3 −2











である．グラフG(A)の臨界閉路，すなわち平均重みが 4である閉路は(1,2,1)と(3,3) であるから，((−4)⊗A)⁺の1列目，2列目，3列目が固有ベクトルであり，2列目は1列 目の定数倍である．よって固有空間の基底は

{(0,−1,−5,−2,−4,1)^⊤,(−2,−3,0,2,−1,−1)^⊤}

となる．固有値2について，行列(−2)⊗AのKleene plusを計算すると

((−2)⊗A)⁺ =











∞ ∞ ∞ ε ε ε

∞ ∞ ∞ ε ε ε

∞ ∞ ∞ ε ε ε

∞ ∞ ∞ −2 ε ε

∞ ∞ ∞ −1 −4 −3

∞ ∞ ∞ −2 −1 0











例1 行列

A=











ε 5 2 ε ε ε

3 1 1 ε ε ε

−1 0 4 ε ε ε

2 ε 6 0 ε ε

ε −2 3 1 −3 −1

5 1 ε 0 1 2











について考える．この行列は既約ではないがすでにFrobenuis標準形となっており，頂点 集合がそれぞれ {1,2,3},{4},{5,6}^である 3つの強連結成分G₁,G₂,G₃ に分けられる．こ の分割に対応する対角ブロックはそれぞれ

A₁₁ =





ε 5 2

3 1 1

−1 0 4



, A₂₂ =(0), A₃₃=

(−3 −1

1 2

)

で，各強連結成分の最大平均閉路重みはそれぞれ λ(A11) = 4, λ(A22)= 0, λ(A33) = 2であ り，λ(A) =max{λ(A11), λ(A22), λ(A33)}=4がAの最大固有値である．また強連結成分G3

は他のどの強連結成分からも到達できないのでspectralであるから，λ(A33)=2もAの固 有値である．一方で，強連結成分G2 はG3から到達可能であり，かつλ(A22)< λ(A33)な のでλ(A22)= 0はAの固有値とはならない．

次に，各固有値に属する固有空間の基底を求める．固有値4について，行列(−4)⊗Aの Kleene plusを計算すると

((−4)⊗A)⁺ =











0 1 −2 ε ε ε

−1 0 −3 ε ε ε

−5 −4 0 ε ε ε

−2 −1 2 −4 ε ε

−4 −3 −1 −3 −7 −5 1 2 −1 −4 −3 −2











である．グラフG(A)の臨界閉路，すなわち平均重みが 4である閉路は(1,2,1) と(3,3) であるから，((−4)⊗A)⁺ の1列目，2列目，3列目が固有ベクトルであり，2列目は1列 目の定数倍である．よって固有空間の基底は

{(0,−1,−5,−2,−4,1)^⊤,(−2,−3,0,2,−1,−1)^⊤}

となる．固有値2について，行列(−2)⊗AのKleene plusを計算すると

((−2)⊗A)⁺ =











∞ ∞ ∞ ε ε ε

∞ ∞ ∞ ε ε ε

∞ ∞ ∞ ε ε ε

∞ ∞ ∞ −2 ε ε

∞ ∞ ∞ −1 −4 −3

∞ ∞ ∞ −2 −1 0











である．記号∞は成分が正の無限大に発散することを表す．グラフG(A)の2-臨界閉路 は(6,6)であるから，((−2)⊗A)⁺の6列目が固有ベクトルであり，固有空間の基底は

{(ε, ε, ε, ε,−3,0)^⊤}

となる．なお，固有空間の基底を求めるには実際には((−2)⊗A₃₃)⁺ を計算すれば十分で ある．

3.4 固有多項式

行列A∈Rⁿ_max^×n に対して，固有多項式χ_A(t)は

χ_A(t)=det(A⊕t⊗E_n)

で定義される．本節では行列の固有値と固有多項式の根との関係について述べるが，先に

max-plus代数上の1変数多項式の性質を整理する．

1変数n次多項式

f(t)=

⊕n

k=0

c_k⊗t^⊗k, c_k ∈R_max,c_n ε (3.4)

を考える．各λ∈ R_max に対して，値 f(λ)は高々(n+1)個の項の最大値である．この最 大値が 2つ以上の項で同時に実現されるとき，λは f(t)の根であるという．関数 f(t)は 区分的に線形な関数であり，そのグラフは下に凸で高々n個の屈折点を持つ．これらの屈 折点が f(t)の根と対応する．多項式 f(t)の項の中には，どのようなλ∈R_maxに対しても 値 f(λ)に影響しない項が存在する場合があり，したがって2つの多項式 f(t)とg(t)は異 なる項を含んでいても関数としては恒等的に f(t)= g(t)となることがある．このように関 数として等しいという意味で考えると，任意の1変数多項式は1次式の積に因数分解可能 である．

定理3.8 ( [25]) 1変数多項式(3.4)に対して，関数として

f(t)=c_n⊗(t⊕ p₁)^⊗m1 ⊗(t⊕p₂)^⊗m2 ⊗ · · · ⊗(t⊕ p_r)^⊗mr (3.5)

が成り立つような p₁,p₂, . . . ,p_r ∈ R_maxおよび正整数m₁,m₂, . . . ,m_r が存在する．さらに このとき，p₁,p₂, . . . ,p_r は f(t)の根であり，またm₁+m₂+· · ·+m_r =nが成り立つ．

式(3.5)において，正整数m_kを f(t)の根 p_kの重複度という．1変数多項式 f(t)の因数分 解は以下のアルゴリズムで求めることができ，その計算量はO(n)である．

アルゴリズム3.9 ( [23]) 入力：式(3.4)の形で与えられた1変数多項式 f(t)，出力：f(t) を因数分解した式

1. I := {j∈ {0,1, . . . ,n−1} |c_j ε}^とする．I = ∅^なら f(t)= c_n⊗t^⊗nは既に因数分解さ れている．そうでないならU := n,L:=max{k|k∈ I}^とし，I:= I\ {L},J:= {L,U} とする．

2. j:=max{k|k∈I}^{とする．このとき}|J|= 1あるいは c_L−c_U

U−L > c_j−c_L L− j となるまで以下を繰り返す：

J := J\ {L}^とし，J の最小の元をL，|J| ≥ 2なら J の2番目に小さい元をU とする．

3. I := I\ {j},J := J∪ {j},U := L,L:= jとする．I = ∅^なら4に進み，そうでないな ら2に戻る．

4. Jの元を小さいほうから順にk₀,k₁,k₂, . . . ,k_r とし，j= 1,2, . . . ,rに対して p_j = c_kj−1 −c_kj

kj−kj−1 , m_j = k_j−k_j−1 とする．

5. f(t)の因数分解として

f(t)= cn⊗(t⊕p1)^⊗m1 ⊗(t⊕ p2)^⊗m2 ⊗ · · · ⊗(t⊕ pr)^⊗mr ⊗t^⊗k0 を出力する．

さて行列A∈Rⁿ_max^×n に対して，固有多項式χ_A(t)を展開して χ_A(t)=

⊕n

k=0

c_k⊗t^⊗k

と表すと，t^⊗kの係数ckは長さがちょうど(n−k)であるG(A)の多重閉路の重みの最大値 である．またχ_A(t)はモニックなn次多項式であるから，

χ_A(t)=(t⊕p₁)^⊗m1 ⊗(t⊕ p₂)^⊗m2 ⊗ · · · ⊗(t⊕ p_r)^⊗mr ⊗t^⊗k0

と因数分解でき，p1,p2, . . . ,pr が根であって，k0 ≥1ならεも根である．これらの固有多 項式の根のことを Aの代数的固有値という[1]．次の定理は行列の固有値と固有多項式を 結びつけるものである．

定理3.10 ( [22]) 行列の最大固有値は最大の代数的固有値に一致する．

行列のすべての固有値は代数的固有値になるものの，代数的固有値は必ずしも固有値であ るとは限らない．この点については次節で詳しく述べる．