千葉大学 理学研究科 基盤理学専攻 数学・情報数理学コース 2013年8月実施 専門 B10

标签：

• Matrix-Rank
• Bipartite-Graph

Author

祭音Myyura (co-authored with GPT 6 Astra)

Description

$P\ge2$ を整数とする。二元体上の $P$ 次行列 $I(1)$ は、第 $i$ 行の第 $i+1\pmod P$ 列だけが $1$ の巡回置換行列とし、$I(b)=I(1)^b$ とおく。

$$H=\begin{pmatrix} I(0)&I(0)&I(2)&I(1)&I(0)&I(0)\\ I(3)&I(4)&I(7)&I(7)&I(7)&I(8)\\ I(-1)&I(1)&I(5)&I(6)&I(7)&I(9) \end{pmatrix},\qquad \Gamma=\begin{pmatrix}0&H\\H^{\mathsf T}&0\end{pmatrix}.$$

(1) $\operatorname{rank}H\le3P-2$ を示せ。

(2–1) $P=10$、(2–2) $P=9$ のそれぞれについて、隣接行列 $\Gamma$ のグラフの最小内径（最短サイクル長）を求めよ。

题目描述

设 $P\ge2$，$I(1)$ 是向右循环移位的 $P$ 阶置换矩阵，$I(b)=I(1)^b$，在二元域上定义上述分块矩阵 $H,\Gamma$。(1) 证明 $\operatorname{rank}H\le3P-2$。(2) 分别求 $P=10,9$ 时以 $\Gamma$ 为邻接矩阵的图的围长。

Kai

(1)

各ブロック行の $P$ 行をすべて足すと、同じ全成分 $1$ の長さ $6P$ の行ベクトルになる。したがって第 $1$・第 $2$ ブロック行の和、第 $1$・第 $3$ ブロック行の和という独立な二つの行関係が存在する。ゆえに $\operatorname{rank}H\le3P-2$。

(2)

指数行列を $E=(e_{rj})$ とする。左頂点 $(r,i)$ と右頂点 $(j,k)$ は $k\equiv i+e_{rj}\pmod P$ のとき隣接する。グラフは単純二部グラフである。

異なる二つのブロック行 $r,s$ と異なる二列 $j,l$ が $4$ サイクルを作る条件は

$$e_{rj}-e_{sj}\equiv e_{rl}-e_{sl}\pmod P.$$

三組の行差は

$$(-3,-4,-5,-6,-7,-8),\quad (1,-1,-3,-5,-7,-9),\quad (4,3,2,1,0,-1).$$

$P=10$ では第二の行差の第 $1,6$ 成分が等しい。よって $4$ サイクルが存在し、最小内径は $4$。

$P=9$ では各行差の成分はすべて相異なるため、$4$ サイクルはない。一方、ブロック番号と内部添字を $0$ 始まりで書くと、

$$L_{0,0}\to R_{0,0}\to L_{1,6}\to R_{1,1} \to L_{2,0}\to R_{5,0}\to L_{0,0}$$

は $6$ サイクルである。よって 最小内径は $6$。