@tefu0818
目次
定義
行列$G_n\in\R^{n\times n}$であって各成分$G_{ij}$が$i$と$j$の最大公約数で与えられるものをGCD行列と呼ぶ.
$G_{ij}= \mathrm{gcd}(i, j)$ということ. 例えばサイズ$6$のGCD行列は次の通り.
$$G_6 = \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 2 & 1 & 2 & 1 & 2\\ 1 & 1 & 3 & 1 & 1 & 3\\ 1 & 2 & 1 & 4 & 1 & 2\\ 1 & 1 & 1 & 1 & 5 & 1\\ 1 & 2 & 3 & 2 & 1 & 6\\ \end{bmatrix}$$次が知られている.
定理
$\varphi(n)$をオイラーのトーシェント関数とすれば,
$$\det G_n = \prod_{i=1}^n \varphi(i).$$証明
行列$L_n\in\R^{n\times n}$を
$$(L_n)_{ij}=\begin{cases} 1 &(\ j \mid i\ )\\ 0 &(\ j\nmid i\ ) \end{cases}$$で定める. $L_n$は下三角行列で対角成分は全て$1$, ゆえに$\det L_n=1$である.
また対角行列$D_n\in\R^{n\times n}$を$D_n = \mathrm{diag}(\varphi(1), \dots, \varphi(n))$とする.
$L_n D_n L_n^{\mathsf T}$の成分を計算すると
$$\begin{aligned} (L_n D_n L_n^{\mathsf T})_{ij}&=\sum_{k=1}^{n} \varphi(k) (L_n)_{ik}(L_n)_{jk} \\ &= \sum_{k\mid i \text{ and } k\mid j}^{n} \varphi(k)\\ &= \sum_{k\mid \mathrm{gcd}(i,j)}^{n} \varphi(k)\\ &= \mathrm{gcd}(i,j). \end{aligned}$$となる. 最後の等号はオイラー関数の性質 $\displaystyle\sum_{d\mid n} \varphi(d) = n$を使った.
結局$G_n=L_n D_n L_n^{\mathsf T}$なので,
$$\det G_n =\det (L_n D_n L_n^{\mathsf T}) = \det L_n \cdot \det D_n \cdot \det L_n^{\mathsf T}= \det D_n = \prod_{i=1}^n \varphi(i).$$GCD行列のLDL分解が結構きれいな構造を持ってるってことだけどこんなん知らんわって感じ.
一般に$S=\{x_1,\dots, x_n\}\in \N^{n}$:given のとき$A_{ij} = \mathrm{gcd}(x_i, x_j)$なる行列$A$が研究されてたりする. 何の役に立つかは不明. GCD行列の代わりにLCM行列もあったりする. 何の役に立つかは不明.
