重解のない固有方程式を持つ数列の行列表現とその成分

漸化式,k-ナッチ数列,線形代数

153

はじめに

　この記事では重解を持たない固有方程式 $f (x) = 0$ を持つ数列 $a_{n}$ の行列による表現をその各成分まで具体的に求めます。

定義と主張

　まず色々と言葉と記号を定めておきます。

数列の固有方程式

　定数係数の線形漸化式
$a_{n + k} = c_{k - 1} a_{n + k - 1} + c_{k - 2} a_{n + k - 2} + \dots + c_{0} a_{n}$
を満たす数列 $a_{n}$ に対し固有多項式 $f (x)$ を
$f (x) = x^{k} - c_{k - 1} x^{k - 1} - c_{k - 2} x^{k - 2} - \dots - c_{0}$
と定め、固有多項式 $f (x)$ についての方程式 $f (x) = 0$ を $a_{n}$ の固有方程式と言う。

　上のような数列 $a_{n}$ に対し $k$ 次正方行列 $M$ を
$M^{T} = (\begin{matrix} 0 & 1 & 0 & \dots & 0 \\ 0 & 0 & 1 & \dots & 0 \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & 0 & \dots & 1 \\ c_{0} & c_{1} & c_{2} & \dots & c_{k - 1} \end{matrix})$
( $A^{T}$ は行列の転置)と定めると $M$ の固有多項式 $\det (x I - M)$ は $a_{n}$ の固有多項式 $f (x)$ に等しく、また
$a_{n} = {(\begin{matrix} a_{n} & a_{n + 1} & \dots & a_{n + k - 1} \end{matrix})}^{T}$
とおくと $a_{n}$ の漸化式は $a_{n + 1} = M^{T} a_{n}$ と表現できる。

　いま
$a_{n} = M^{T} a_{n - 1} = (M^{T})^{n} a_{0}$
より $a_{n}$ は $a_{0}$ と $M^{n}$ の値によって定まるので、以下 $M^{n}$ の計算に焦点を当てていきます。
　ここで ${a_{n}}$ の固有方程式が重解を持たない、つまりその解 $x = α_{1}, α_{2}, \dots, α_{k}$ がそれぞれ異なるものとすると以下が成り立ちます。

$P = (\begin{matrix} 1 & α_{1} & \dots & α_{1}^{k - 1} \\ 1 & α_{2} & \dots & α_{2}^{k - 1} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 1 & α_{k} & \dots & α_{k}^{k - 1} \end{matrix}), D = (\begin{matrix} α_{1} \\ α_{2} \\ ⋱ \\ α_{k} \end{matrix})$
とおくと
$P^{- 1} = {(\frac{\sum_{l = 0}^{i - 1} c_{l} α_{j}^{l - i}}{f^{'} (α_{j})})}_{1 \leq i, j \leq k}, M^{n} = P^{- 1} D^{n} P$
が成り立つ。

　そして $P^{- 1} D^{n} P$ を実際に計算することで以下の公式が得られます。

$A_{n} = \sum_{m = 1}^{k} \frac{α_{m}^{n}}{f^{'} (α_{m})}$
とおくと
$(M^{n})_{i, j} = \sum_{l = 0}^{i - 1} c_{i - 1 - l} A_{n + j - l - 2}$
が成り立つ。

　この系として apu_yokai 氏がこちらの記事で提起していた予想が解決されます。

　 $g (x)$ を多項式とし
$A_{n}^{'} = \sum_{m = 1}^{k} \frac{α_{m}^{n}}{f^{'} (α_{m})} g (α_{m})$
とおくと
$(g (M))_{i, j} = \sum_{l = 0}^{i - 1} c_{i - 1 - l} A_{j - l - 2}^{'}$
が成り立つ。
　特に $c_{0} = c_{1} = \dots = c_{k - 1} = 1$ において
$(M^{n})_{i, j} = \sum_{l = 0}^{i - 1} F_{n + j - l - 2}^{[k]}, (f^{'} (M))_{i, j} = \sum_{l = 0}^{i - 1} L_{j - l - 2}^{[k]}$
が成り立つ。

　 $g (x) = x^{n}$ とおくと $A_{j - l - 2}^{'} = A_{n + j - l - 2}$ なので定理3はこの系に埋め込まれることになります。
　また $a_{n} = ((M^{n})^{T} a_{0})_{1} = \sum_{i = 1}^{k} (M^{n})_{i, 1} a_{i - 1}$ および
$(M^{n})_{i, 1} = \sum_{l = 0}^{i - 1} c_{i - 1 - l} A_{n - l - 1} = A_{n + k - i} - \sum_{l = 0}^{k - i - 1} c_{i + l} A_{n + l}$
から以下のように ${a_{n}}$ の一般項が求まります。

$\begin{aligned} a_{n} & = \sum_{l = 0}^{k - 1} (\sum_{i = l}^{k - 1} c_{i - l} a_{i}) A_{n - l - 1} \\ = \sum_{l = 0}^{k - 1} (a_{k - 1 - l} - \sum_{i = l + 1}^{k - 1} c_{i} a_{i - l - 1}) A_{n + l} \end{aligned}$
が成り立つ。

　ちなみに定理3を $n = 0$ において適応し $(k, j)$ 成分を比較すると漸化式から
$(M^{0})_{k, j} = (I)_{k, j} = \sum_{l = 0}^{k - 1} c_{l} A_{j - 1 - k + l} = A_{j - 1}$
となるので $A_{n}$ の一般項を漸化式で表すと以下のようになります。

　 ${A_{n}}$ は漸化式
${\begin{cases} A_{n} = 0 & (0 \leq n \leq k - 2) \\ A_{n} = 1 & (n = k - 1) \\ A_{n + k} = \sum_{j = 0}^{k - 1} c_{j} A_{n + j} & (n \geq 0) \end{cases}$
によって定まる。

　 $A_{n}$ は定理3で示した定義では扱いづらいですがこうやって漸化式で表すと色々と便利です。特に $c_{j}$ の取り方によらず初項が同じというのは扱いやすい事実ですね。

定理2の証明

　 $M^{T}$ の固有値 $α = α_{1}, α_{2}, \dots, α_{k}$ に対する固有ベクトルを考える。
$α I - M^{T} = (\begin{matrix} α & - 1 & \dots & 0 \\ 0 & α & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ - c_{0} & - c_{1} & \dots & α - c_{k - 1} \end{matrix})$
の第 $k$ 行に第 $1$ 行の $\frac{c_{0}}{α}$ 倍を足し、また第 $2$ 行の $\frac{c_{1} α + c_{0}}{α^{2}}$ 倍を足し、第 $3$ 行の $\frac{c_{2} α^{2} + c_{1} α + c_{0}}{α^{3}}$ 倍を足し、...と掃き出していくことで最終的に $(k, k)$ 成分は
$α - \frac{c_{k - 1} α^{k - 1} + c_{k - 2} α^{k - 2} + \dots + c_{0}}{α^{k - 1}} = α - \frac{α^{k}}{α^{k - 1}} = 0$
となる。そしてその状態からさらに掃き出していくことで $α I - M^{T}$ の簡約化
$(\begin{matrix} 1 & 0 & \dots & 0 & - \frac{1}{α^{k - 1}} \\ 0 & 1 & \dots & 0 & - \frac{1}{α^{k - 2}} \\ ⋮ & ⋮ & ⋱ & ⋮ & ⋮ \\ 0 & 0 & \dots & 1 & - \frac{1}{α} \\ 0 & 0 & \dots & 0 & 0 \end{matrix})$
を得る。すなわち $α$ に対する固有ベクトルは
${(\begin{matrix} 1 & α & \dots & α^{k - 2} & α^{k - 1} \end{matrix})}^{T}$
と取れるので
$P = (\begin{matrix} 1 & α_{1} & \dots & α_{1}^{k - 1} \\ 1 & α_{2} & \dots & α_{2}^{k - 1} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 1 & α_{k} & \dots & α_{k}^{k - 1} \end{matrix}), D = (\begin{matrix} α_{1} \\ α_{2} \\ ⋱ \\ α_{k} \end{matrix})$
とおくと対角化の理論から
$(P^{T})^{- 1} (M^{T})^{n} P^{T} = D^{n}$
ひいては
$P M^{n} P^{- 1} = D^{n}$
が成り立つことになる(ちなみに ${a_{n}}$ の固有方程式が重解を持つときは $P$ が正則にならないので広義固有空間 $Ker (α I - M)^{m}$ の基底を考える必要が出てくる)。
　そして $P$ は $α_{1}, α_{2}, \dots, α_{k}$ についてのヴァンデルモンド行列なのでこの記事で解説したようにその逆行列は
$P^{- 1} = {(\frac{\sum_{l = 0}^{i - 1} c_{l} α_{j}^{l - i}}{f^{'} (α_{j})})}_{1 \leq i, j \leq k}$
と求まることがわかる。

定理3の証明

　いま
$D^{n} P = (α_{i}^{n + j - 1})_{1 \leq i, j \leq k}$
に注意すると
$\begin{array}{rcl} (M^{n})_{i, j} & = & \sum_{m = 1}^{k} (P^{- 1})_{i, m} (D^{n} P)_{m, j} \\ = & \sum_{m = 1}^{k} \frac{\sum_{l = 0}^{i - 1} c_{l} α_{m}^{l - i}}{f^{'} (α_{m})} \cdot α_{m}^{n + j - 1} \\ = & \sum_{l = 0}^{i - 1} c_{l} A_{n + l - i + j - 1} \\ = & \sum_{l = 0}^{i - 1} c_{i - 1 - l} A_{n + j - l - 2} \end{array}$
と計算できる。

定理3系の証明

　いま $g (x) = \sum_{t = 0}^{d} C_{t} x^{t}$ とおくと
$\begin{array}{rcl} (g (M))_{i, j} & = & \sum_{t = 0}^{d} C_{t} (M^{t})_{i, j} \\ = & \sum_{t = 0}^{d} C_{t} \sum_{m = 1}^{k} \frac{\sum_{l = 0}^{i - 1} c_{l} α_{m}^{l - i}}{f^{'} (α_{m})} α_{m}^{t + j - 1} \\ = & \sum_{l = 0}^{i - 1} c_{l} \sum_{m = 1}^{k} \frac{α_{m}^{j + l - i - 1}}{f^{'} (α_{m})} \sum_{t = 0}^{d} C_{t} α_{m}^{t} \\ = & \sum_{l = 0}^{i - 1} c_{i - 1 - l} \sum_{m = 1}^{k} \frac{α_{m}^{j - l - 2}}{f^{'} (α_{m})} g (α_{m}) \\ = & \sum_{l = 0}^{i - 1} c_{i - 1 - l} A_{j - l - 2}^{'} \end{array}$
と計算できる。