トップ› 大阪大学› 2007年› 理系第5問

大阪大学 2007年理系第5問解説

方針・初手

行列の積が定義できる条件である「左の行列の列数と右の行列の行数が一致すること」に着目し、隣り合う行列の選び方の規則を把握する。また、各行列を具体的に計算すると、$A$ と $D$ はそれぞれ単位行列であり、$BC = O$ となることに気づくのが最大のポイントである。これにより、積が零行列になる条件を単純な文字列（行列の並び）のルールに帰着して考えることができる。

解法1

(1)

各行列の行数と列数は以下の通りである。

$A$: $2 \times 2$ 行列
$B$: $2 \times 3$ 行列
$C$: $3 \times 2$ 行列
$D$: $3 \times 3$ 行列

行列の積 $XY$ が定義できるのは、「$X$ の列数 $=$ $Y$ の行数」のときである。したがって、$M_k$ の次に並べることができる $M_{k+1}$ の条件は次のようになる。

$M_k \in \{A, C\}$ （列数が2）のとき、$M_{k+1} \in \{A, B\}$ （行数が2）
$M_k \in \{B, D\}$ （列数が3）のとき、$M_{k+1} \in \{C, D\}$ （行数が3）

$n$ 個の積 $M_1 M_2 \cdots M_n$ が定義できる並びのうち、最後の行列 $M_n$ の列数が2であるものの総数を $p_n$、列数が3であるものの総数を $q_n$ とする。 $M_1$ は $A, B, C, D$ のいずれでもよいので、

$$ p_1 = 2 \quad (M_1 = A, C) $$

$$ q_1 = 2 \quad (M_1 = B, D) $$

である。上記の遷移規則より、以下の漸化式が成り立つ。

$$ \begin{cases} p_{k+1} = p_k + q_k \\ q_{k+1} = p_k + q_k \end{cases} $$

これより $p_{k+1} = q_{k+1}$ であり、$p_{k+1} = 2p_k$ を得る。よって、数列 $\{p_k\}$ は初項 $p_1 = 2$、公比 $2$ の等比数列となるから、

$$ p_n = 2 \cdot 2^{n-1} = 2^n $$

同様に $q_n = 2^n$ である。積が定義できる並びの総数は $p_n + q_n$ であるから、

$$ p_n + q_n = 2^n + 2^n = 2^{n+1} $$

(2)

与えられた行列をよく見ると、$A = I_2$ （2次の単位行列）、$D = I_3$ （3次の単位行列）である。また、$B$ と $C$ の積を計算すると、

$$ BC = \begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix} \begin{pmatrix} 1 & -1 \\ -1 & 1 \\ 1 & -1 \end{pmatrix} = \begin{pmatrix} 1-1+0 & -1+1+0 \\ 0-1+1 & 0+1-1 \end{pmatrix} = \begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix} = O $$

$$ CB = \begin{pmatrix} 1 & -1 \\ -1 & 1 \\ 1 & -1 \end{pmatrix} \begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 0 & -1 \\ -1 & 0 & 1 \\ 1 & 0 & -1 \end{pmatrix} \neq O $$

となる。単位行列である $A, D$ を掛けても行列自体は変化しないため、積の列から $A, D$ を無視して $B, C$ だけを取り出した列（これを「コア列」と呼ぶ）を考える。コア列に $BC$ が含まれる場合、その間には $D$ がいくつか挟まる可能性があるが、$B D \cdots D C = B I_3 \cdots I_3 C = BC = O$ となるため、全体の積も零行列になる。逆に、コア列が $BC$ を含まない場合、要素の構成から積は零行列にはならない。（コア列に隣り合う文字は列数・行数の関係から必ず $B$ と $C$ が交互になるため、コア列が $BC$ を含まないものは $\emptyset, B, C, CB$ のいずれかに限られる。これらを計算すると確かに零行列ではない）

積が $2 \times 3$ 行列となるには、積の行数が $2$、列数が $3$ であればよいので、$M_1 \in \{A, B\}$ かつ $M_n \in \{B, D\}$ が必要である。この条件のもとで、積が零行列にならない（＝コア列が $BC$ を含まない）ものを探す。コア列の候補は以下の4パターンである。

(ア) コア列が $\emptyset$ の場合: 積は $A \cdots A$ ($2 \times 2$) または $D \cdots D$ ($3 \times 3$) となり、サイズが不適。
(イ) コア列が $B$ の場合: 積は $A \cdots A B D \cdots D$ の形。これは $M_1 \in \{A, B\}, M_n \in \{B, D\}$ を満たし、サイズは $2 \times 3$ となる。$B \neq O$ より条件を満たす。
(ウ) コア列が $C$ の場合: 積は $D \cdots D C A \cdots A$ の形。$M_1 \in \{C, D\}$ となり、行数が3になるので不適。
(エ) コア列が $CB$ の場合: 積は $D \cdots D C A \cdots A B D \cdots D$ の形。これも $M_1 \in \{C, D\}$ となり、行数が3になるので不適。

以上より、条件を満たす並びは $A \cdots A B D \cdots D$ の形のみである。これは $n$ 個の枠のうち、$B$ が入る場所を1つ決めれば、それより前は全て $A$、後は全て $D$ と一意に定まる。よって、$B$ の位置の選び方と等しく、その数は $n$ 通りである。

(3)

(2)の考察から、積が零行列にならないための必要十分条件は、コア列が $\emptyset, B, C, CB$ のいずれかになることである。それぞれの場合について場合の数を求める。

(i) コア列が $\emptyset$ の場合 $A$ だけが並ぶ $A \cdots A$ か、$D$ だけが並ぶ $D \cdots D$ の $2$ 通り。
(ii) コア列が $B$ の場合 (2)で求めた通り、$A \cdots A B D \cdots D$ の形で $n$ 通り。
(iii) コア列が $C$ の場合 $D \cdots D C A \cdots A$ の形である。$C$ が入る場所を1つ選べば前後の配列が決まるため、$n$ 通り。
(iv) コア列が $CB$ の場合 $D \cdots D C A \cdots A B D \cdots D$ の形である。 $n$ 個の枠から $C$ と $B$ が入る2つの場所を選べば（左が $C$、右が $B$）、その他の部分は位置に応じて $D, A, D$ に一意に決まる。その選び方は ${}_n\mathrm{C}_{2}$ 通りであるから、

$$ \frac{n(n-1)}{2} $$

通り。これらは互いに排反であるから、求める総数は

$$ 2 + n + n + \frac{n(n-1)}{2} = \frac{4 + 4n + n^2 - n}{2} = \frac{n^2 + 3n + 4}{2} $$

解説

行列の積が定義できる条件（左の列数＝右の行数）と、積を計算したときの性質を組み合わせて場合の数を問う、漸化式および場合の数の融合問題である。 $A, D$ が単位行列であることに気づくこと、そして $BC=O$ になることに着目して「実質的に積を決定する文字列（コア列）」を抜き出す発想が鍵となる。状態遷移図を描いて考えると、禁止された遷移（$B$ の次に $C$ を選ぶこと）を除外した経路の数を数え上げる問題に帰着でき、見通しよく解くことができる。