ペケとジマの線形代数+ #6 漸化式や帰納法の使い方

コジ

2024年12月9日 21:51

登場人物

ペケ(聞き手)
理系，学部3年．
工学系の院試を控えている．

ジマ(話し手)
文系，ペケの先輩．
口が悪い．

ジマ：今回も問題演習すっかナァーー．
5分程度で終わるよ．

ペケ：随分と難易度下げましたね．

ジマ：だって必死こいて記事あたり平均5000字書いても誰も見ねーんだもん．読んだらいいねくらい付けてくれよなァー．

ペケ：まぁ，線形代数勉強中の人は検索上位のサイト見てるだろうし．

ジマ：それはそう．だからこのシリーズでは，他サイトにはない問題演習でオリジナリティーを出していくよ．では早速，

$$
\begin{aligned}
A_n=
\begin{pmatrix}
p+q & p & \cdots & 0\\
q & p+q & \ddots & \vdots \\
\vdots & \ddots & \ddots & p\\
0 & \cdots & q & p+q
\end{pmatrix}
\end{aligned}
$$

のとき，$${|A_n|}$$を計算してくれ．院試や定期試験でよく出るやつだねェ～～．

ペケ：1行目で余因子展開すると，

$$
\begin{aligned}
&|A_n|\\
&=(p+q)|A_{n-1}|-p
\begin{vmatrix}
q & p& \cdots & 0\\
0 & p+q & \ddots & \vdots \\
\vdots & \ddots & \ddots & p\\
0 & \cdots & q & p+q
\end{vmatrix}\\
&=(p+q)|A_{n-1}|-pq
\begin{vmatrix}
p+q & p & \cdots & 0\\
q & p+q & \ddots & \vdots \\
\vdots & \ddots & \ddots & p\\
0 & \cdots & q & p+q
\end{vmatrix}\\
&=(p+q)|A_{n-1}|-pq|A_{n-2}|
\end{aligned}
$$

あ，コレ高校の時にやった隣接三項間漸化式じゃないですか！
てことは，$${|A_1|=p+q,|A_2|=p^2+pq+q^2}$$より，

$$
\begin{aligned}
&|A_{n+1}|-q|A_{n}|\\
&=p(|A_{n+1}|-q|A_{n}|)\\
& \ \ \vdots\\
&=p^{n-1}(|A_{2}|-q|A_{1}|)\\
&=p^{n+1}\\
\end{aligned}
$$

$$
\begin{aligned}
&|A_{n+1}|-p|A_{n}|\\
&=q(|A_{n+1}|-p|A_{n}|)\\
& \ \ \vdots\\
&=q^{n-1}(|A_{2}|-p|A_{1}|)\\
&=q^{n+1}\\
\end{aligned}
$$

$$
\begin{aligned}
\therefore
&|A_{n+1}|-q|A_{n}|=p^{n+1},|A_{n+1}|-p|A_{n}|=q^{n+1}
\end{aligned}
$$

となるから，これらを辺々引いて$${(p-q)}$$で割ると，

$$
\begin{aligned}
\therefore|A_{n}|=\frac{p^{n+1}-q^{n+1}}{p-q}
\end{aligned}
$$

となるんすね．

ジマ：合ってるよォーー．今回のように，線形代数では，計算ムズくても漸化式や帰納法でなんとかできる問題が意外とあるよォー．Soーー．

ペケ：なるほどねー．

ジマ：では最後に次を示してくれ．

$$
\begin{aligned}
A_n\in M_n(\{-1,1\})\implies 2^{n-1}\mid |A_n|
\end{aligned}
$$

$${a\mid b}$$は，$${a}$$は$${b}$$を割り切るという意味だ．

ペケ：$${M_n(\cdot)}$$ってなんですか？

ジマ：$${M_n(K)}$$は成分に$${K}$$の元(高校数学の言葉で言うと，$${K}$$の要素)をもつ$${n}$$次正方行列全体の集合だね．

ペケ：てことは，行列$${A_n\big(\in M_n(\{-1,1\})\big)}$$っていうのは，すべての成分が$${-1}$$か$${1}$$の$${n}$$次正方行列なんですね．

ジマ：さっきからそう言ってるだろボケナス！！

ペケ：読者に向けて言ってるんだよなぁ．$${n=2}$$のとき，

$$
\begin{aligned}
|A_2|
&=
\begin{vmatrix}
\pm1&\pm1\\
\pm1&\pm1\\
\end{vmatrix} \ (複合任意)\\
&=(\pm1)(\pm1)-(\pm1)(\pm1) \ (複合任意)\\
&=(\pm1)+(\pm1) \ (複合任意)\\
&=-2,0,2
\end{aligned}
$$

確かに$${2}$$で割り切れますね．

ジマ：(複合任意)，(複合任意)うるせぇ！！

ペケ：すみませんでした．$${n=3}$$は，

$$
\begin{aligned}
|A_3|
&=
\begin{vmatrix}
\pm1&\pm1&\pm1\\
\pm1&\pm1&\pm1\\
\pm1&\pm1&\pm1\\
\end{vmatrix} \ (複合任意)\\
&=(\pm1)+(\pm1)+(\pm1)+(\pm1)+(\pm1)+(\pm1)\\
&=0,\pm2,\pm4,\pm6???
\end{aligned}
$$

…あれ，分かんなくなっちゃった．

ジマ：ほーら間違えた．無理に計算しようとせず素直に帰納法使えよなァー．

ペケ：なるほどねー．$${n=1}$$は$${A_1=\pm1}$$で$${1}$$で割り切れてokだから，$${n=k}$$のときを仮定して，$${|A_{k+1}|}$$の1列目で余因子展開すると，

$$
\begin{aligned}
&|A_{k+1}|\\
&=a_{11}|\mathcal A_1|+a_{21}|\mathcal A_2|+\cdots +a_{(k+1)1}|\mathcal A_{k+1}|\\
&=(\pm1)|\mathcal A_1|+(\pm1)|\mathcal A_2|+\cdots +(\pm1)|\mathcal A_{k+1}|
\end{aligned}
$$

で，$${\mathcal A_i \in M_k(\{-1,1\})}$$だから，仮定より…
・・・これじゃ$${2^{k-1}\mid |A_{k+1}|}$$しか示せないや．

ジマ：n～～．方向性は良いんだけどSa～～～～．行列式の列をほかの列に加えても値変わんないっていう性質あったじゃん？

ペケ：なるほど，$${|A_{k+1}|}$$の1列目に2列目を加えると，1列目の成分が$${-2}$$か$${0}$$か$${2}$$になるから，そうしてから1列目で余因子展開すると，

$$
\begin{aligned}
&|A_{k+1}|\\
&=(a_{11}+a_{12})|\mathcal A_1|+\cdots +(a_{(k+1)1}+a_{(k+1)2})|\mathcal A_{k+1}|\\
&=(0,\pm2)|\mathcal A_1|+\cdots +(0,\pm2)|\mathcal A_{k+1}|
\end{aligned}
$$

で，$${\mathcal A_i \in M_k(\{-1,1\})}$$だから，仮定より，$${2^{k}\mid (-2|\mathcal A_i|),2^{k}\mid 0,2^{k}\mid (2|\mathcal A_i|)}$$となるから，$${2^{k}\mid |A_{k+1}|}$$となり，数学的帰納法により正しいってことなんすね．