0474-1992 东大工 数学 WEB

线性代数 矩阵方程 排列矩阵 组合数学

$X$ は $4$ 次正方行列で、その各成分は $0$ または $1$ である。また、$E$ はすべての成分が $1$ である $4$ 次正方行列である。ここで、次の方程式を考える。

$$X^2=E$$
この方程式の解の一つが
$$X_0=\left(\begin{array}{cccc}1& 1& 0& 0\\ 0& 0& 1& 1\\ 1& 1& 0& 0\\ 0& 0& 1& 1\end{array}\right)$$
であることを利用して、他の解をできるだけ多く求めよ。なお、$X_0$ と求めた解が解のすべてであることを示す必要はない。

---

解答：
方程式 $X^2=E$ の両辺に右から $E$ を掛けると、$X^{2}E=E^2=4E$ である。また $X^3=X(X^2)=XE$ であり、$X^3=(X^2)X=EX$ となるため、$XE=EX$ が成り立つ。
$XE=EX$ より、$X$ の各行の成分の和はすべて等しく、各列の成分の和もすべて等しい。成分は $0,1$ のみであるため、各行の和を $r$、各列の和を $c$ とおき、$X^2=E$ の全成分の総和を計算すると、

$$\sum _{i=1}^4\sum _{j=1}^4(X^2{)}_{ij}=\sum _{k=1}^4{c}_k{r}_k=4rc=16$$
すなわち $rc=4$ を得る。$r=4,c=1$ のとき $X=E$ となるが $E^2\ne E$ のため不適である。したがって $r=2,c=2$ となる。
これより、$X$ の各行・各列には $1$ がちょうど $2$ つ含まれる。さらに $X^2=E$ であることは、任意の行ベクトルと列ベクトルの内積が常に $1$ であることを意味する。

任意の $4$ 次置換行列 $P$ について $PE{P}^{-1}=E$ が成り立つ。したがって、$X$ が解ならば、

$$(PX{P}^{-1}{)}^2=P{X}^2{P}^{-1}=PE{P}^{-1}=E$$
となり、$PX{P}^{-1}$ も解である。また、$(X^T{)}^2=(X^2{)}^T=E^T=E$ より $X^T$ も解である。
与えられた解 $X_0$ は、行のインデックスの分割 $\{\{1,3\},\{2,4\}\}$ と、列のインデックスの分割 $\{\{1,2\},\{3,4\}\}$ に基づいて $1$ が配置されている。集合 $\{1,2,3,4\}$ を2要素ずつの2つの部分集合に分割する方法は、以下の3通りである。
$$P_1=\{\{1,2\},\{3,4\}\}$$
$$P_2=\{\{1,3\},\{2,4\}\}$$
$$P_3=\{\{1,4\},\{2,3\}\}$$
行の分割 $A$ と列の分割 $B$ （ただし $A\ne B$）を選び、要素の対応を入れ替えることで、$X_0$ 以外の解を網羅的に構成できる。すべての組み合わせにより、$X_0$ を除く11個の他の解が得られる。

X_1 &= \begin{pmatrix} 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \end{pmatrix}, & X_2 &= \begin{pmatrix} 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 \end{pmatrix}, & X_3 &= \begin{pmatrix} 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 \end{pmatrix} \\ X_4 &= \begin{pmatrix} 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 \end{pmatrix}, & X_5 &= \begin{pmatrix} 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \end{pmatrix}, & X_6 &= \begin{pmatrix} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \end{pmatrix} \\ X_7 &= \begin{pmatrix} 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \end{pmatrix}, & X_8 &= \begin{pmatrix} 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix}, & X_9 &= \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \end{pmatrix} \\ X_{10} &= \begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix}, & X_{11} &= \begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{pmatrix} \end{aligned} } $$ --- 本题考查的是矩阵方程的求解以及排列组合在矩阵结构中的应用。 已知矩阵的所有元素都是0或1，且平方后为全1矩阵。根据矩阵乘法的定义，这意味着原矩阵的任意一行和任意一列进行内积时，结果都必须恰好为1。换言之，任意一行和任意一列在相同位置上同时为1的情况只有一处。 通过利用已知解构造新解是线性代数中常用的技巧。因为全1矩阵在任意排列矩阵的共轭作用下保持不变，所以我们可以通过交换原解的行和列来快速找到其他解。此外，对矩阵进行转置也同样满足原方程。 进一步深入分析可以发现，满足条件的矩阵每行每列都必须恰好有两个1。将4个行列索引分为两组，每组2个，共有3种分法。只要行和列采用不同的分法进行组合，就能构造出一个符合条件的矩阵，从而可以穷举出包含已知解在内的总共12个解。题目虽然只要求尽可能多地列出其他解，但通过这种结构化构造，我们实际上已经找出了全部的剩余解。