京都大学 1996年度 前期日程 第2次学力試験文系数学 第3問

$A$ を $2$ 次正方行列とし，$$A=\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)$$とおく。$a,b,c,d$ は0以上の整数である。

まず$$A^2=\left(\begin{array}{cc}{a}^2+bc& b(a+d)\\ c(a+d)& d^2+bc\end{array}\right)$$であるから，$A^3=A$ の各成分を比較すると $a^3+2abc+bcd=a$ $b(a^2+ad+bc+d^2-1)=0$ $c(a^2+ad+bc+d^2-1)=0$ $abc+2bcd+d^3=d$ である。

第1式の左辺は非負整数の和であるから，特に $a^3\leqq a$ である。よって $$a=0\text{または}a=1$$ である。同様に第4式から $$d=0\text{または}d=1$$ である。

まず $bc>0$ の場合を考える。このとき $b,c$ は正の整数である。第2式または第3式より $a^2+ad+bc+d^2=1$ である。ここで $bc\geqq 1$ であり，他の項はすべて0以上だから $bc=1,a=d=0$ でなければならない。したがって $b=c=1$ であり$$A=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$$を得る。

次に $bc=0$ の場合を考える。 $b=c=0$ なら，$A$ は対角行列であり，すでに $a,d\in \{0,1\}$ と分かっている。よって$$A=\left(\begin{array}{cc}a& 0\\ 0& d\end{array}\right)(a,d=0,1)$$である。 $b>0$，$c=0$ の場合は，第2式から $a^2+ad+d^2=1$ である。$a,d$ は0または1なので，これは $(a,d)=(1,0),(0,1)$ に限られる。したがって$$A=\left(\begin{array}{cc}1& b\\ 0& 0\end{array}\right)\text{または}A=\left(\begin{array}{cc}0& b\\ 0& 1\end{array}\right)(b=1,2,3,\dots )$$である。

同様に $b=0$，$c>0$ の場合は$$A=\left(\begin{array}{cc}1& 0\\ c& 0\end{array}\right)\text{または}A=\left(\begin{array}{cc}0& 0\\ c& 1\end{array}\right)(c=1,2,3,\dots )$$である。

以上をまとめると，求める行列は$$\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$$および$$\left(\begin{array}{cc}a& 0\\ 0& d\end{array}\right)(a,d=0,1),$$さらに$$\left(\begin{array}{cc}1& b\\ 0& 0\end{array}\right),\left(\begin{array}{cc}0& b\\ 0& 1\end{array}\right),\left(\begin{array}{cc}1& 0\\ c& 0\end{array}\right),\left(\begin{array}{cc}0& 0\\ c& 1\end{array}\right)(b,c=1,2,3,\dots )$$である。逆に，これらの行列は直接計算によりいずれも $A^3=A$ を満たす。

行列の各成分を有向グラフの「重み」とみなし、
$A^3$ の対角成分が長さ3の道の重みの和になることを利用する。
非負性のため各項を個別に抑えられ、対角成分は0か1に限られる。
その後は $bc>0$、片方だけ正、両方0の3場合に分ける。

$$A=\left(\begin{array}{cc}a& b\\ c& d\end{array}\right),a,b,c,d\in {\mathbb{Z}}_{\geqq 0}$$とする。$A^3=A$ の対角成分は$$a^3+2abc+bcd=a,abc+2bcd+d^3=d\mathrm{.}$$左辺の各項は非負なので $a^3\leqq a$，$d^3\leqq d$ であり、$$a,d\in \{0,1\}\mathrm{.}$$非対角成分は$$b\{a^2+ad+bc+d^2-1\}=0,$$$$c\{a^2+ad+bc+d^2-1\}=0.$$$bc>0$ なら中括弧は0である。すべて非負整数であるから$$bc=1,a=d=0,$$したがって $b=c=1$ で$$A=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)\mathrm{.}$$$b=c=0$ なら$$A=\left(\begin{array}{cc}a& 0\\ 0& d\end{array}\right),a,d\in \{0,1\}\mathrm{.}$$$b>0,c=0$ なら$$a^2+ad+d^2=1.$$$a,d\in \{0,1\}$ より $(a,d)=(1,0),(0,1)$ であり、$$A=\left(\begin{array}{cc}1& b\\ 0& 0\end{array}\right)\text{または}A=\left(\begin{array}{cc}0& b\\ 0& 1\end{array}\right)(b\in {\mathbb{Z}}_{>0})\mathrm{.}$$同様に $b=0,c>0$ なら$$A=\left(\begin{array}{cc}1& 0\\ c& 0\end{array}\right)\text{または}A=\left(\begin{array}{cc}0& 0\\ c& 1\end{array}\right)(c\in {\mathbb{Z}}_{>0})\mathrm{.}$$以上の行列は直接3乗すればすべて条件を満たす。