有限型シフトの位相エントロピー

遷移行列 $A$ の有限型シフトについて、周期点の個数 $∣ Fix (σ^{n}) ∣ = tr A^{n}$ と許される長さ $n$ の語の数の増え方から、位相エントロピー $h_{top} = lo g λ_{m a x}$ （ $λ_{m a x}$ はペロン・フロベニウス固有値）を求められる（例: $A = (1110)$ で $lo g \frac{1 + 5}{2}$ ）

前提

周期点の個数とメビウス反転（大学院数学力学系・エルゴード理論）
固有値と固有ベクトル（大学数学線形代数）

この技能までの道筋（58 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
約数の見つけ方（算数整数の性質）
文字式で表した整数の性質（中学数学数と式）
余りによる整数の分類（数学A 整数の性質）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
合同式（数学A 整数の性質）
最大公約数と最小公倍数（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
最大公約数と最小公倍数（数学A 整数の性質）
互いに素な法への分解（数学A 整数の性質）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
確率の定義と和事象・余事象（数学A 場合の数と確率）
包除原理（数学A 場合の数と確率）
オイラー関数の計算（大学数学整数論）
約数の個数と総和（数学A 整数の性質）
乗法的関数と約数にわたる和（大学数学整数論）
メビウス関数と反転公式（大学数学整数論）
周期点の個数とメビウス反転（大学院数学力学系・エルゴード理論）
三角形の角の大きさ（算数平面図形）
対頂角と平行線の同位角・錯角（中学数学平面図形）
三角形の外角と角の組み合わせ（中学数学平面図形）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
1 次方程式の解き方（中学数学方程式）
二等辺三角形の角（中学数学平面図形）
平行四辺形と特別な四角形の性質（中学数学平面図形）
三角形・四角形の面積（算数平面図形）
平方根の意味と根号の簡単化（中学数学数と式）
三平方の定理（中学数学相似と三平方の定理）
折り返した図形の角と長さ（中学数学平面図形）
三平方の定理と平面図形（中学数学相似と三平方の定理）
ベクトルの演算と成分（数学C ベクトル）
行列の和・積と 2 次の逆行列（大学数学線形代数）
行列式（大学数学線形代数）
掃き出し法と連立 1 次方程式（大学数学線形代数）
行列の階数と解の存在（大学数学線形代数）
ベクトル空間・一次独立・基底・次元（大学数学線形代数）
円の周の長さと面積（算数平面図形）
おうぎ形の弧の長さと面積（算数平面図形）
弧の長さからおうぎ形の中心角と面積を求める（中学数学平面図形）
特別な直角三角形の辺の比（中学数学相似と三平方の定理）
弧度法と単位円による三角関数（数学II 三角関数）
加法定理と 2 倍角・半角・積和の公式（数学II 三角関数）
線形変換と行列（大学数学線形代数）
核と像と次元定理（大学数学線形代数）
固有値と固有ベクトル（大学数学線形代数）

説明

記号 $1, \dots, m$ の両側無限列のうち、隣り合う記号 $x_{i} x_{i + 1}$ がつねに $A_{x_{i} x_{i + 1}} = 1$ をみたすものの全体 $X_{A}$ とシフト $σ$ （1 つ左にずらす写像）を、 $0, 1$ 成分の遷移行列 $A$ の有限型シフトといいます。その位相エントロピー $h_{top}$ は、 $X_{A}$ に現れる長さ $n$ の語（許される語）の数 $∣ B_{n} ∣$ が指数的に増える速さ $h_{top} = lim_{n \to \infty} \frac{1}{n} lo g ∣ B_{n} ∣$ で、力学系の「複雑さ」を 1 つの数で表します。この技能を使うと、語を数え上げなくても、 $A$ の固有値を求めるだけで $h_{top} = lo g λ_{m a x}$ が得られ、周期点の個数 $tr A^{n}$ もあわせて計算できます。

なぜそうしてよいのか

$A$ を頂点 $1, \dots, m$ の有向グラフ（ $A_{ij} = 1$ のとき $i \to j$ に辺）とみると、許される長さ $n$ の語 $x_{1} x_{2} \dots x_{n}$ はこのグラフ上の長さ $n - 1$ の道です。行列の積の定義から $(A^{n - 1})_{ij}$ は $i$ から $j$ への長さ $n - 1$ の道の本数なので、 $∣ B_{n} ∣ = \sum_{i, j} (A^{n - 1})_{ij}$ （ $A^{n - 1}$ の成分の総和）です。同じく、 $σ^{n} x = x$ となる点は長さ $n$ の語を繰り返したもので、最初と最後が同じ頂点に戻る長さ $n$ の閉じた道に対応するので、 $∣ Fix (σ^{n}) ∣ = \sum_{i} (A^{n})_{ii} = tr A^{n}$ です。

成分の総和の増え方は固有値で決まります。 $A$ が既約（グラフのどの頂点からどの頂点へも道がある）なら、ペロン・フロベニウスの定理により、絶対値最大の固有値の中に正の実数 $λ_{m a x}$ があり、成分がすべて正の固有ベクトル $v$ （ $A v = λ_{m a x} v$ ）がとれます。 $v$ の成分の最小値を $c > 0$ 、最大値を $C$ とすると、 $A^{n - 1}$ の成分は $0$ 以上で $(A^{n - 1} v)_{i} = \sum_{j} (A^{n - 1})_{ij} v_{j}$ なので
$c i, j \sum (A^{n - 1})_{ij} \leq i \sum (A^{n - 1} v)_{i} = λ_{m a x}^{n - 1} i \sum v_{i} \leq C i, j \sum (A^{n - 1})_{ij}$
が成り立ち、 $∣ B_{n} ∣$ は定数倍の違いを除いて $λ_{m a x}^{n - 1}$ に等しくなります。両辺の $lo g$ を $n$ で割って $n \to \infty$ とすると定数の寄与は $0$ に消え、 $h_{top} = lo g λ_{m a x}$ が得られます。

周期点の側から見ると、 $A$ の固有値を重複も込めて $λ_{1}, \dots, λ_{m}$ とすれば $tr A^{n} = \sum_{k} λ_{k}^{n}$ です。これは、 $A$ を複素数の範囲で上三角行列 $T = P^{- 1} A P$ に直すと（どの正方行列もこのように三角化できます）、 $T$ の対角成分が固有値 $λ_{k}$ で、 $T^{n} = P^{- 1} A^{n} P$ の対角成分が $λ_{k}^{n}$ になり、トレースが $tr (P^{- 1} M P) = tr M$ で変わらないことからわかります。 $A$ が既約かつ非周期的（ある $N$ で $A^{N}$ の成分がすべて正）なら絶対値最大の固有値は $λ_{m a x}$ ただ 1 つ（重複なし）なので $tr A^{n} \approx λ_{m a x}^{n}$ となり、 $lim \frac{1}{n} lo g ∣ Fix (σ^{n}) ∣ = lo g λ_{m a x}$ と、同じ値が周期点の増え方からも読み取れます。

手順

遷移行列 $A$ をグラフとして描き、既約か（どの頂点からどの頂点へも行けるか）、さらに非周期的か（たとえば既約で自己ループ $A_{ii} = 1$ があれば非周期的）を確かめる
特性多項式 $det (A - λ E)$ を計算し、固有値 $λ_{1}, \dots, λ_{m}$ をすべて求める
絶対値が最大の正の実固有値 $λ_{m a x}$ （ペロン・フロベニウス固有値）を選ぶ。必要なら成分が正の固有ベクトルがとれることで確認する
検算として周期点の個数 $∣ Fix (σ^{n}) ∣ = tr A^{n} = \sum_{k} λ_{k}^{n}$ を求め、小さい $n$ で $tr A$ , $tr A^{2}$ を直接計算したものと比べる
位相エントロピーを $h_{top} = lo g λ_{m a x}$ と答える（語の数 $∣ B_{n} ∣ = \sum_{i, j} (A^{n - 1})_{ij}$ の増え方 $\approx λ_{m a x}^{n}$ と一致することを意識する）

例題

遷移行列 $A = 111100100$ の有限型シフト $(X_{A}, σ)$ の位相エントロピー $h_{top} (σ)$ を求めよ。

例題の解答

手順 1（既約性・非周期性） グラフには辺 $1 \to 1, 1 \to 2, 1 \to 3, 2 \to 1, 3 \to 1$ がある。頂点 $2, 3$ からは $1$ へ、 $1$ からはどの頂点へも行けるので既約である。また自己ループ $1 \to 1$ があるので非周期的である。

手順 2（固有値）
$det (A - λ E) = 1 - λ 11 1 - λ 0 10 - λ$
を第 1 行で展開すると
$(1 - λ) λ^{2} - 1 \cdot (- λ - 0) + 1 \cdot (0 + λ) = - λ^{3} + λ^{2} + 2 λ = - λ (λ - 2) (λ + 1)$
となり、固有値は $2, - 1, 0$ である。

手順 3（ペロン・フロベニウス固有値） 絶対値が最大の固有値は $λ_{m a x} = 2$ である。実際 $v = (2, 1, 1)^{T}$ とすると $A v = (4, 2, 2)^{T} = 2 v$ で、成分がすべて正の固有ベクトルがとれている。

手順 4（検算） $∣ Fix (σ^{n}) ∣ = tr A^{n} = 2^{n} + (- 1)^{n} + 0^{n} = 2^{n} + (- 1)^{n}$ （ $n \geq 1$ ）。 $n = 1$ で $2 - 1 = 1 = tr A$ （固定点は $\dots 111 \dots$ のみ）。 $n = 2$ で $4 + 1 = 5$ 、一方 $A$ は対称なので $tr A^{2} = \sum_{i, j} A_{ij}^{2} = 5$ で一致する。

手順 5（エントロピー） $h_{top} (σ) = lo g λ_{m a x} = lo g 2$ 。周期点の側からも $\frac{1}{n} lo g (2^{n} + (- 1)^{n}) \to lo g 2$ で一致する。

答え: $lo g 2$

よくある誤り

固有値を求めずに、行列の成分（たとえば行和の最大値）をそのまま使ってしまう誤り。行和は $min_{i} \sum_{j} A_{ij} \leq λ_{m a x} \leq max_{i} \sum_{j} A_{ij}$ という評価しか与えず、例題では行和 $3, 1, 1$ に対し $λ_{m a x} = 2$ なので、 $lo g 3$ とするのは誤り。正しくは固有値を求めて $λ_{m a x}$ を選ぶ。
エントロピーを $λ_{m a x}$ そのもの、あるいは $lo g_{2} λ_{m a x}$ としてしまう誤り。正しくは自然対数で $h_{top} = lo g λ_{m a x}$ （例: $A = (1110)$ なら $lo g \frac{1 + 5}{2}$ であって $\frac{1 + 5}{2}$ ではない。例題でも $lo g_{2} 2 = 1$ ではなく $lo g 2$ ）。
許される長さ $n$ の語の数を $tr A^{n}$ や $A^{n}$ の成分の総和としてしまう誤り。正しくは語 $x_{1} \dots x_{n}$ は辺 $n - 1$ 本の道なので $∣ B_{n} ∣ = \sum_{i, j} (A^{n - 1})_{ij}$ 、 $tr A^{n}$ は周期点の個数 $∣ Fix (σ^{n}) ∣$ である（エントロピーの値はどちらの増え方でも同じだが、個数としては別物。例題で $∣ B_{2} ∣ = \sum_{i, j} A_{ij} = 5$ 、 $∣ B_{3} ∣ = \sum_{i, j} (A^{2})_{ij} = 11$ ）。
$∣ Fix (σ^{n}) ∣ = tr A^{n}$ を最小周期 $n$ の周期点の個数と取り違える誤り。正しくは $tr A^{n}$ は周期が $n$ の約数である点も含む個数で、最小周期 $n$ の点の個数はメビウス反転 $P_{n} = \sum_{k ∣ n} μ (n / k) tr A^{k}$ で求める（例題で $n = 2$ なら $P_{2} = 5 - 1 = 4$ ）。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 1（大学院の講義の例題レベル）
記号の集合を ${0, 1, 2}$ とし、両側無限列 $x = (x_{i})_{i \in Z}$ で、すべての $i \in Z$ について $∣ x_{i + 1} - x_{i} ∣ \leq 1$ をみたすもの全体を $X$ とする（つまり隣り合う記号として $02$ と $20$ だけが禁止されている）。 $X$ 上のシフト写像 $σ : X \to X$ , $(σ x)_{i} = x_{i + 1}$ の位相エントロピー $h_{top} (σ)$ を求めよ。ただし $lo g$ は自然対数とする。

有限型シフトの位相エントロピー

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題