有限体上の階数を指定した行列の個数

$F_{q}$ 上の階数 $r$ の $m \times n$ 行列の個数を、列空間（ $r$ 次元部分空間）の選び方と全射の個数に分けて $(r n)_{q} \prod_{i = 0}^{r - 1} (q^{m} - q^{i})$ の形で $q$ の多項式として求められる

前提

中学までに習ったことだけで始められます。

説明

元が $q$ 個の有限体 $F_{q}$ の成分をもつ $m \times n$ 行列のうち、階数がちょうど $r$ のものが何個あるかを、 $q$ の式として求められるようになります。考え方は「列ベクトルたちが張る $r$ 次元の空間（列空間）をまず選び、次に列がその空間をちょうど埋め尽くすような並べ方を数える」という 2 段階の積の法則です。結果は $q$ の多項式になり、符号理論・ランダム行列の確率・有限群の位数の計算などで使われます。

なぜそうしてよいのか

言葉を確認します。 $F_{q}$ は四則演算（0 で割る以外）ができる、元が $q$ 個の集まり（体）です。たとえば $F_{2} = {0, 1}$ は 2 で割った余りで計算します。 $F_{q}^{m}$ は成分が $F_{q}$ の長さ $m$ の列ベクトル全体で、 $q^{m}$ 個の元があります。ベクトル $v_{1}, \dots, v_{k}$ の一次結合 $c_{1} v_{1} + \dots + c_{k} v_{k}$ 全体をそれらが張る部分空間といい、 $c_{1} v_{1} + \dots + c_{k} v_{k} = 0$ となるのが $c_{1} = \dots = c_{k} = 0$ だけのとき一次独立といいます。部分空間 $W$ を張る一次独立なベクトルの組を $W$ の基底といいます。線形代数の基本事実として、 $F_{q}^{m}$ の部分空間には必ず基底があり、どの基底も同じ個数のベクトルからなること、また $F_{q}^{m}$ の中の一次独立なベクトルは $m$ 個以下であることを認めて使います。この一定の個数を $W$ の次元といいます。行列 $A$ の階数は、 $A$ の列ベクトルが張る部分空間（列空間）の次元です。

2 つの基本的な数え方を準備します。(a) $W$ の基底を $w_{1}, \dots, w_{r}$ とすると、 $W$ の各元は $c_{1} w_{1} + \dots + c_{r} w_{r}$ の形にただ 1 通りに書けます（2 通りに書けたら差をとって一次独立性に反する）。よって $W$ の元は係数の組 $(c_{1}, \dots, c_{r}) \in F_{q}^{r}$ と 1 対 1 に対応し、 $r$ 次元の $W$ はちょうど $q^{r}$ 個の元をもちます。(b) 一次独立な $v_{1}, \dots, v_{i}$ に $v$ を付け加えた組が一次独立であるのは、 $v$ が $v_{1}, \dots, v_{i}$ の張る空間に入らないときちょうどです（入れば明らかに関係式ができ、入らなければ関係式の $v$ の係数は 0 でなければならず、残りは $v_{1}, \dots, v_{i}$ の独立性から 0）。

まず $F_{q}^{m}$ の $r$ 次元部分空間の個数を数えます。一次独立な $r$ 個のベクトルを順に選ぶと、(b) より 1 個目は $0$ 以外で $q^{m} - 1$ 通り、 $i + 1$ 個目は既に選んだ $i$ 個が張る空間（(a) より $q^{i}$ 個の元）以外で $q^{m} - q^{i}$ 通りなので、順序付きの組は $\prod_{i = 0}^{r - 1} (q^{m} - q^{i})$ 個です。各組はちょうど 1 つの $r$ 次元部分空間（その組が張る空間）の順序付き基底です。逆に 1 つの $r$ 次元部分空間 $W$ の中で一次独立な $r$ 個の組を同じように数えると $\prod_{i = 0}^{r - 1} (q^{r} - q^{i})$ 組あり、それらはどれも $q^{r}$ 個の元をもつ $W$ の部分空間を張るので $W$ 自身を張り、 $W$ の基底になります。したがって部分空間の個数は
$(r m)_{q} = i = 0 \prod r - 1 \frac{q ^{m} - q ^{i}}{q ^{r} - q ^{i}}$
です（これを $q$ 二項係数と呼びます）。

次に、列空間がちょうど $W$ （ $r$ 次元）になる $m \times n$ 行列を数えます。 $W$ の基底 $w_{1}, \dots, w_{r}$ を 1 つ固定すると、列がすべて $W$ に入る行列の各列 $x_{j}$ は (a) により $x_{j} = b_{1 j} w_{1} + \dots + b_{r j} w_{r}$ とただ 1 通りに書けるので、行列は係数を並べた $r \times n$ 行列 $B = (b_{k j})$ と 1 対 1 に対応します。 $B$ の第 $j$ 列を $y_{j} \in F_{q}^{r}$ とすると、対応 $y \mapsto y_{1} w_{1} + \dots + y_{r} w_{r}$ は $F_{q}^{r}$ から $W$ への一次結合を保つ 1 対 1 対応なので、「 $x_{1}, \dots, x_{n}$ が $W$ を張る」ことは「 $y_{1}, \dots, y_{n}$ が $F_{q}^{r}$ を張る」こと（列の写し方が全射であること）と同じです。これが「 $B$ の $r$ 本の行ベクトル（ $F_{q}^{n}$ の元）が一次独立」と同値であることを示します。

・行が一次従属なら列は張らない: 行に $c_{1} (第 1 行) + \dots + c_{r} (第 r 行) = 0$ （ $c = (c_{1}, \dots, c_{r}) \neq = 0$ ）という関係があると、成分ごとに見てどの列 $y$ も $c_{1} y_{1} + \dots + c_{r} y_{r} = 0$ を満たします（ここで $y_{k}$ は $y$ の第 $k$ 成分）。この式を満たす $y$ 全体は一次結合で閉じているので、列の張る空間もこの式を満たします。一方 $c_{k} \neq = 0$ となる $k$ について、第 $k$ 成分だけ $1$ の単位ベクトル $e_{k}$ は $c_{k} \neq = 0$ を与えるので式を満たしません。よって列は $F_{q}^{r}$ を張りません。

・列が張らなければ行は一次従属: 列の張る空間 $U$ が $F_{q}^{r}$ より真に小さいとします。 $U$ の基底 $u_{1}, \dots, u_{s}$ をとり、(b) を使って $U$ の外のベクトルを 1 本ずつ付け加えていくと、一次独立性を保ったまま延長でき、一次独立なベクトルは $r$ 個以下なので、張る空間が $F_{q}^{r}$ 全体になったところで止まります。こうして $F_{q}^{r}$ の基底 $u_{1}, \dots, u_{s}, u_{s + 1}, \dots, u_{r}$ （ $s < r$ ）が得られます。各 $y \in F_{q}^{r}$ をこの基底で $a_{1} u_{1} + \dots + a_{r} u_{r}$ とただ 1 通りに表し、 $f (y) = a_{r}$ （ $u_{r}$ の係数）とおきます。 $f$ は一次結合を保つので、 $y = y_{1} e_{1} + \dots + y_{r} e_{r}$ より $f (y) = c_{1} y_{1} + \dots + c_{r} y_{r}$ （ $c_{k} = f (e_{k})$ ）の形の 1 次式です。 $f (u_{r}) = 1$ なので $c \neq = 0$ であり、 $U$ の元は $u_{1}, \dots, u_{s}$ の一次結合なので $f = 0$ です。とくにすべての列 $y_{j}$ で $c_{1} y_{1} + \dots + c_{r} y_{r} = 0$ となり、これを第 $j$ 成分とみれば $c_{1} (第 1 行) + \dots + c_{r} (第 r 行) = 0$ という自明でない関係になります。

以上より、列空間が $W$ になる行列の個数は、一次独立な $r$ 本の行ベクトル（ $F_{q}^{n}$ の元）の順序付きの組の個数で、上と同じ数え方で $\prod_{i = 0}^{r - 1} (q^{n} - q^{i})$ 個です。 $W$ の選び方と掛けて、積の法則より階数 $r$ の $m \times n$ 行列の個数は
$(r m)_{q} i = 0 \prod r - 1 (q^{n} - q^{i}) = i = 0 \prod r - 1 \frac{( q ^{m} - q ^{i} ) ( q ^{n} - q ^{i} )}{q ^{r} - q ^{i}}$
です。右辺は $m$ と $n$ を入れ替えても同じなので、 $(r n)_{q} \prod_{i = 0}^{r - 1} (q^{m} - q^{i})$ と書いても等しくなります。なお $r = 0$ のときは積が空で値 $1$ （零行列 1 個）です。

手順

$q$ , 行数 $m$ , 列数 $n$ , 階数 $r$ を確認する（ $0 \leq r \leq min (m, n)$ でなければ個数は $0$ ）
列空間の選び方として、 $F_{q}^{m}$ の $r$ 次元部分空間の個数 $(r m)_{q} = \prod_{i = 0}^{r - 1} \frac{q ^{m} - q ^{i}}{q ^{r} - q ^{i}}$ を計算する
列空間を固定したとき、列がそれを張る行列の個数（全射の個数、すなわち一次独立な $r$ 本の行の組の個数） $\prod_{i = 0}^{r - 1} (q^{n} - q^{i})$ を計算する
2 つを掛けて個数を求める。検算に、 $m$ と $n$ を入れ替えた $(r n)_{q} \prod_{i = 0}^{r - 1} (q^{m} - q^{i})$ と一致するか確かめる

例題

成分が $F_{2} = {0, 1}$ （2 で割った余りで計算する）の $3 \times 4$ 行列のうち、階数が $2$ であるものの個数を求めよ。

例題の解答

手順 1: $q = 2$ , $m = 3$ , $n = 4$ , $r = 2$ 。 $r \leq min (3, 4)$ を満たす。

手順 2: 列空間は $F_{2}^{3}$ の 2 次元部分空間で、その個数は
$(2 3)_{2} = \frac{( 2 ^{3} - 1 ) ( 2 ^{3} - 2 )}{( 2 ^{2} - 1 ) ( 2 ^{2} - 2 )} = \frac{7 \cdot 6}{3 \cdot 2} = 7.$

手順 3: 列空間を 1 つ固定したとき、列がそれを張る行列は、一次独立な 2 本の行ベクトル（ $F_{2}^{4}$ の元）の順序付きの組と同じ数で
$(2^{4} - 1) (2^{4} - 2) = 15 \cdot 14 = 210.$

手順 4: 積の法則より $7 \times 210 = 1470$ 。検算: $(2 4)_{2} = \frac{15 \cdot 14}{3 \cdot 2} = 35$ , $(2^{3} - 1) (2^{3} - 2) = 42$ で $35 \times 42 = 1470$ と一致する。

よって求める個数は $1470$ 。

答え: $1470$

よくある誤り

$q$ 二項係数と後ろの積で $m$ と $n$ を揃えてしまう誤り。例題で $(2 3)_{2} (2^{3} - 1) (2^{3} - 2) = 7 \cdot 42 = 294$ とするのは誤り（これは $3 \times 3$ 行列の個数）。正しくは $(r m)_{q} \prod (q^{n} - q^{i})$ か $(r n)_{q} \prod (q^{m} - q^{i})$ のように、一方に $m$ 、他方に $n$ を使う
部分空間の個数にふつうの二項係数 $(r m)$ を使ってしまう誤り。 $F_{2}^{3}$ の 2 次元部分空間は $(2 3) = 3$ 個ではなく、正しくは $(2 3)_{2} = 7$ 個
部分空間の個数を、一次独立なベクトルの順序付きの組の個数 $\prod_{i = 0}^{r - 1} (q^{m} - q^{i})$ のままにしてしまう誤り。1 つの部分空間が $\prod_{i = 0}^{r - 1} (q^{r} - q^{i})$ 回数えられているので、正しくはそれで割る
積の添字を $i = 1$ から始めてしまう誤り。1 本目のベクトルは $0$ 以外を選ぶので因子は $q^{n} - q^{0} = q^{n} - 1$ から始まり、正しくは $\prod_{i = 0}^{r - 1} (q^{n} - q^{i})$

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 1（大学院の講義の例題レベル）
$q$ を素数の累乗とし、 $F_{q}$ を位数 $q$ の有限体とする。 $F_{q}$ の元を成分とする $3 \times 3$ 行列のうち、階数がちょうど $2$ であるものの個数を $q$ の式で求めよ。

この技能を使う問題

この技能の次に学べること

有限体上の数え上げと包除原理（大学院数学代数的組合せ論）
有限アーベル群の自己同型群の位数（大学院数学群論）
有限体上の行列群の位数（大学院数学群論）