美しき行列式たち〜第二回 - プログラムモグモグ

前回から始まった美しき行列式たち, 第二回です. 連載にはタグ『行列式』をつけています. 今回は巡回行列式(Circulant matrix)という行列を紹介します.

3. Circulant matrix

$\begin{align} \left| \left( x_{j-i\;\bmod{n}} \right) \right| = \left| \begin{array}{cccccc} x_0 & x_1 & x_2 & x_3 & \cdots & x_{n-1} \\ x_{n-1} & x_0 & x_1 & x_2 & \cdots & x_{n-2} \\ x_{n-2} & x_{n-1} & x_0 & x_1 & \cdots & x_{n-3} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ x_2 & x_3 & x_4 & x_5 & \cdots & x_1 \\ x_1 & x_2 & x_3 & x_4 & \cdots & x_0 \end{array} \right| = \prod_{\zeta^n=1} \left(\sum_{k=0}^{n-1}{\zeta^k x_k} \right) \end{align}$
行列式=何かの積和となっています. この行列は正式名称です. まずは真ん中の式を見誤らないようにして下さい. どの行も $\{x_0, x_1, \ldots , x_{n-1}\}$ のセットで, それが巡回しているんです. 右辺は1の全ての根についての積を取ります.
(証明) $\omega$ を $1$ のn乗根, $\lambda_l= \sum_{k=0}^{n-1}{\omega^{kl} x_k}$ とする. すると, 固有値及び固有ベクトルは次のようになる.
$\begin{align} \left( \begin{array}{cccccc} x_0 & x_1 & x_2 & x_3 & \cdots & x_{n-1} \\ x_{n-1} & x_0 & x_1 & x_2 & \cdots & x_{n-2} \\ x_{n-2} & x_{n-1} & x_0 & x_1 & \cdots & x_{n-3} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ x_2 & x_3 & x_4 & x_5 & \cdots & x_1 \\ x_1 & x_2 & x_3 & x_4 & \cdots & x_0 \end{array} \right) \left( \begin{array}{c} 1 \\ \omega^l \\ \omega^{2l} \\ \omega^{3l} \\ \vdots \\ \omega^{(n-1)l} \end{array} \right) = \lambda_l \left( \begin{array}{c} 1 \\ \omega^l \\ \omega^{2l} \\ \omega^{3l} \\ \vdots \\ \omega^{(n-1)l} \end{array} \right) \end{align}$
固有ベクトルが一次独立なので, 行列式は
$\left| \left( x_{j-i\;\bmod{n}} \right) \right| = \prod_{l=0}^{n-1} \lambda_l = \prod_{l=0}^{n-1} \left(\sum_{k=0}^{n-1}{\omega^{kl} x_k} \right) = \prod_{\zeta^n=1} \left(\sum_{k=0}^{n-1}{\zeta^k x_k} \right)$
となる.(証明終)
巡回していることと, n乗根が上手く効いていますね. 行列式が固有値の積というのは, 固有ベクトルを横に並べてみればすぐに分かります.

三行三列のCirculant matrixの行列式は次のようになります.
$\begin{eqnarray} \left| \begin{array}{ccc} x_0 & x_1 & x_2 \\ x_2 & x_0 & x_1 \\ x_1 & x_2 & x_0 \\ \end{array} \right| &=& (x_0+x_1+x_2)(x_0+\omega x_1+\omega^2 x_2)(x_0+\omega^2 x_1+\omega^4 x_2) \\ &=& (x_0+x_1+x_2)({x_0}^2+{x_1}^2+{x_2}^2-x_0x_1-x_1x_2-x_2x_0) \\ &=& {x_0}^3+{x_1}^3+{x_3}^3-3x_0x_1x_2 \end{eqnarray}$
おうおう, 高校生の時に見たことある形です！高校生の時はこの式と行列式の関係には気が付かなかったですね...

4. Circulant matrix - arithmetic progression

$\begin{align} \left| \left( a+(j-i\;\bmod{n})d \right) \right| &= \left| \begin{array}{cccccc} a & a+d & a+2d & a+3d & \cdots & a+(n-1)d \\ a+(n-1)d & a & a+d & a+2d & \cdots & a+(n-2)d \\ a+(n-2)d & a+(n-1)d & a & a+d & \cdots & a+(n-3)d \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ a+2d & a+3d & a+4d & a+5d & \cdots & a+d \\ a+d & a+2d & a+3d & a+4d & \cdots & a \end{array} \right| \\ &= {(-nd)}^{n-1} \left(a+\frac{n-1}{2}d\right) \end{align}$
巡回行列式の1つ. 等差数列になってます. 先程の, 巡回行列式の一般式では $1$ の根が出てきて中々見通しが悪かったんですが, 具体的な数列を入れてみる事でものすごく簡約できるんですね. この行列の証明はほかのとは異なり, 行列のサイズを変えずに $0$ をいっぱい作っていって行います.
(証明)
$\begin{align} \left| \left( a+(j-i\;\bmod{n})d \right) \right| &= \left| \begin{array}{ccccccc} a & a+d & a+2d & a+3d & \cdots & a+(n-2)d & a+(n-1)d \\ a+(n-1)d & a & a+d & a+2d & \cdots & a+(n-3)d & a+(n-2)d \\ a+(n-2)d & a+(n-1)d & a & a+d & \cdots & a+(n-4)d & a+(n-3)d \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ a+2d & a+3d & a+4d & a+5d & \cdots & a & a+d \\ a+d & a+2d & a+3d & a+4d & \cdots & a+(n-1)d & a \end{array} \right| \\ &= \left| \begin{array}{ccccccc} a & d & d & d & \cdots & d & d \\ a+(n-1)d & -(n-1)d & d & d & \cdots & d & d \\ a+(n-2)d & d & -(n-1)d & d & \cdots & d & d \\ \vdots & \vdots & \ddots & \ddots & \ddots & \ddots & \vdots \\ a+2d & d & d & d & \cdots & -(n-1)d & d \\ a+d & d & d & d & \cdots & d & -(n-1)d \end{array} \right| \\ &= \left| \begin{array}{ccccccc} a & 0 & 0 & 0 & \cdots & 0 & d \\ a+(n-1)d & -nd & 0 & 0 & \cdots & 0 & d \\ a+(n-2)d & 0 & -nd & 0 & \cdots & 0 & d \\ \vdots & \vdots & \ddots & \ddots & \ddots & \ddots & \vdots \\ a+2d & 0 & 0 & 0 & \cdots & -nd & d \\ a+d & nd & nd & nd & \cdots & nd & -(n-1)d \end{array} \right| \\ &= \left| \begin{array}{ccccccc} a & 0 & 0 & 0 & \cdots & 0 & d \\ (n-1)d & -nd & 0 & 0 & \cdots & 0 & 0 \\ (n-2)d & 0 & -nd & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & \ddots & \vdots \\ 2d & 0 & 0 & 0 & \cdots & -nd & 0 \\ d & nd & nd & nd & \cdots & nd & -nd \end{array} \right| \\ &= \left| \begin{array}{ccccccc} a & 0 & 0 & 0 & \cdots & 0 & d \\ (n-1)d & -nd & 0 & 0 & \cdots & 0 & 0 \\ (n-2)d & 0 & -nd & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & \ddots & \vdots \\ 2d & 0 & 0 & 0 & \cdots & -nd & 0 \\ \frac{n(n-1)d}{2} & 0 & 0 & 0 & \cdots & 0 & -nd \end{array} \right| \\ &= a {(-nd)}^{n-1}-\frac{n(n-1)d}{2}{(-nd)}^{n-2}d \\ &= {(-nd)}^{n-1} \left(a+\frac{n-1}{2}d\right) \end{align}$
(証明終)

5. Circulant matrix - one two three

$\begin{align} \left| \left( 1+(j-i\;\bmod{n}) \right) \right| = \left| \begin{array}{cccccc} 1 & 2 & 3 & 4 & \cdots & n \\ n & 1 & 2 & 3 & \cdots & n-1 \\ n-1 & n & 1 & 2 & \cdots & n-2 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 3 & 4 & 5 & 6 & \cdots & 2 \\ 2 & 3 & 4 & 5 & \cdots & 1 \end{array} \right| &= \frac{{(-n)}^{n-1}(n+1)}{2} \end{align}$
これは先程の等差数列の巡回行列式の結果から直ぐに出てきます. オーダー的には $n^n$ と, 行列がかなり密に詰まっていることが分かります. 計算はさっきの式に代入するだけなので省略します.

3つ紹介しました. まぁ全部巡回行列式なんですけど, 特殊化により見えてくるものもあるものです. 明日はまた違った形状の行列式を紹介しますよ. お楽しみに♪