同伴行列

同義語：コンパニオン行列companion matrix

概要

前提知識: 固有多項式, 最小多項式(線形代数), 相似(行列)

Fibonacci 数列 $F_0=0$、$F_1=1$、$F_{m+2}=F_{m+1}+F_m$ は、行列を使うと
$$ \begin{pmatrix}F_{m+1}\\F_{m+2}\end{pmatrix}=\begin{pmatrix}0&1\\1&1\end{pmatrix}\begin{pmatrix}F_m\\F_{m+1}\end{pmatrix} $$
と 1 段ずつ進められる。右辺の行列の固有多項式は $x^2-x-1$ で、これは漸化式の特性方程式そのものである。このように、与えられた多項式 $f$ を固有多項式にもつ行列を係数から直接書き下したものが 同伴行列 である。同伴行列は、$f$ の根の問題を行列の固有値の問題に言い換え、漸化式や高階の線形微分方程式を 1 階の連立の形に直し、さらに「すべての正方行列は同伴行列を対角に並べた行列に相似である」という有理標準形の部品になる。この記事では、同伴行列の固有多項式と最小多項式がともに $f$ であることを証明し、固有ベクトル、対角化できる条件、同伴行列に相似な行列の特徴づけを述べる。

定義

以下、$K$ は体、$M_n(K)$ は $K$ の元を成分とする $n$ 次正方行列の全体、$e_1,\dots,e_n$ は $K^n$ の標準基底とする。最高次の係数が $1$ の多項式を モニック という。$A\in M_n(K)$ の固有多項式を $\chi_A(x):=\det(xI_n-A)$、最小多項式を $\mu_A$ と書く。

多項式の同伴行列

$f(x)=x^n+c_{n-1}x^{n-1}+\cdots+c_1x+c_0\in K[x]$（$n\ge1$）をモニックな多項式とする。$n$ 次正方行列
$$ C(f):=\begin{pmatrix} 0&0&\cdots&0&-c_0\\ 1&0&\cdots&0&-c_1\\ 0&1&\cdots&0&-c_2\\ \vdots&&\ddots&&\vdots\\ 0&0&\cdots&1&-c_{n-1} \end{pmatrix} $$
を $f$ の 同伴行列（companion matrix）という。すなわち、対角線のすぐ下に $1$ を並べ、最後の列に $-c_0,\dots,-c_{n-1}$ を並べ、ほかの成分を $0$ とした行列である。$n=1$ では $C(f)=(-c_0)$ である。

列ごとに見ると
$$ C(f)e_j=e_{j+1}\quad(1\le j< n),\qquad C(f)e_n=-\sum_{k=0}^{n-1}c_ke_{k+1} $$
である。とくに $e_1,\ C(f)e_1,\dots,C(f)^{n-1}e_1$ は $e_1,e_2,\dots,e_n$ そのものである。

流儀の違い

同伴行列の形は文献によって違う。$C(f)$ の転置（対角線のすぐ上に $1$、最後の行に $-c_0,\dots,-c_{n-1}$）を同伴行列とよぶ流儀や、第 1 行に $-c_{n-1},\dots,-c_0$ を並べ、対角線のすぐ下に $1$ を並べる流儀がある（漸化式の行列表示の記事の $\begin{pmatrix}p&q\\1&0\end{pmatrix}$ は $f(t)=t^2-pt-q$ についての後者の形である）。後者は $C(f)^{\top}$ の行と列の順序をともに逆にした行列 $RC(f)^{\top}R^{-1}$（$R$ は座標の順序を逆にする置換行列）である。$C(f)^{\top}$ の固有多項式は $C(f)$ と同じ $f$ であり、多項式 $g$ について $g(C(f)^{\top})=g(C(f))^{\top}$ なので最小多項式も $f$ である。よって thm-companion-similar により $C(f)^{\top}$ は $C(f)$ に相似であり、これらはすべて $C(f)$ に相似で、以下の固有多項式・最小多項式・対角化についての主張はどの流儀でも同じである。

直感

$K[x]$ を $f$ で割った剰余環 $K[x]/(f)$ で「$x$ を掛ける」写像を考えると、その表現行列が $C(f)$ になる（prop-companion-quotient）。剰余環の中では $x^n$ は $-c_0-c_1x-\cdots-c_{n-1}x^{n-1}$ に等しいので、$1,x,\dots,x^{n-1}$ に $x$ を掛けると、最後の $x^{n-1}$ だけが「$f$ を使って低い次数に書き直される」。同伴行列は「$x$ が $f(x)=0$ を満たすときの $x$ 倍」を行列にしたものであり、$f(C(f))=O$ となるのは当然である。

剰余環での $x$ 倍

$x$ 倍の表現行列

$f\in K[x]$ をモニックで $\deg f=n\ge1$ とし、$A:=K[x]/(f)$、$\bar g$ を $g\in K[x]$ の類とする。

$\bar1,\bar x,\dots,\bar x^{\,n-1}$ は $K$ 上のベクトル空間 $A$ の基底である。
$K$ 線形写像 $m_x\colon A\to A$、$\bar g\mapsto\bar x\bar g$ の、この基底に関する表現行列は $C(f)$ である。

1：$f$ はモニックなので、任意の $g\in K[x]$ は $g=qf+r$（$\deg r< n$ または $r=0$）と割り算でき、$\bar g=\bar r$ は $\bar1,\dots,\bar x^{\,n-1}$ の線形結合である。$\sum_{k< n}a_k\bar x^{\,k}=0$ なら $f$ が $\sum_ka_kx^k$ を割り切るが、後者の次数は $n$ 未満なので $\sum_ka_kx^k=0$、すなわちすべての $a_k=0$ である。
2：$j< n$ では $m_x(\bar x^{\,j-1})=\bar x^{\,j}$ であり、$\bar f=0$ から $m_x(\bar x^{\,n-1})=\bar x^{\,n}=-\sum_{k=0}^{n-1}c_k\bar x^{\,k}$ である。$\bar x^{\,j-1}$ を第 $j$ の基底とみると、これは $C(f)$ の列の式と同じである。$\square$

固有多項式と最小多項式

同伴行列の固有多項式と最小多項式

$f\in K[x]$ をモニックで $\deg f=n\ge1$ とし、$C:=C(f)$ とする。

$\chi_C=f$ である。
$f(C)=O$ であり、$\mu_C=f$ である。
$e_1$ は $C$ の巡回ベクトルである。すなわち $e_1,Ce_1,\dots,C^{n-1}e_1$ は $K^n$ の基底である。

第 1 行に他の行の $x$ 冪倍を加える

3：列の式から $C^{j-1}e_1=e_j$（$j=1,\dots,n$）である。
1：$n=1$ では $\chi_C(x)=x+c_0=f(x)$ である。$n\ge2$ とし、$T:=xI_n-C$ を $K[x]$ の元を成分とする行列とみる。$T$ の第 $i$ 行を $r_i$ と書くと、$r_1$ は第 $1$ 列に $x$、第 $n$ 列に $c_0$ をもち、$2\le i\le n-1$ の $r_i$ は第 $i-1$ 列に $-1$、第 $i$ 列に $x$、第 $n$ 列に $c_{i-1}$ をもち、$r_n$ は第 $n-1$ 列に $-1$、第 $n$ 列に $x+c_{n-1}$ をもつ（ほかの成分は $0$）。第 1 行を
$$ r_1':=r_1+xr_2+x^2r_3+\cdots+x^{n-1}r_n $$
に取り替える。第 $j$ 列（$j< n$）には、$x^{j-1}r_j$ から $x^{j-1}\cdot x=x^j$、$x^jr_{j+1}$ から $x^j\cdot(-1)=-x^j$ が来るだけなので、和は $0$ である。第 $n$ 列は
$$ c_0+xc_1+\cdots+x^{n-2}c_{n-2}+x^{n-1}(x+c_{n-1})=f(x) $$
である。ある行に別の行の倍を加えても行列式は変わらないので（行列式の記事の定理「多重線形性と交代性」の 4。同記事の注意「可換環上の行列式」のとおり、成分が $K[x]$ でもそのまま使える）、$\det T$ は第 1 行が $(0,\dots,0,f(x))$ の行列の行列式に等しい。これを第 1 行で余因子展開すると（同記事の定理「行と列に関する余因子展開」）$\det T=(-1)^{1+n}f(x)\det T'$ で、$T'$ は $T$ から第 1 行と第 $n$ 列を除いた $n-1$ 次の行列である。$T'$ の $(i-1,i-1)$ 成分は $r_i$ の第 $i-1$ 列の $-1$、$(i-1,i)$ 成分は $x$（$i\le n-1$）で、それより左下は $0$ なので、$T'$ は対角成分がすべて $-1$ の上三角行列であり、$\det T'=(-1)^{n-1}$ である。よって $\chi_C(x)=\det T=(-1)^{1+n}(-1)^{n-1}f(x)=f(x)$ である。
2：まず $f(C)e_1=0$ を示す。3 により $C^ke_1=e_{k+1}$（$k< n$）で、$C^ne_1=Ce_n=-\sum_{k< n}c_ke_{k+1}$ なので
$$ f(C)e_1=C^ne_1+\sum_{k=0}^{n-1}c_kC^ke_1=-\sum_{k< n}c_ke_{k+1}+\sum_{k< n}c_ke_{k+1}=0 $$
である。$C$ と $f(C)$ は可換なので、$f(C)e_{j}=f(C)C^{j-1}e_1=C^{j-1}f(C)e_1=0$（$j=1,\dots,n$）であり、$f(C)=O$ である。
次に、$0$ でない $g=\sum_{k=0}^mg_kx^k$（$m< n$）について、$g(C)e_1=\sum_{k=0}^mg_ke_{k+1}\ne0$ なので $g(C)\ne O$ である。したがって $\deg\mu_C\ge n$ である。$f(C)=O$ なので $\mu_C$ は $f$ を割り切り（最小多項式(線形代数) の記事の命題「零化多項式は最小多項式の倍数」）、どちらもモニックで $\deg f=n\le\deg\mu_C$ だから $\mu_C=f$ である。$\square$

1 の証明は $x$ を変数のまま扱い、体の性質（割り算・逆元）を使っていない。したがって 1 は、成分が任意の可換環 $R$ にある場合にも、モニックな $f\in R[x]$ について $\det(xI_n-C(f))=f$ として成り立つ。2 の $f(C)=O$ は、Cayley–Hamiltonの定理を同伴行列に使っても得られるが、上の証明は Cayley–Hamilton の定理を使わない。

小さい次数の同伴行列

$f(x)=x^2+1$ のとき $C(f)=\begin{pmatrix}0&-1\\1&0\end{pmatrix}$ で、$\mathbb{R}^2$ の $90^\circ$ の回転である。固有多項式 $x^2+1$ は $\mathbb{R}$ に根をもたないので、$\mathbb{R}$ の上では固有値をもたない。$\mathbb{C}$ の上では固有値 $\pm i$ をもつ。
$f(x)=x^n$ のとき $C(f)$ は $e_j\mapsto e_{j+1}$、$e_n\mapsto0$ のずらしの行列で、$C(f)^{n-1}\ne O$、$C(f)^n=O$ である。$\mu=x^n$ はこのことを表す。
$f(x)=x^n-1$ のとき $c_0=-1$、ほかの $c_k=0$ なので、$C(f)$ は $e_1\mapsto e_2\mapsto\cdots\mapsto e_n\mapsto e_1$ と基底を巡回させる置換の行列である。その固有値は $1$ の $n$ 乗根である。
冒頭の Fibonacci 数列の行列は $f(x)=x^2-x-1$（$c_0=c_1=-1$）の同伴行列 $C(f)=\begin{pmatrix}0&1\\1&1\end{pmatrix}$ であり、この場合はたまたま対称行列である。

固有ベクトルと対角化

同伴行列の固有ベクトル

$f\in K[x]$ をモニックで $\deg f=n\ge1$、$C:=C(f)$ とし、$\lambda\in K$ を $f$ の根とする。

$q_\lambda(x):=f(x)/(x-\lambda)=\sum_{k=0}^{n-1}b_kx^k$ の係数を並べた $b:=(b_0,\dots,b_{n-1})^{\top}$ は、固有値 $\lambda$ に対する $C$ の固有ベクトルである。
$v_\lambda:=(1,\lambda,\lambda^2,\dots,\lambda^{n-1})^{\top}$ は、固有値 $\lambda$ に対する $C^{\top}$ の固有ベクトルである。
$C$ の固有値 $\lambda$ に対する固有空間は 1 次元である。すなわち、$C$ のどの固有値も幾何重複度は $1$ である。

1：prop-companion-quotient により、座標ベクトル $b$ に $C$ を掛けることは、$K[x]/(f)$ の類 $\bar q_\lambda$ に $\bar x$ を掛けることにあたる。$xq_\lambda=(x-\lambda)q_\lambda+\lambda q_\lambda=f+\lambda q_\lambda$ なので $\bar x\bar q_\lambda=\lambda\bar q_\lambda$ であり、$Cb=\lambda b$ である。$q_\lambda$ はモニックで次数 $n-1$ なので $b_{n-1}=1$ で、$b\ne0$ である。
2：$C^{\top}$ は対角線のすぐ上に $1$、最後の行に $-c_0,\dots,-c_{n-1}$ をもつので、
$$ C^{\top}v_\lambda=\Bigl(\lambda,\lambda^2,\dots,\lambda^{n-1},\ -\sum_{k=0}^{n-1}c_k\lambda^k\Bigr)^{\top}=\lambda v_\lambda $$
である。最後の成分は $f(\lambda)=0$ から $-\sum_kc_k\lambda^k=\lambda^n$ による。
3：$\lambda I_n-C$ から第 1 行と第 $n$ 列を除いた $n-1$ 次の行列は、prf-companion-main の $T'$ で $x$ に $\lambda$ を代入したもので、対角成分がすべて $-1$ の上三角行列である。その行列式は $(-1)^{n-1}\ne0$ なので $\operatorname{rank}(\lambda I_n-C)\ge n-1$ であり、固有空間 $\ker(\lambda I_n-C)$ の次元は $1$ 以下である。$\lambda$ は固有値なので次元はちょうど $1$ である。$\square$

同伴行列が対角化できる条件

$C(f)$ が $K$ 上で対角化可能であることと、$f$ が $K[x]$ で相異なる 1 次式の積 $(x-\lambda_1)\cdots(x-\lambda_n)$ に分解することは同値である。このとき、$v_{\lambda_1},\dots,v_{\lambda_n}$ を列に並べた Vandermonde 行列 $V$ について $V^{-1}C(f)^{\top}V=\operatorname{diag}(\lambda_1,\dots,\lambda_n)$ である。

thm-companion-main の 2 により $\mu_{C(f)}=f$ であり、最小多項式(線形代数) の記事の定理「対角化の判定」により、対角化可能であることは最小多項式が相異なる 1 次式の積に分解することと同値である。後半：prop-companion-eigen の 2 により $C(f)^{\top}V=V\operatorname{diag}(\lambda_1,\dots,\lambda_n)$ であり、$\lambda_i$ が相異なるので Vandermonde の行列式 $\det V=\prod_{i< j}(\lambda_j-\lambda_i)$ は $0$ でない（Vandermonde行列式）。$\square$

固有値の重複は、prop-companion-eigen の 3 から次のように読める。同伴行列では各固有値の固有空間が 1 次元なので、$f$ が重根 $\lambda$ をもつと、$\lambda$ の代数重複度（根の重複度）は幾何重複度 $1$ より大きくなり、対角化できない。$f=(x-1)^2$ の $C(f)=\begin{pmatrix}0&-1\\1&2\end{pmatrix}$ がその例である。

Fibonacci 数の一般項

$f(x)=x^2-x-1$ の根を $\varphi=\frac{1+\sqrt5}2$、$\psi=\frac{1-\sqrt5}2$ とする（$K=\mathbb{R}$）。根は相異なるので、cor-companion-diagonalizable により $V=\begin{pmatrix}1&1\\\varphi&\psi\end{pmatrix}$ で $C^{\top}=V\operatorname{diag}(\varphi,\psi)V^{-1}$ である（ここでは $C=C^{\top}$）。$s_m:=(F_m,F_{m+1})^{\top}=C^ms_0$、$s_0=(0,1)^{\top}$ なので
$$ s_m=V\begin{pmatrix}\varphi^m&0\\0&\psi^m\end{pmatrix}V^{-1}s_0,\qquad V^{-1}s_0=\frac1{\psi-\varphi}\begin{pmatrix}\psi&-1\\-\varphi&1\end{pmatrix}\begin{pmatrix}0\\1\end{pmatrix}=\frac1{\sqrt5}\begin{pmatrix}1\\-1\end{pmatrix} $$
であり、第 1 成分をとって $F_m=\frac{\varphi^m-\psi^m}{\sqrt5}$ を得る（$\psi-\varphi=-\sqrt5$ を使った）。

同伴行列に相似な行列

同伴行列に相似な行列の特徴づけ

$A\in M_n(K)$ について、次は同値である。

$A$ はある同伴行列に相似である。
$A$ は巡回ベクトルをもつ。
$\mu_A=\chi_A$ である。
このとき $A$ は $C(\chi_A)$ に相似である。とくに、モニックな $f,g$ について $C(f)$ と $C(g)$ が相似であることと $f=g$ は同値である。

1 ⇒ 2：$P^{-1}AP=C(f)$ とする。thm-companion-main の 3 により $e_1,C(f)e_1,\dots,C(f)^{n-1}e_1$ は基底であり、$A^kPe_1=PC(f)^ke_1$ なので、$Pe_1$ は $A$ の巡回ベクトルである。
2 ⇒ 1：相似(行列) の記事の定理「巡回ベクトルをもつ行列の相似」の 1 による。巡回ベクトル $v$ に対し $P:=(v\ Av\ \cdots\ A^{n-1}v)$ とおくと $P^{-1}AP=C(\chi_A)$ となる。
1 ⇒ 3：相似な行列の固有多項式と最小多項式は等しいので、thm-companion-main の 1・2 により $\mu_A=\mu_{C(f)}=f=\chi_{C(f)}=\chi_A$ である。
3 ⇒ 2：有理標準形の記事の系「巡回ベクトルをもつ行列」による（不変因子の理論を使う）。
最後の主張：1 のとき $\chi_A=\chi_{C(f)}=f$ なので $A$ は $C(\chi_A)$ に相似である。$C(f)\sim C(g)$ なら固有多項式を比べて $f=g$ であり、逆は明らかである。$\square$

一般の正方行列は 1 つの同伴行列に相似とは限らないが、同伴行列をいくつか対角に並べた行列 $C(a_1)\oplus\cdots\oplus C(a_m)$（$a_1\mid\cdots\mid a_m$）にはただ 1 通りに相似になる。これが有理標準形であり、同伴行列はその部品である。

応用

線形漸化式と高階の線形微分方程式

$K$ の数列 $(a_m)$ が $a_{m+n}+c_{n-1}a_{m+n-1}+\cdots+c_0a_m=0$（すべての $m\ge0$）を満たすとき、$s_m:=(a_m,a_{m+1},\dots,a_{m+n-1})^{\top}$ とおくと、$s_{m+1}$ の最後の成分は $a_{m+n}=-\sum_kc_ka_{m+k}$ なので $s_{m+1}=C(f)^{\top}s_m$、したがって $s_m=(C(f)^{\top})^ms_0$ である。cor-companion-diagonalizable の対角化から、$f$ の根が相異なるとき一般項は $a_m=\sum_i\alpha_i\lambda_i^m$ の形になる（ex-companion-fibonacci）。同じように、定数係数の方程式 $y^{(n)}+c_{n-1}y^{(n-1)}+\cdots+c_0y=0$ は、$Y:=(y,y',\dots,y^{(n-1)})^{\top}$ についての 1 階の連立方程式 $Y'=C(f)^{\top}Y$ と同値である（線形微分方程式）。2 項の漸化式の場合は漸化式の行列表示が詳しく扱う。

根と固有値

thm-companion-main の 1 により、モニックな多項式の根は同伴行列の固有値にほかならない。とくに、任意のモニックな多項式はある行列の固有多項式であり最小多項式でもある。このことから、5 次以上の正方行列の固有値を成分から四則演算と冪根だけで求める一般の公式は存在しない。そのような公式があれば同伴行列に使って 5 次方程式の根の公式が得られ、Abel–Ruffiniの定理に反するからである。また、有理数係数の行列の固有値は代数的数であり、逆に代数的数 $\alpha$ はその最小多項式の同伴行列の固有値として現れる。これは代数的数の記事で、代数的数の和と積が代数的数であることを示すのに使われている。

条件を外した反例

外す条件	反例	成り立たなくなること
$\mu_A=\chi_A$	$A=I_2$、$f=(x-1)^2$	$\chi_A=f$ から $A\sim C(f)$ を結論すること
$f$ の根が相異なる	$C\bigl((x-1)^2\bigr)=\begin{pmatrix}0&-1\\1&2\end{pmatrix}$	対角化可能であること
$f$ が $K$ で 1 次式に分解する	$K=\mathbb{R}$、$C(x^2+1)$	$K$ 上で固有値をもち、対角化可能であること
（巡回ベクトルは $e_1$ などに限る）	$C(x^2)$ と $v=e_2$	$0$ でないベクトルがすべて巡回ベクトルであること

反例：表の各行の確かめ

1 行目：$\chi_{I_2}=(x-1)^2=f$ だが、$\mu_{I_2}=x-1\ne f=\mu_{C(f)}$ なので $I_2$ と $C(f)$ は相似でない。thm-companion-similar の 3 を満たさない例である。
2 行目：$f=x^2-2x+1$ なので $c_0=1$、$c_1=-2$ で $C(f)=\begin{pmatrix}0&-1\\1&2\end{pmatrix}$ である。固有値は $1$ だけで、$I_2-C(f)=\begin{pmatrix}1&1\\-1&-1\end{pmatrix}$ の階数は $1$ なので固有空間は 1 次元であり、固有ベクトルからなる基底はない。
3 行目：$x^2+1$ は $\mathbb{R}$ に根をもたないので、$C(x^2+1)$ は $\mathbb{R}$ の上に固有値をもたず、$\mathbb{R}$ 上では対角化できない（ex-companion-small の 1）。$\mathbb{C}$ 上では根 $\pm i$ が相異なるので対角化できる。
4 行目：$C(x^2)=\begin{pmatrix}0&0\\1&0\end{pmatrix}$ で $C(x^2)e_2=0$ なので、$e_2,C(x^2)e_2$ は基底にならない。巡回ベクトルはあるが（$e_1$）、すべてのベクトルがそうではない。