フロベニウスの同伴行列(companion matrix)の定義と応用

メルセンヌ・ツイスタ(Mersenne Twister)法まとめ

上記でまとめたメルセンヌ・ツイスタ(Mersenne Twister)法ではフロベニウスの同伴行列(companion matrix)が用いられます。当記事では同伴行列の定義と応用に関して取りまとめを行いました。

・数学まとめ
https://www.hello-statisticians.com/math_basic

同伴行列の概要

同伴行列(companion matrix)の定義

フロベニウスの同伴行列(companion matrix)は下記のように定められる。
$$
\large
\begin{align}
C_{n} = \left(\begin{array}{cccccc} 0 & 1 & 0 & \cdots & \cdots & 0 \\ 0 & 0 & 1 & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 & 1 & 0 \\ 0 & 0 & \cdots & \cdots & 0 & 1 \\ -c_0 & -c_1 & \cdots & \cdots & -c_{n-2} & -c_{n-1} \end{array} \right)
\end{align}
$$

同伴行列と固有多項式

下記のように$n$次多項式$p(\lambda)$を定める。
$$
\large
\begin{align}
p(\lambda) = c_0 + c_1 \lambda + c_2 \lambda^2 + \cdots + c_{n-1} \lambda^{n-1} + \lambda^{n}
\end{align}
$$

以下、$p(\lambda)=0$と$\det{(\lambda I_n – C_n)}=0$が同値であることを示す。$\det{(\lambda I_n – C_n)}$は余因子展開を用いて下記のように変形できる。
$$
\begin{align}
& \det{(\lambda I_n – C_n)} = \left| \begin{array}{cccccc} \lambda & -1 & 0 & \cdots & \cdots & 0 \\ 0 & \lambda & -1 & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda & -1 & 0 \\ 0 & 0 & \cdots & \cdots & \lambda & -1 \\ c_0 & c_1 & \cdots & \cdots & c_{n-2} & \lambda+c_{n-1} \end{array} \right| \\
&= \lambda (-1)^{1+1} \left| \begin{array}{cccccc} \lambda & -1 & 0 & \cdots & \cdots & 0 \\ 0 & \lambda & -1 & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda & -1 & 0 \\ 0 & 0 & \cdots & \cdots & \lambda & -1 \\ c_1 & c_2 & \cdots & \cdots & c_{n-2} & \lambda + c_{n-1} \end{array} \right| + c_0 (-1)^{n+1} \left| \begin{array}{ccccc} -1 & 0 & \cdots & \cdots & 0 \\ \lambda & -1 & 0 & \cdots & 0 \\ \vdots & \ddots & \ddots & \ddots & \vdots \\ 0 & \cdots & \lambda & -1 & 0 \\ 0 & \cdots & \cdots & \lambda & -1 \end{array} \right| \\
&= \lambda (-1)^{1+1} \left| \begin{array}{cccccc} \lambda & -1 & 0 & \cdots & \cdots & 0 \\ 0 & \lambda & -1 & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda & -1 & 0 \\ 0 & 0 & \cdots & \cdots & \lambda & -1 \\ c_1 & c_2 & \cdots & \cdots & c_{n-2} & \lambda + c_{n-1} \end{array} \right| + c_0 (-1)^{n+1+(n-1)} \\
&= \lambda \left| \begin{array}{cccccc} \lambda & -1 & 0 & \cdots & \cdots & 0 \\ 0 & \lambda & -1 & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda & -1 & 0 \\ 0 & 0 & \cdots & \cdots & \lambda & -1 \\ c_1 & c_2 & \cdots & \cdots & c_{n-2} & \lambda + c_{n-1} \end{array} \right| + c_0 \\
&= \lambda^2 (-1)^{1+1} \left| \begin{array}{cccccc} \lambda & -1 & 0 & \cdots & \cdots & 0 \\ 0 & \lambda & -1 & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda & -1 & 0 \\ 0 & 0 & \cdots & \cdots & \lambda & -1 \\ c_2 & c_3 & \cdots & \cdots & c_{n-2} & \lambda + c_{n-1} \end{array} \right| + c_1 \lambda + c_0 \\
&= \lambda^3 (-1)^{1+1} \left| \begin{array}{cccccc} \lambda & -1 & 0 & \cdots & \cdots & 0 \\ 0 & \lambda & -1 & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda & -1 & 0 \\ 0 & 0 & \cdots & \cdots & \lambda & -1 \\ c_2 & c_3 & \cdots & \cdots & c_{n-2} & \lambda + c_{n-1} \end{array} \right| + c_2 \lambda^2 + c_1 \lambda + c_0 \\
&= \; \cdots \\
&= c_0 + c_1 \lambda + c_2 \lambda^2 + \cdots + c_{n-1} \lambda^{n-1} + \lambda^{n}
\end{align}
$$

上記より$p(\lambda)=0 \iff \det{(\lambda I_n – C_n)}=0$であることが確認できる。

参考

・Wikipedia：同伴行列
・線形空間と固有値の応用