プロローグ
どうも、安田です。
この記事はシリーズ記事です。このシリーズでは、周期性を持つ差分方程式(漸化式)について研究していきます。
周期性というのは、ある周期$\theta \in \mathbb{N}$が存在して、全ての$n$に対して
\[
a_{n+\theta} = a_n
\]
が存在することを指します。
考察
今回のテーマ
今回考えるのは、線形差分方程式です。すなわち
\[
a_m = s_1 a_n + s_2 a_{n+1} + \cdots + s_m a_{n + m - 1}
\]
という形の漸化式を満たす数列の周期性について考えていきます。ただし、恒等的に$0$になることは周期性を持つとは言わないこととします。
もちろん、この形の差分方程式では常に周期性を持つわけではなく、周期性を持つ場合はある初期値において周期性を持ちます。
本記事では、周期性を持つ可能性があるかどうかを判断する方法について考えてます。
実際の例
さて、では実際に存在するのかどうなのかというのを見ていきます。 \[ a_{n+2} = 3a_{n+1} + 4a_n \] この漸化式について周期2を持つような初期値について考えます。
$a_1, a_2$ が初期値として与えられますが、周期が2なので$a_3, a_4$ についてのみ調べれば良いことがわかります。 まずは$a_3, a_4$ について漸化式を立てます。 \begin{equation} \begin{cases} a_3 = 3a_2 + 4a_1 \\ a_4 = 3a_3 + 4a_2 \end{cases} \end{equation} これに $a_3 = a_1, a_4 = a_2$ を代入すれば、条件が求まります。 \begin{equation} \begin{cases} a_1 = 3a_2 + 4a_1 \\ a_2 = 3a_1 + 4a_2 \end{cases} \end{equation} これは、上下ともに $a_1 + a_2 = 0$ となっているので、上下の式に矛盾はありません。ここで、例えば $a_1 = 3, a_2 = -3$ とすれば、 \begin{equation} \begin{cases} a_3 = 3 \cdot (-3) + 4 \cdot 3 = 3 = a_1 \\ a_4 = 3 \cdot 3 + 4 \cdot (-3) = -3 = a_2 \end{cases} \end{equation} となり、周期性を持つことがわかりました。逆に必ず周期性を持たない漸化式というものもあります。例えば、 \[ a_{n+2} = 3a_{n+1} + 5a_n \] は必ず周期2を持たないことが簡単にわかります。上と同じように計算すると、連立した2式が矛盾することがわかります。
一般的な周期可能性
周期を持つものと周期を持たないものがあることがわかったので、一般的な議論をします。次のような差分方程式を考えます。
$\theta = m$ のとき
例と同じように式を連立します。
行列をまだ習っていない高校生などへ向けて簡単に解説すると、連立方程式の係数と変数を分離させてそれぞれ数として扱って性質を見よう、という試みです。(実際はもっと色々な目的があるのですが、今回はこの解釈で十分です。)
このブログは一応高校生以上向けですので、多少行列の解説を入れながら解説します。(新課程では行列をやるのかもしれませんが、よく知らないので解説します。)
なお、行列の積については外部のサイトを除いてください。(こちらがわかりやすそうです)
ここで考えるべきは、上の式が示すように、この行列を作用させても変化しないような零でないベクトルが存在するかということです。すなわち固有ベクトルの存在可能性ですね。 単位行列(行列の右肩下がりの対角線成分が1でそれ以外が0)を$E$とすると、$E$は全てのベクトルを固有ベクトルに持つので、上の$s_1, \cdots s_m$ が並んだ行列を$S$、$a_1, \cdots a_m$を並べたベクトルを$\boldsymbol{a}$とすると \[ E \boldsymbol{a} = S \boldsymbol{a} \] 行列は分配法則や実数倍の保存が成立するので \[ (S - E) \boldsymbol{a} = \boldsymbol{0} \] とできます。ここで、このような零でない$\boldsymbol{a}$が存在するのは、行列式(行列Aの行列式は$|A|$と書く)というものが0になれば良いことがわかっています。ここで
という事実があります。紛らわしいですが $i$ は虚数単位です。巡回行列という名前がついているそうです。ここで、これが0になるのが条件でしたので、次の結論が導かれました。
非常に綺麗な形で結論が出ました。
$\theta \lt m$ のとき
こちらは、一般化しようとすると$\theta = m$ よりも少々面倒になります。ここからが本記事の本番となります。
まずは $\theta = m$ のときと同様に初期値を固有値として持つ行列を考えなくてはなりません。
非常にややこしいですが、今回は連立した式を書き下さず、一般化した式として見ます。自分でも混乱したまま記事を書いているので、間違いを発見したらぜひご指摘ください。
ただし $r = 0$ のときはこのような $k$ が存在しない。
同様に \begin{equation} \begin{cases} T_{n, k} = z\\ T_{n, k + 1}= z - 1 \end{cases} \end{equation} を満たす点も考えておく。 こちらは $p = 1$ となる点から $k$ が $+r$ だけズレた点であることがわかる。なぜならば、 $r + q\theta \leq m$ となる非負整数$q$の個数は$z$個だが、$r + 1 + q\theta \leq m$ となる非負整数$q$の数は$z-1$個だからである。 また、この係数となっている和の各項の集合を $A_{n,k}$ とおくと、明らかに$A_{n + 1, k - 1} = A_{n, k}$ であり、端においても同様の議論をすれば、係数行列が巡回行列になることがわかる。
これだけの事実が求まれば、あとは $n = 1$ となるような上手い漸化式を見つけ、最初の$\theta$個の項について考えればよいです。
これで、求めたい情報を全て求めることができました。 最後に係数行列$P$の $(1, k)$ 成分 $u_k$ を式として表せば、$k = 1$ のときだけ $-1$ を加えた $t_k$ について $\theta = m$ のときと同様の計算で出来ます。
$r + 1 \lt R$ ならば \begin{equation} u_k = \left\{ \begin{aligned} & \sum_{x = 0}^{z - 1} a_{\theta - r + k + x\theta} & (k \leq r) \\ & \sum_{x = 0}^z a_{k - r + x\theta} & (r \lt k \lt R) \\ & \sum_{x = 0}^{z-1} a_{k - r + x\theta} & (R \geq k) \end{aligned} \right. \end{equation} $r + 1 \gt R$ ならば \begin{equation} u_k = \left\{ \begin{aligned} & \sum_{x = 0}^{z} a_{\theta - r + k + x\theta} & (k \lt R) \\ & \sum_{x = 0}^{z - 1} a_{\theta - r + k + x\theta} & (R \leq k \leq r) \\ & \sum_{x = 0}^{z} a_{k - r + x\theta} & (r \lt k) \end{aligned} \right. \end{equation} $r + 1 = R$ ならば \begin{equation} u_k = \sum_{x = 0}^{z - 1} a_{k + x\theta} \end{equation} とすれば、$t_1 = u_1 - 1$ また $k \neq 1$ に対して $t_k = u_k$ として \[ \prod_{k=1}^{\theta} \left(\sum_{l=1}^{\theta} e^{\frac{2\pi(k-1)(l-1)i}{\theta}} t_l \right) = 0 \] となるとき、さらにその時に限り、数列$(a_n)$はある初期値で周期$\theta \lt m$を持つ。
一番面倒な部分が終わりました。
$\theta \gt m$ のとき
こちらはシグマが来ることはないので、先程の議論に比べてとても簡単です。今回の巡回行列になるわけですが、この証明は上同様なので省略します。
あとは巡回行列の行列式に代入するだけですね。
以上で全ての場合においてある周期における周期可能性の判定法を入手することができました。
色をつけて強調した通り、任意の周期$\theta$を持つかどうかの判定法はまだ確立できていないので、これが今後の課題かなと思います。
ここで補足ですが、「ある$a_1, \cdots, a_\theta$で周期を持つなら、それをずらした$a_\theta, a_1, \cdots, a_{\theta - 1}$ などでも周期を持つはずだから、
固有ベクトルが$\theta$個ある必要があるのではないか」という疑問に対する答えを書いておきます。
実は$\theta$次の巡回行列の固有ベクトルは、$x^\theta = 1$ の根 $\zeta$ を使って
\[
\begin{pmatrix}
1 \\ \zeta \\ \zeta^2 \\ \vdots \\ \zeta^{\theta - 1}
\end{pmatrix}
\]
という形で表されるそうです。よって、これを$\zeta$倍すれば成分がずれていきます。
しかしながら、これは逆向きの議論をすることができます。今回求めた周期性の条件は、周期性との同値条件でした。
つまり、固有ベクトルの成分をずらすためのある定数倍$\zeta$が存在して、これを$\theta$回作用させると$1$に戻ってくることがわかります。すなわち
\[
\zeta^{\theta} = 1
\]
です。よって、$\zeta$ は $1$ の $\theta$乗根であることがわかりました。また、各成分も$\zeta$を作用させたら次の成分と一致するわけですから、第1成分を$c$とすれば、固有ベクトルは
\[
\begin{pmatrix}
c \\ c\zeta \\ c\zeta^2 \\ \vdots \\ c\zeta^{\theta - 1}
\end{pmatrix}
\]
という形になることがわかります。以上のことをもって、ある$1$ の $\theta$ 乗根$\zeta$が存在して巡回行列の固有値1の固有ベクトルの第$k$成分が$\zeta^{k-1}$となっているという、サブの結論として導かれることになります。
以上、補足でした。
今回はここまでにしようと思います。それでは、お疲れ様でした。
この記事いいね！コメント送信フォームまで飛ぶ
この記事には0件のコメントがあります。