代数的組合せ論の問題

難易度 2大学院の講義の演習問題レベル証明問題大学院数学代数的組合せ論

$q$ を素数冪、 $F_{q}$ を $q$ 元体とし、 $n, m$ を $0$ 以上の整数とする。 $0 \leq k \leq m$ に対して $q$ 二項係数を
$(k m)_{q} = i = 0 \prod k - 1 \frac{q ^{m - i} - 1}{q ^{k - i} - 1} (k = 0 のときは空積で (0 m)_{q} = 1)$
で定める。次の事実は証明なしに用いてよい。

$(k m)_{q}$ は $F_{q}^{m}$ の $k$ 次元部分空間の個数に等しい。
$F_{q}^{m}$ の部分空間全体を包含関係で順序づけた半順序集合を $L_{m}$ とすると、そのメビウス関数は、 $W \subseteq V$ のとき $μ (W, V) = (- 1)^{d} q^{d (d - 1) /2}$ （ $d = dim V - dim W$ ）である。
有限半順序集合上のメビウスの反転公式。

このとき、 $F_{q}^{n}$ から $F_{q}^{m}$ への全射な線形写像の個数を 2 通りに数えることにより、等式
$k = 0 \sum m (- 1)^{k} q^{k (k - 1) /2} (k m)_{q} q^{n (m - k)} = i = 0 \prod m - 1 (q^{n} - q^{i})$
が成り立つことを証明せよ。ただし $m = 0$ のとき右辺は空積で $1$ とし、 $F_{q}^{0} = {0}$ とする。

この問題で使うもの

有限体上の階数を指定した行列の個数（説明と入口の問題）
メビウス反転公式と直積の積公式（説明と入口の問題）
有限体上の数え上げと包除原理（説明と入口の問題）

この問題を解けるようになるまで（13 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

両辺がどちらも「 $F_{q}^{n} \to F_{q}^{m}$ の全射線形写像の個数」になることを示します。右辺は直接数え、左辺は部分空間の半順序集合 $L_{m}$ 上のメビウスの反転（包除原理の $q$ 類似）で数えましょう。

ヒント 2

部分空間 $W$ に対し「像がちょうど $W$ 」の写像の個数 $f (W)$ と「像が $W$ に含まれる」写像の個数 $g (W)$ を考えると、 $g (W) = \sum_{U \subseteq W} f (U)$ が成り立ち、 $dim W = j$ なら $g (W) = q^{nj}$ です。

ヒント 3

右辺: 表現行列の $m$ 本の行が線形独立になるように順に選ぶと、 $i + 1$ 本目はすでに選んだ $i$ 本の張る空間（ $q^{i}$ 個の元）の外から選ぶことになります。左辺: $f (F_{q}^{m}) = \sum_{U} μ (U, F_{q}^{m}) g (U)$ を部分空間の次元ごとにまとめましょう。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

全射線形写像を、行ベクトルが線形独立な $m \times n$ 行列（階数 $m$ ）と 1 対 1 に対応させている（2 点）
行ベクトルを順に選び、 $i + 1$ 本目の選び方が前の選び方によらず $q^{n} - q^{i}$ 通りであることから右辺の積を導いている（2 点）
像がちょうど $W$ である写像の個数 $f$ と像が $W$ に含まれる写像の個数 $g$ を定め、 $g (W) = \sum_{U \subseteq W} f (U)$ と $g (W) = q^{n d i m W}$ を示している（3 点）
メビウスの反転を $W = F_{q}^{m}$ に適用し、与えられた $μ$ の値と $j$ 次元部分空間の個数 $(j m)_{q}$ を用いて次元ごとにまとめている（2 点）
$k = m - j$ の置き換えで必要な $(m - k m)_{q} = (k m)_{q}$ を（直交補空間などで）正当化し、両辺が同じ数を数えることから等式を結論している（1 点）

結果を記録する（このブラウザにだけ保存されます）:

模範解答を読む

$H$ を $F_{q}^{n}$ から $F_{q}^{m}$ への線形写像全体とし、 $N$ をそのうち全射であるものの個数とする。 $N$ が右辺と左辺の両方に等しいことを示す。

(i) 直接数える（右辺）. 線形写像 $F_{q}^{n} \to F_{q}^{m}$ は、標準基底に関する表現行列によって $m \times n$ 行列 $A$ と 1 対 1 に対応する（ $x \mapsto A x$ ）。写像が全射であることは列空間が $F_{q}^{m}$ であること、すなわち $rank A = m$ と同値であり、行階数と列階数は等しいので、これは $A$ の $m$ 本の行ベクトル $r_{1}, \dots, r_{m} \in F_{q}^{n}$ が線形独立であることと同値である。

線形独立な組 $(r_{1}, \dots, r_{m})$ を順に選んで数える。 $0 \leq i \leq m - 1$ とし、 $r_{1}, \dots, r_{i}$ が線形独立に選ばれているとき、 $r_{1}, \dots, r_{i + 1}$ が線形独立であるための必要十分条件は $r_{i + 1} \in / span (r_{1}, \dots, r_{i})$ である。この張る空間は $i$ 次元なので $q^{i}$ 個の元をもち、 $r_{i + 1}$ の選び方は $q^{n} - q^{i}$ 通りである（ $i = n$ のときは張る空間が $F_{q}^{n}$ 全体で $0$ 通り）。選び方の数は前に選んだ $r_{1}, \dots, r_{i}$ によらないので、 $i = 0, 1, \dots, m - 1$ について掛け合わせて
$N = i = 0 \prod m - 1 (q^{n} - q^{i}) .$
（ $m > n$ のときは $i = n$ の因子が $0$ となり、全射が存在しないことと整合する。 $m = 0$ のときは零写像だけが全射で $N = 1$ となり、空積 $1$ と一致する。）

(ii) メビウスの反転で数える（左辺）. $L_{m}$ の各元 $W$ （ $F_{q}^{m}$ の部分空間）に対し
$f (W) = # {φ \in H ∣ Im φ = W}, g (W) = # {φ \in H ∣ Im φ \subseteq W}$
とおく。各 $φ$ の像はちょうど 1 つの部分空間なので、像が $W$ に含まれる写像を像ごとに分類して $g (W) = \sum_{U \in L_{m}, U \subseteq W} f (U)$ が成り立つ。

$g (W)$ を求める。 $dim W = j$ とする。像が $W$ に含まれる線形写像 $F_{q}^{n} \to F_{q}^{m}$ は線形写像 $F_{q}^{n} \to W$ と 1 対 1 に対応し、線形写像 $F_{q}^{n} \to W$ は標準基底 $e_{1}, \dots, e_{n}$ の行き先を $W$ （ $q^{j}$ 個の元）の中で自由に選ぶことでただ 1 つに定まる。よって $g (W) = (q^{j})^{n} = q^{nj}$ である。

$L_{m}$ は有限半順序集合なので、メビウスの反転公式（すべての $W$ で $g (W) = \sum_{U \subseteq W} f (U)$ ならば $f (W) = \sum_{U \subseteq W} μ (U, W) g (U)$ ）が使える。これを $W = F_{q}^{m}$ に適用すると、全射とは像が $F_{q}^{m}$ であることなので
$N = f (F_{q}^{m}) = U \in L_{m} \sum μ (U, F_{q}^{m}) g (U) .$
$dim U = j$ のとき、与えられた事実で $d = m - j$ とすると $μ (U, F_{q}^{m}) = (- 1)^{m - j} q^{(m - j) (m - j - 1) /2}$ であり、 $g (U) = q^{nj}$ である。これらは $j$ だけで決まり、 $j$ 次元部分空間は $(j m)_{q}$ 個あるから
$N = j = 0 \sum m (j m)_{q} (- 1)^{m - j} q^{(m - j) (m - j - 1) /2} q^{nj} .$
ここで $k = m - j$ と置き換える（ $j = 0, \dots, m$ と $k = m, \dots, 0$ が対応する）。 $(m - k m)_{q} = (k m)_{q}$ を確かめる。 $F_{q}^{m}$ の対称双線形形式 $⟨ x, y ⟩ = \sum_{i = 1}^{m} x_{i} y_{i}$ は非退化なので、部分空間 $W$ に対し $dim W^{⊥} = m - dim W$ かつ $(W^{⊥})^{⊥} = W$ （ $W \subseteq (W^{⊥})^{⊥}$ で次元が等しい）が成り立つ。よって $W \mapsto W^{⊥}$ は $(m - k)$ 次元部分空間全体から $k$ 次元部分空間全体への全単射であり、両者の個数は等しい。したがって
$N = k = 0 \sum m (- 1)^{k} q^{k (k - 1) /2} (k m)_{q} q^{n (m - k)} .$

結論. (i) と (ii) は同じ数 $N$ を数えているので
$k = 0 \sum m (- 1)^{k} q^{k (k - 1) /2} (k m)_{q} q^{n (m - k)} = i = 0 \prod m - 1 (q^{n} - q^{i})$
が成り立つ。 $■$

（確認: $q = 2, n = m = 2$ のとき、左辺は $(1 2)_{2} = 3$ より $16 - 3 \cdot 4 + 2 = 6$ 、右辺は $(4 - 1) (4 - 2) = 6$ で一致する。）

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が模範解答を見ずに 3 回証明を試み、3 回証明できました
2 つの AI が独立に、模範解答の証明を 1 ステップずつ確かめました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる