行列式がフィボナッチ数列になる行列

フィボナッチ数列

\[ 1, 2, 3, 5, 8, 13, 21, \dots \]

の第n項を \(F_n\) と置くと、\(i\) を純虚数として \(i, 1, i\) が並ぶ以下のような \(n\times n\) の三重対角行列の行列式は \(F_n\) に一致します。

\[ \left|\begin{matrix} 1 & i & & & \\ i & 1 & i & & \\ & i & \ddots & \ddots & \\ & & \ddots & \ddots & i \\ & & & i & 1 \end{matrix}\right| = F_n \]

行列の数字が書かれていない要素は0です。まずはこの事実を計算して確かめてみましょう。

行列式の余因子展開

本稿では行列の実装として二重リストを使用します。

-- 行列
type Matrix a = [[a]]

後々必要になるので、先に行列を整形して表示する関数も用意しておきましょう。

import Data.List (intercalate)

-- | 行列を整形して表示する
displayM :: Show a => Matrix a -> IO ()
displayM = putStrLn . intercalate "\n" . map (unwords . map show)

行列式を効率よく計算するにはLU分解を使用するのが良いですが、今回はシンプルに行列式の余因子展開を使って再帰的に計算します。

-- 行列式
det :: Num a => Matrix a -> a
det [[x]] = x
det xss = foldr1 (-) (zipWith (*) col1 (map det (minors cols)))
  where
    col1 = map head xss
    cols = map tail xss

-- | 与えられたリストから要素を一つ除いたリストのリストを生成する
-- | >>> minors [1,2,3,4]
-- [[2,3,4],[1,3,4],[1,2,4],[1,2,3]]
minors :: [a] -> [[a]]
minors []     = []
minors (x:xs) = xs : map (x:) (minors xs)

こちらの実装は『関数プログラミング 珠玉のアルゴリズムデザイン』で紹介されているものを元にしており、同書の「行列式の3つの計算法」という章では他にも面白い行列式の計算方法が解説されているので気になる人はぜひ読んでみてください。

簡単な例で実際に行列式が計算できることを確かめてみましょう。

det [[1, 2], [3, 4]]

-2

\(1\times 4 - 2\times 3 = -2\) なので正解ですね。

次に行列式がフィボナッチ数列となる行列を生成する関数を実装しましょう。

まずは複素数を用意します。

import Data.Complex

-- | 複素数
type C = Complex Float

-- | 純虚数
i :: C 
i = 0.0 :+ 1.0

\(i, 1, i\) が並ぶような \(n\times n\) の三重対角行列を生成する関数 fibM を実装します。

-- 行列式がフィボナッチ数列となるn次行列
fibM :: Int -> Matrix C
fibM 1 = [[1.0]]
fibM n =
  let fibM' = fibM (n-1)
   in (1.0 : i : replicate (n-2) 0) : (i : head fibM') : map (0:) (tail fibM')

実際に想定通りの行列が生成されているか確認してみましょう

displayM (fibM 2)

1.0 :+ 0.0 0.0 :+ 1.0
0.0 :+ 1.0 1.0 :+ 0.0

displayM (fibM 3)

1.0 :+ 0.0 0.0 :+ 1.0 0.0 :+ 0.0
0.0 :+ 1.0 1.0 :+ 0.0 0.0 :+ 1.0
0.0 :+ 0.0 0.0 :+ 1.0 1.0 :+ 0.0

displayM (fibM 4)

1.0 :+ 0.0 0.0 :+ 1.0 0.0 :+ 0.0 0.0 :+ 0.0
0.0 :+ 1.0 1.0 :+ 0.0 0.0 :+ 1.0 0.0 :+ 0.0
0.0 :+ 0.0 0.0 :+ 1.0 1.0 :+ 0.0 0.0 :+ 1.0
0.0 :+ 0.0 0.0 :+ 0.0 0.0 :+ 1.0 1.0 :+ 0.0

少し目がチカチカしますがうまく行ってますね！

それではこれらの行列の行列式を計算してみましょう。

mapM_ (print . det . fibM) [1..10]

1.0 :+ 0.0
2.0 :+ 0.0
3.0 :+ 0.0
5.0 :+ 0.0
8.0 :+ 0.0
13.0 :+ 0.0
21.0 :+ 0.0
34.0 :+ 0.0
55.0 :+ 0.0
89.0 :+ 0.0

実際にフィボナッチ数列が得られることが確認できました！

証明

なぜこのような行列の行列式でフィボナッチ数列が現れるのでしょうか？いくつか具体的に計算して考えてみましょう。

まず2次の行列の場合

\[ \left|\begin{matrix} 1 & i\\ i & 1\\ \end{matrix}\right| \]

行列式は \(1\times 1 - i\times i = 2\) で確かに\(F_2\)になります。

次に3次の行列の場合

\[ \left|\begin{matrix} 1 & i & 0\\ i & 1 & i\\ 0 & i & 1\\ \end{matrix}\right| \]

1行目を使って行列式の余因子展開を考えると、行列式は

\[ 1\times\left|\begin{matrix} 1 & i\\ i & 1\\ \end{matrix}\right| -i\times\left|\begin{matrix} i & i\\ 0 & 1\\ \end{matrix}\right| = 1\times F_2 - i\times i = 3 \]

で確かに\(F_3\)となります。

そして4次の行列の場合

\[ \left|\begin{matrix} 1 & i & 0 & 0\\ i & 1 & i & 0\\ 0 & i & 1 & i\\ 0 & 0 & i & 1\\ \end{matrix}\right| \]

1行目を使って行列式の余因子展開を考えると、行列式は

\[ 1\times\left|\begin{matrix} 1 & i & 0\\ i & 1 & i\\ 0 & i & 1\\ \end{matrix}\right| -i\left|\begin{matrix} i & i & 0\\ 0 & 1 & i\\ 0 & i & 1\\ \end{matrix}\right| =1\times F_3 - i \left( i\times\left|\begin{matrix} 1 & i\\ i & 1\\ \end{matrix}\right| -i\times\left|\begin{matrix} 0 & i\\ 0 & 1\\ \end{matrix}\right| \right) =F_3-i\times i\times F_2 =F_3+F_2 =F_4 \]

でフィボナッチ数列の定義より確かに\(F_4\)に一致します。

ここまで確認すれば行列式がフィボナッチ数列とどのように対応しているかは明白ですね！

実は三重対角行列の行列式は一般的に

\[ f_n = \left|\begin{matrix} a_1 & b_1 & & & \\ c_1 & a_2 & b_2 & & \\ & c_2 & \ddots & \ddots & \\ & & \ddots & \ddots & b_{n-1} \\ & & & c_{n-1} & a_n \\ \end{matrix}\right| \]

と置くと

\[ f_n = a_nf_{n-1} - c_{n-1}b_{n-1}f_{n-2} \]

という漸化式で計算できることが知られています（参考）。フィボナッチ数列を生成する行列はこの漸化式がうまくフィボナッチ数列の漸化式になるように調整されていたんですね。

仕組みが分かれば純虚数\(i\)を使わなくても、例えば以下の様な行列の行列式でフィボナッチ数列が計算できることが分かります。

\[ \left|\begin{matrix} 1 & -1 & & & \\ 1 & 1 & -1 & & \\ & 1 & \ddots & \ddots & \\ & & \ddots & \ddots & -1 \\ & & & 1 & 1 \end{matrix}\right| \]

最後のこの行列式がフィボナッチ数列と一致することを確認してみましょう。

fibM2 :: Int -> Matrix Int
fibM2 1 = [[1]]
fibM2 n =
  let fibM2' = fibM2 (n-1)
   in (1 : -1 : replicate (n-2) 0) : (1 : head fibM2') : map (0:) (tail fibM2')

displayM (fibM2 2)

1 -1
1 1

displayM (fibM2 3)

1 -1 0
1 1 -1
0 1 1

displayM (fibM2 4)

1 -1 0 0
1 1 -1 0
0 1 1 -1
0 0 1 1

行列式を計算すると

mapM_ (print . det . fibM2) [1..10]

1
2
3
5
8
13
21
34
55
89

フィボナッチ数列に一致することが確認できました👏