同伴行列どうはんぎょうれつcompanion matrixの基本きほん

Basics of the companion matrix同伴行列どうはんぎょうれつ

1導入どうにゅう

この講義こうぎで重要じゅうようなのは、同伴行列どうはんぎょうれつcompanion matrixは、与あたえられたモニック多項式たこうしきpolynomialを特性多項式とくせいたこうしきcharacteristic polynomialにもつように作つくられた行列ぎょうれつmatrixであるということである。

同伴行列どうはんぎょうれつcompanion matrixを使つかうと、多項式たこうしきの根こんを行列ぎょうれつmatrixの固有値こゆうちeigenvalueとして読よめる。これは、固有値問題こゆうちもんだいeigenvalue problemと多項式たこうしきpolynomialの根こんの問題もんだいを接続せつぞくする標準的ひょうじゅんてきな構成こうせいである。

名称めいしょうに注意ちゅういする。同伴行列どうはんぎょうれつcompanion matrixは、余因子よいんしcofactorから作つくる随伴行列ずいはんぎょうれつadjugate matrixとは別べつの概念がいねんである。

1Introduction

The companion matrix同伴行列どうはんぎょうれつ of a monic polynomial is a matrix built so that the polynomial becomes its characteristic polynomial. It turns a polynomial root problem into an eigenvalue problem.

Do not confuse the companion matrix with the adjugate matrix随伴行列ずいはんぎょうれつ from cofactors; they are different concepts.

2用語ようごと定義ていぎ

モニック多項式たこうしきmonic polynomial

を考かんがえる。この講義こうぎでは、$p\left(t\right)$p(t) の同伴行列どうはんぎょうれつcompanion matrixを

で定義ていぎする。

教科書きょうかしょによっては、この転置てんちtransposeを同伴行列どうはんぎょうれつcompanion matrixと呼よぶ流儀りゅうぎもある。転置てんちtransposeしても特性多項式とくせいたこうしきcharacteristic polynomialは変かわらないため、本質ほんしつは同おなじである。この講義こうぎでは、固有こゆうベクトルeigenvectorの形かたちが読よみやすい上うえの流儀りゅうぎを採用さいようする。

2Terms and definitions

For a monic polynomial

define its companion matrix同伴行列どうはんぎょうれつ by

Some books use the transpose convention. The characteristic polynomial is unchanged by transpose, so the essential construction is the same.

3方針ほうしん

証明しょうめいしたいことは次つぎの 3 点てんである。

1. $p\left(\lambda \right)=0$p(\lambda)=0 なら、$\lambda$\lambda は $C_p$C_p の固有値こゆうちeigenvalueである。
2. 逆ぎゃくに、$\lambda$\lambda が $C_p$C_p の固有値こゆうちeigenvalueなら、$p\left(\lambda \right)=0$p(\lambda)=0 である。
3. $C_p$C_p の特性多項式とくせいたこうしきcharacteristic polynomialは $p\left(t\right)$p(t) である。

核心かくしんは、同伴行列どうはんぎょうれつcompanion matrixの最後さいごの行ぎょうに、関係式かんけいしき

が埋うめ込こまれていることである。

3Plan

We prove three facts: roots of $p$p are eigenvalues of $C_p$C_p, eigenvalues of $C_p$C_p are roots of $p$p, and the characteristic polynomial of $C_p$C_p is $p\left(t\right)$p(t). The last row encodes the relation

4直感的ちょっかんてきな説明せつめい

同伴行列どうはんぎょうれつcompanion matrixは、「$t$t を掛かける操作そうさ」を、$1,t,t^2,\dots ,t^{n-1}$1,t,t^2,\ldots,t^{n-1} の範囲はんいに閉とじ込こめるための行列ぎょうれつmatrixである。$t^{n-1}$t^{n-1} にさらに $t$t を掛かけると $t^n$t^n になるが、$p\left(t\right)=0$p(t)=0 と見みれば

と低次ていじの冪べきpowerへ戻もどせる。同伴行列どうはんぎょうれつcompanion matrixの最後さいごの行ぎょうは、この戻もどし方かたを記録きろくしている。

そのため、$p\left(\lambda \right)=0$p(\lambda)=0 となる数かず $\lambda$\lambda では、列れつベクトル

が固有こゆうベクトルeigenvectorになる。これは、多項式たこうしきpolynomialの根こんが行列ぎょうれつmatrixの固有値こゆうちeigenvalueとして現あらわれることを直接ちょくせつ示しめしている。

4Intuitive explanation

The companion matrix records multiplication by $t$t while using the relation $p\left(t\right)=0$p(t)=0 to rewrite $t^n$t^n in terms of lower powers. If $p\left(\lambda \right)=0$p(\lambda)=0, then

becomes an eigenvector of $C_p$C_p with eigenvalue $\lambda$\lambda.

5厳密げんみつな説明せつめい

5.11. 根こんから固有こゆうベクトルeigenvectorを作つくる

$p\left(\lambda \right)=0$p(\lambda)=0 とする。

と置おく。$C_{p}v\left(\lambda \right)$C_pv(\lambda) の第だい 1 成分せいぶんから第だい $n-1$n-1 成分せいぶんまでは、それぞれ

である。これは $\lambda v\left(\lambda \right)$\lambda v(\lambda) の第だい 1 成分せいぶんから第だい $n-1$n-1 成分せいぶんに一致いっちする。

最後さいごの成分せいぶんは

である。$p\left(\lambda \right)=0$p(\lambda)=0 より

なので、

である。これは $\lambda v\left(\lambda \right)$\lambda v(\lambda) の最後さいごの成分せいぶんである。よって

であり、$\lambda$\lambda は $C_p$C_p の固有値こゆうちeigenvalueである。

5.22. 固有値こゆうちeigenvalueから根こんを得える

$C_{p}x=\lambda x$C_px=\lambda x とし、$x=(x_1,\dots ,x_n{)}^T\ne 0$x=(x_1,\ldots,x_n)^T\ne0 とする。最初さいしょの $n-1$n-1 行ぎょうから

である。もし $x_1=0$x_1=0 なら、順じゅんに $x_2=\cdots =x_n=0$x_2=\cdots=x_n=0 となり、$x\ne 0$x\ne0 に反はんする。したがって $x_1\ne 0$x_1\ne0 であり、

である。最後さいごの行ぎょうを使つかうと

である。$x_k=x_1{\lambda }^{k-1}$x_k=x_1\lambda^{k-1} を代入だいにゅうし、$x_1\ne 0$x_1\ne0 で割わると

となる。したがって

である。

5.33. 特性多項式とくせいたこうしきcharacteristic polynomialが $p\left(t\right)$p(t) になる理由りゆう

上うえの 2 つの証明しょうめいにより、$C_p$C_p の固有値こゆうちeigenvalueは $p\left(t\right)$p(t) の根こんと一致いっちする。しかし重複度ちょうふくどまで含ふくめて特性多項式とくせいたこうしきcharacteristic polynomialが $p\left(t\right)$p(t) に等ひとしいことも確認かくにんする。

$M=C_{p^T}$M=C_p^T とする。転置てんちtransposeで特性多項式とくせいたこうしきcharacteristic polynomialは変かわらないので、${\chi }_{C_p}\left(t\right)={\chi }_M\left(t\right)$\chi_{C_p}(t)=\chi_M(t) である。

$M$M は標準基底ひょうじゅんきてい $e_1,\dots ,e_n$e_1,\ldots,e_n に対たいして

かつ

を満みたす。したがって

である。さらに $e_1,M{e}_1,\dots ,M^{n-1}{e}_1$e_1,Me_1,\ldots,M^{n-1}e_1 は $e_1,\dots ,e_n$e_1,\ldots,e_n そのものなので、基底きていである。$p\left(M\right)$p(M) は $M$M と可換かかんであるため、$p\left(M\right)$p(M) はこの基底きていの各かくベクトルを 0 へ送おくる。よって

である。

一方いっぽう、次数じすうが $n$n 未満みまんの非零多項式ひぜろたこうしき $q$q について、$q\left(M\right)e_1$q(M)e_1 は $e_1,\dots ,e_n$e_1,\ldots,e_n の非自明ひじめいな線型結合せんけいけつごうlinear combinationになるため 0 ではない。したがって $M$M の最小多項式さいしょうたこうしきminimal polynomialは $p\left(t\right)$p(t) である。

最小多項式さいしょうたこうしきminimal polynomialは特性多項式とくせいたこうしきcharacteristic polynomialを割わり、どちらもモニックな $n$n 次じ多項式たこうしきpolynomialである。よって

である。したがって

である。

5Precise explanation

5.11. Roots give eigenvectors

If $p\left(\lambda \right)=0$p(\lambda)=0, set

The first $n-1$n-1 components of $C_{p}v\left(\lambda \right)$C_pv(\lambda) are $\lambda ,{\lambda }^2,\dots ,{\lambda }^{n-1}$\lambda,\lambda^2,\ldots,\lambda^{n-1}. The last component is

because $p\left(\lambda \right)=0$p(\lambda)=0. Hence $C_{p}v\left(\lambda \right)=\lambda v\left(\lambda \right)$C_pv(\lambda)=\lambda v(\lambda).

5.22. Eigenvalues give roots

Conversely, if $C_{p}x=\lambda x$C_px=\lambda x with $x\ne 0$x\ne0, the first $n-1$n-1 rows force

The vector would be zero if $x_1=0$x_1=0, so $x_1\ne 0$x_1\ne0. The last row then gives $p\left(\lambda \right)=0$p(\lambda)=0.

5.33. Why the characteristic polynomial is $p\left(t\right)$p(t)

Let $M=C_{p^T}$M=C_p^T. Transpose preserves the characteristic polynomial. The matrix $M$M satisfies

and

Thus $p\left(M\right)=0$p(M)=0. Since $e_1,M{e}_1,\dots ,M^{n-1}{e}_1$e_1,Me_1,\ldots,M^{n-1}e_1 is a basis, no nonzero polynomial of degree less than $n$n can annihilate $M$M. Hence the minimal polynomial of $M$M is $p\left(t\right)$p(t). The minimal polynomial divides the characteristic polynomial, and both are monic of degree $n$n, so the characteristic polynomial is $p\left(t\right)$p(t). Therefore ${\chi }_{C_p}\left(t\right)=p\left(t\right)$\chi_{C_p}(t)=p(t).

6具体例ぐたいれい

とする。これは

で $c_2=-6,c_1=11,c_0=-6$c_2=-6,\ c_1=11,\ c_0=-6 である。したがって同伴行列どうはんぎょうれつcompanion matrixは

である。$p\left(t\right)=(t-1)(t-2)(t-3)$p(t)=(t-1)(t-2)(t-3) なので、$C_p$C_p の固有値こゆうちeigenvalueは $1,2,3$1,2,3 である。

たとえば $\lambda =2$\lambda=2 について

とすると、

である。

6Worked example

For

the companion matrix is

Since $p\left(t\right)=(t-1)(t-2)(t-3)$p(t)=(t-1)(t-2)(t-3), the eigenvalues are $1,2,3$1,2,3. For $\lambda =2$\lambda=2,

7別べつの見方みかた：巡回基底じゅんかいきていcyclic basis

同伴行列どうはんぎょうれつcompanion matrixは、巡回基底じゅんかいきていcyclic basisの行列表示ぎょうれつひょうじとしても理解りかいできる。あるベクトルvector $v$v から

が基底きていbasisになるとき、$v$v を巡回じゅんかいベクトルcyclic vectorという。この基底きていでは、$T$T は前まえの基底きていベクトルを次つぎへ送おくり、最後さいごだけを低次ていじの線型結合せんけいけつごうへ戻もどす。その表示ひょうじが同伴行列どうはんぎょうれつcompanion matrixである。

この見方みかたは、最小多項式さいしょうたこうしきminimal polynomialやジョルダン標準形ひょうじゅんけいJordan normal formの先さきにある標準形ひょうじゅんけいの理解りかいへ接続せつぞくする。

7Another viewpoint: cyclic bases

A companion matrix is also the matrix representation in a cyclic basis巡回基底じゅんかいきてい. If

is a basis, then $T$T shifts each basis vector to the next one, and the last vector is rewritten using the polynomial relation. This viewpoint connects companion matrices to minimal polynomials and later canonical forms.

8見分みわけ方かた

• 多項式たこうしき $p\left(t\right)$p(t) の根こんを固有値問題こゆうちもんだいeigenvalue problemとして扱あつかいたいとき、同伴行列どうはんぎょうれつcompanion matrixを作つくる。
• 特性多項式特性多項式とくせいたこうしきだけを指定していして行列ぎょうれつmatrixの例れいを作つくりたいときにも、同伴行列どうはんぎょうれつcompanion matrixが使つかえる。
• 随伴行列随伴行列ずいはんぎょうれつという語ごが出でたら、余因子よいんしcofactorから作つくる逆行列ぎゃくぎょうれつinverse matrixの公式こうしきの道具どうぐであり、同伴行列どうはんぎょうれつcompanion matrixとは別べつである。

8How to recognize when to use this

Use a companion matrix when turning a polynomial root problem into an eigenvalue problem, or when constructing a matrix with a prescribed characteristic polynomial. The adjugate matrix from cofactors is a different object.

9どこまで成立せいりつするか

この講義こうぎでは、最高次係数さいこうじけいすうが 1 のモニック多項式たこうしきmonic polynomialを扱あつかった。最高次係数さいこうじけいすうが 0 でない多項式たこうしきなら、全体ぜんたいをその係数けいすうで割わってモニックに直なおしてから同伴行列どうはんぎょうれつcompanion matrixを作つくる。

根こんが考察こうさつしている体たいの中なかに存在そんざいしない場合ばあいでも、同伴行列どうはんぎょうれつcompanion matrixは定義ていぎできる。その場合ばあい、固有値こゆうちeigenvalueをすべて確認かくにんするには、体たいを拡大かくだいして根こんが存在そんざいする場所ばしょで考察こうさつする。

9Scope

This lecture treats monic polynomials. A polynomial with nonzero leading coefficient can first be divided by that coefficient. The companion matrix can be defined even when the roots are not in the base field; to see all eigenvalues, one may extend the field.

10最終形さいしゅうけい

10Final forms

11一言ひとことでいうと

• 同伴行列どうはんぎょうれつcompanion matrixは、多項式たこうしきpolynomialを特性多項式とくせいたこうしきcharacteristic polynomialとして同伴どうはんする行列ぎょうれつmatrixである。
• 多項式たこうしきの根こんは、その同伴行列どうはんぎょうれつcompanion matrixの固有値こゆうちeigenvalueである。

12演習えんしゅうリンク

11In one sentence

• A companion matrix accompanies a polynomial by making it the characteristic polynomial.
• The roots of the polynomial are the eigenvalues of the companion matrix.

12Exercise links

13関連かんれんリンク

13Related links