行列のn乗と割り算の余り

$t^n$ を $t^2-3t+2=(t-1)(t-2)$ で割った余りを求める。割る式が 2 次なので、余りは 1 次以下で $r_nt+s_n$ と書け、
$$ t^n=Q(t)(t-1)(t-2)+r_nt+s_n $$
となる（$Q(t)$ は商）。$t=1$ を代入すると $1=r_n+s_n$、$t=2$ を代入すると $2^n=2r_n+s_n$ である。2 式を引いて $r_n=2^n-1$、すると $s_n=1-r_n=2-2^n$ である。たとえば $n=5$ で、$t^5$ を $t^2-3t+2$ で割った余りは $31t-30$ である。

1. $f(t)=t^2+1$、$A=\begin{pmatrix}1&2\\3&4\end{pmatrix}$ とする。$A^2=\begin{pmatrix}1+6&2+8\\3+12&6+16\end{pmatrix}=\begin{pmatrix}7&10\\15&22\end{pmatrix}$ なので、$f(A)=A^2+E=\begin{pmatrix}8&10\\15&23\end{pmatrix}$ である。
2. $g(t)=t^2-3t+2$、$M=\begin{pmatrix}3&-1\\2&0\end{pmatrix}$ とする。$M^2=\begin{pmatrix}9-2&-3+0\\6+0&-2+0\end{pmatrix}=\begin{pmatrix}7&-3\\6&-2\end{pmatrix}$ なので
   $$ g(M)=M^2-3M+2E=\begin{pmatrix}7-9+2&-3+3+0\\6-6+0&-2-0+2\end{pmatrix}=\begin{pmatrix}0&0\\0&0\end{pmatrix} $$
   となる。$g(M)$ がすべての成分 $0$ の行列 $O$ になった。$g(t)$ は $M$ の固有多項式 $t^2-(\operatorname{tr}M)t+\det M=t^2-3t+2$ である。

1. $A=\begin{pmatrix}1&2\\3&4\end{pmatrix}$、$f(t)=t$、$g(t)=t+1$ とする。$fg=t^2+t$ なので、ex-mpr-subst の $A^2$ を使って
   $$ (fg)(A)=A^2+A=\begin{pmatrix}7+1&10+2\\15+3&22+4\end{pmatrix}=\begin{pmatrix}8&12\\18&26\end{pmatrix} $$
   である。一方
   $$ f(A)\,g(A)=A(A+E)=\begin{pmatrix}1&2\\3&4\end{pmatrix}\begin{pmatrix}2&2\\3&5\end{pmatrix}=\begin{pmatrix}2+6&2+10\\6+12&6+20\end{pmatrix}=\begin{pmatrix}8&12\\18&26\end{pmatrix} $$
   で、確かに等しい。
2. ex-mpr-subst の $M=\begin{pmatrix}3&-1\\2&0\end{pmatrix}$ と $g(t)=t^2-3t+2=(t-1)(t-2)$ では、
   $$ (M-E)(M-2E)=\begin{pmatrix}2&-1\\2&-1\end{pmatrix}\begin{pmatrix}1&-1\\2&-2\end{pmatrix}=\begin{pmatrix}2-2&-2+2\\2-2&-2+2\end{pmatrix}=O $$
   となり、ex-mpr-subst で直接計算した $g(M)=O$ と一致する。因数分解した形に代入してもよいのである。

$A=\begin{pmatrix}1&2\\3&4\end{pmatrix}$ では $\operatorname{tr}A=5$、$\det A=4-6=-2$ で、ex-mpr-subst の $A^2=\begin{pmatrix}7&10\\15&22\end{pmatrix}$ を使うと
$$ A^2-5A-2E=\begin{pmatrix}7-5-2&10-10-0\\15-15-0&22-20-2\end{pmatrix}=\begin{pmatrix}0&0\\0&0\end{pmatrix} $$
である。ex-mpr-subst の 2 の $M$ も、$g(M)=\chi_M(M)=O$ であった。

$M=\begin{pmatrix}3&-1\\2&0\end{pmatrix}$ の固有多項式は $\chi_M(t)=t^2-3t+2$ である。ex-mpr-remainder-hs により $t^n$ をこれで割った余りは $(2^n-1)t+(2-2^n)$ なので、thm-mpr-cayley-hamilton により
$$ M^n=(2^n-1)M+(2-2^n)E $$
である。$n=5$ では $M^5=31M-30E=\begin{pmatrix}93-30&-31\\62&-30\end{pmatrix}=\begin{pmatrix}63&-31\\62&-30\end{pmatrix}$ で、$M$ を 5 回掛けた結果と一致する。

$a_{n+2}=2a_{n+1}+3a_n$、$a_0=0$、$a_1=4$ のコンパニオン行列は $C=\begin{pmatrix}2&3\\1&0\end{pmatrix}$、$\chi_C(t)=t^2-2t-3=(t-3)(t+1)$ である。$t^5=Q(t)(t-3)(t+1)+r_5t+s_5$ に $t=3$、$t=-1$ を代入すると $243=3r_5+s_5$、$-1=-r_5+s_5$ で、引き算して $4r_5=244$、$r_5=61$、$s_5=60$ である。よって cor-mpr-recurrence により
$$ C^5=61C+60E=\begin{pmatrix}122+60&183\\61&60\end{pmatrix}=\begin{pmatrix}182&183\\61&60\end{pmatrix} $$
であり、$a_5=r_5a_1+s_5a_0=61\cdot4+0=244=3^5-(-1)^5$ である。

$t^n$ を $(t-2)^2=t^2-4t+4$ で割った余りは、prop-mpr-remainder の 2 により $n2^{n-1}t+(1-n)2^n$ である。$n=3$ では $12t-16$ で、実際 $t^3=(t+4)(t^2-4t+4)+12t-16$（右辺を展開すると $t^3-4t^2+4t+4t^2-16t+16+12t-16=t^3$）である。$C=\begin{pmatrix}4&-4\\1&0\end{pmatrix}$（漸化式 $a_{n+2}=4a_{n+1}-4a_n$）では、$n=5$ の余り $80t-128$ から
$$ C^5=80C-128E=\begin{pmatrix}320-128&-320\\80&-128\end{pmatrix}=\begin{pmatrix}192&-320\\80&-128\end{pmatrix} $$
である。

Fibonacci数 の漸化式 $F_{n+2}=F_{n+1}+F_n$ では $p=q=1$ で、$F_0=0$、$F_1=1$ なので、cor-mpr-single の $r_n$ は $F_n$ である。よって $t^n$ の $t^2-t-1$ による余りは $F_nt+F_{n-1}$（$n\ge1$）で、実際 $t^2,t^3,t^4,t^5$ の余りは $t+1$、$2t+1$、$3t+2$、$5t+3$ である。cor-mpr-single により、$C=\begin{pmatrix}1&1\\1&0\end{pmatrix}$ について、$n\ge1$ で
$$ C^n=F_nC+F_{n-1}E=\begin{pmatrix}F_n+F_{n-1}&F_n\\F_n&F_{n-1}\end{pmatrix}=\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix} $$
である。$n=10$ では $t^{10}$ の余り $55t+34$ から $C^{10}=\begin{pmatrix}89&55\\55&34\end{pmatrix}$ である。行列式は積を保つ（$\det(XY)=\det X\det Y$。2 次なら成分の計算で確かめられるが、本記事では計算を省く）ので、$\det C^n=(\det C)^n=(-1)^n$ から
$$ F_{n+1}F_{n-1}-F_n^2=(-1)^n $$
を得る（Cassini の恒等式）。$n=10$ で $89\cdot34-55^2=3026-3025=1$ である。

$a_{n+2}=a_{n+1}-a_n$ のコンパニオン行列 $C=\begin{pmatrix}1&-1\\1&0\end{pmatrix}$ の固有多項式は $t^2-t+1$ である。$t^3+1=(t+1)(t^2-t+1)$ なので $t^3=(t+1)(t^2-t+1)-1$ であり、$t^3$ の余りは $-1$ である。thm-mpr-cayley-hamilton により $C^3=-E$、したがって $C^6=(C^3)^2=E$ である。すると $v_{n+6}=C^6v_n=v_n$ となり、どの解も 6 項ごとに同じ値をくり返す。たとえば $100=6\cdot16+4$ なので $C^{100}=(C^6)^{16}C^4=C^4=C^3C=-C$ である。

$C=\begin{pmatrix}2&1\\1&0\end{pmatrix}$（漸化式 $a_{n+2}=2a_{n+1}+a_n$）の固有多項式 $t^2-2t-1$ の解は $\alpha=1+\sqrt2$、$\beta=1-\sqrt2$ である。$T_n:=\operatorname{tr}(C^n)$ とおく。cor-mpr-recurrence の $C^n=r_nC+s_nE$ の跡をとると $T_n=r_n\operatorname{tr}C+2s_n=2r_n+2s_n$ である。一方、prop-mpr-remainder の証明の段 1 の 2 式 $\alpha^n=r_n\alpha+s_n$、$\beta^n=r_n\beta+s_n$ を足すと $\alpha^n+\beta^n=r_n(\alpha+\beta)+2s_n=2r_n+2s_n$ なので、
$$ T_n=(1+\sqrt2)^n+(1-\sqrt2)^n $$
である。$r_n,s_n$ は $0,1,2,5,12,29,\dots$ と $1,0,1,2,5,12,\dots$ で整数なので、$T_n=2,2,6,14,34,82,\dots$ も整数である。$|1-\sqrt2|=\sqrt2-1<1$ なので、$(1+\sqrt2)^n=T_n-(1-\sqrt2)^n$ と整数 $T_n$ の差 $(\sqrt2-1)^n$ は、$n$ が大きくなると急速に小さくなる。$(1-\sqrt2)^n$ の符号が交互に変わるので、$(1+\sqrt2)^n$ は $n$ が偶数なら $T_n$ より小さく、奇数なら大きい。たとえば $(1+\sqrt2)^5=82.0121\ldots$、$(1+\sqrt2)^{10}=6725.99985\ldots$（$T_{10}=6726$）、$(1+\sqrt2)^{20}=45239073.99999997\ldots$ である。

$C=\begin{pmatrix}2&3\\1&0\end{pmatrix}$（固有多項式 $t^2-2t-3$）について、$t^2$ を別の 2 次式 $t^2-t$ で割ると、$t^2=1\cdot(t^2-t)+t$ で余りは $t$ である。もし「余りを代入すればよい」が成り立つなら $C^2=C$ となるはずだが、$C^2=\begin{pmatrix}4+3&6\\2&3\end{pmatrix}=\begin{pmatrix}7&6\\2&3\end{pmatrix}\ne C$ である。$C$ を代入して $O$ になるのは固有多項式 $t^2-2t-3$ であって、$t^2-t$ ではない（$C^2-C=\begin{pmatrix}5&3\\1&3\end{pmatrix}\ne O$）。仮定「割る式を $A$ に代入すると $O$」が崩れると、結論も崩れる。

$A=\begin{pmatrix}1&2\\3&4\end{pmatrix}$、$B=\begin{pmatrix}0&1\\1&1\end{pmatrix}$ とする。数なら $(x+y)^2=x^2+2xy+y^2$ だが、行列では
$$ (A+B)^2=\begin{pmatrix}13&18\\24&37\end{pmatrix},\qquad A^2+2AB+B^2=\begin{pmatrix}12&17\\24&38\end{pmatrix} $$
で等しくない。$(A+B)^2=A^2+AB+BA+B^2$ であり、$AB=\begin{pmatrix}2&3\\4&7\end{pmatrix}$ と $BA=\begin{pmatrix}3&4\\4&6\end{pmatrix}$ が等しくないため、差 $BA-AB=\begin{pmatrix}1&1\\0&-1\end{pmatrix}$ が残る。prop-mpr-subst-hom は、1 つの行列 $A$ の冪どうしが交換する（$A^iA^j=A^jA^i=A^{i+j}$）から成り立つのである。