東京大学 2012年 理系 第5問 解説

方針・初手

行列が条件 (D) を満たすための必要十分条件を、行列式の言葉で言い換えることから始める。 平面上の4点 $(0,0), (x,y), (x+z, y+w), (z,w)$ が面積 $1$ の平行四辺形の頂点をなすことは、2つのベクトル $\begin{pmatrix} x \\ y \end{pmatrix}$ と $\begin{pmatrix} z \\ w \end{pmatrix}$ が作る平行四辺形の面積が $1$ であることと同値である。 この面積は行列 $\begin{pmatrix} x & y \\ z & w \end{pmatrix}$ の行列式の絶対値に等しい。したがって、行列 $X$ が条件 (D) を満たすことは、「$X$ の成分がすべて整数であり、かつ $|\det(X)| = 1$ が成り立つこと」と同値になる。これを前提として各小問の証明を進める。

解法1

(1)

行列 $A$ が条件 (D) を満たすため、$a, b, c, d$ は整数であり、かつ

$$ |\det(A)| = |ad - bc| = 1 $$

が成り立つ。 また、行列 $B$ とその逆行列 $B^{-1}$ はそれぞれ、

$$ B = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}, \quad B^{-1} = \begin{pmatrix} 1 & -1 \\ 0 & 1 \end{pmatrix} $$

である。これらは成分がすべて整数であり、

$$ \det(B) = 1, \quad \det(B^{-1}) = 1 $$

を満たす。 成分が整数である行列同士の積はやはり整数を成分とする行列となるため、$BA$ および $B^{-1}A$ の成分はすべて整数である。 さらに、行列式の性質 $\det(XY) = \det(X)\det(Y)$ を用いると、

$$ |\det(BA)| = |\det(B)\det(A)| = 1 \cdot 1 = 1 $$

$$ |\det(B^{-1}A)| = |\det(B^{-1})\det(A)| = 1 \cdot 1 = 1 $$

となる。 よって、$BA$ および $B^{-1}A$ は成分がすべて整数で、かつ行列式の絶対値が $1$ となるため、条件 (D) を満たす。

(2)

$c = 0$ のとき、条件 (D) より、

$$ |\det(A)| = |ad - 0 \cdot b| = |ad| = 1 $$

となる。$a, d$ は整数であるから、取りうる値の組は $a = \pm 1, d = \pm 1$ のいずれかである。 $A$ に左から $B$ または $B^{-1}$ を次々にかけるという操作は、ある整数 $k$ を用いて $B^k$ を $A$ に左からかけることと同値である。 ここで $B^k = \begin{pmatrix} 1 & k \\ 0 & 1 \end{pmatrix}$ であるから、

$$ B^k A = \begin{pmatrix} 1 & k \\ 0 & 1 \end{pmatrix} \begin{pmatrix} a & b \\ 0 & d \end{pmatrix} = \begin{pmatrix} a & b + kd \\ 0 & d \end{pmatrix} $$

となる。 $d = \pm 1$ であるから $d^2 = 1$ となる。ここで $k = -bd$ と選ぶと、$b, d$ は整数なので $k$ も整数であり、

$$ b + kd = b - bd^2 = b - b = 0 $$

となる。 これは、$k > 0$ ならば $B$ を $k$ 回、$k < 0$ ならば $B^{-1}$ を $-k$ 回、$k = 0$ ならば何もかけないことで、行列を $\begin{pmatrix} a & 0 \\ 0 & d \end{pmatrix}$ の形にできることを意味している。 $a = \pm 1, d = \pm 1$ より、この行列は、

$$ \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} -1 & 0 \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}, \begin{pmatrix} -1 & 0 \\ 0 & -1 \end{pmatrix} $$

のいずれかに一致する。

(3)

$BA$ および $B^{-1}A$ を計算すると、それぞれ

$$ BA = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} a & b \\ c & d \end{pmatrix} = \begin{pmatrix} a + c & b + d \\ c & d \end{pmatrix} $$

$$ B^{-1}A = \begin{pmatrix} 1 & -1 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} a & b \\ c & d \end{pmatrix} = \begin{pmatrix} a - c & b - d \\ c & d \end{pmatrix} $$

となる。 これらを $\begin{pmatrix} x & y \\ z & w \end{pmatrix}$ とおいたとき、評価すべき値 $|x| + |z|$ は、 $BA$ のときは $|a + c| + |c|$、 $B^{-1}A$ のときは $|a - c| + |c|$ である。 $|a| \geqq |c| > 0$ より、$a \neq 0, c \neq 0$ であるため、$a$ と $c$ の符号は同符号か異符号のいずれかである。

(i)

$a$ と $c$ が同符号の場合

$ac > 0$ であり、$|a| \geqq |c|$ より $|a - c| = |a| - |c|$ が成り立つ。 このとき、$B^{-1}A$ について考えると、

$$ |x| + |z| = |a - c| + |c| = (|a| - |c|) + |c| = |a| $$

となる。$|c| > 0$ であるから $|a| < |a| + |c|$ であり、

$$ |x| + |z| < |a| + |c| $$

を満たす。

(ii)

$a$ と $c$ が異符号の場合

$ac < 0$ であり、$|a| \geqq |c|$ より $|a + c| = |a| - |c|$ が成り立つ。 このとき、$BA$ について考えると、

$$ |x| + |z| = |a + c| + |c| = (|a| - |c|) + |c| = |a| $$

となる。同様に $|c| > 0$ であるから $|a| < |a| + |c|$ であり、

$$ |x| + |z| < |a| + |c| $$

を満たす。

（i）, （ii）より、$a, c$ の符号にかかわらず、$BA$ または $B^{-1}A$ の少なくとも一方は条件 $|x| + |z| < |a| + |c|$ を満たす。

解説

2次正方行列の基本変形（行の足し引き）に相当する操作を繰り返すことで、行列を簡単な対角行列に帰着させるというユークリッドの互除法に似た考え方を背景に持つ問題である。 (1) で条件の同値な言い換えに気づけるかが重要である。(3) では、$|a| \geqq |c| > 0$ という条件のもとで、「1回の操作で左側の列ベクトル $(a, c)$ の成分の絶対値の和を必ず小さくできる」ことを示しており、これがアルゴリズムの停止性（有限回の操作で $c = 0$ に到達すること）の保証となっている。

答え

(1)

略（解法1の証明を参照）

(2)

$c=0$ ならば、$A$ に $B$ または $B^{-1}$ を左から有限回かけることにより、

$$ \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} -1 & 0 \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}, \begin{pmatrix} -1 & 0 \\ 0 & -1 \end{pmatrix} $$

のいずれかにできる。

略（解法1の証明を参照）

(3)

$|a| \geqq |c| > 0$ のとき、$BA$ または $B^{-1}A$ の少なくとも一方は、$\begin{pmatrix} x & y \\ z & w \end{pmatrix}$ とおけば

$$ |x| + |z| < |a| + |c| $$

略（解法1の証明を参照）