GCD矩阵 LDU分解

hbghlyj

REU12 第10页

78. (GCD matrix) Let $D=\left(d_{i j}\right)_{n \times n}$ where $d_{i j}=\gcd(i, j)$. Then,
$$
\det(D)=\varphi(1) \varphi(2) \ldots \varphi(n)
$$
where $\varphi$ is Euler's $\varphi$ function: $\varphi(m)=|\{k \mid 1 \leq k \leq m, \gcd(k, m)=1\}|$.

hbghlyj

math.stackexchange.com/questions/299652/let-t … prove-t?noredirect=1
math.stackexchange.com/questions/1199581/surp … tient-f?noredirect=1
core.ac.uk/download/pdf/82233356.pdf

由欧拉函数的性质,$m=\sum_{k\mid m}\phi(k)$,有
$$a_{i,j}=\gcd(i,j)=\sum_{k\mid\gcd(i,j)}\phi(k)=\sum_{k|i,k|j}\phi(k).$$
一般地,

定理:
对于任意函数$\psi$,定义矩阵$A=(a_{i,j})$为$a_{i,j}=\sum_{k\mid i,k\mid j}\psi(k)$,则$\det A=\psi(1)\psi(2)\cdots\psi(n)$.

证明:
定义矩阵$B=(b_{i,j})$为$b_{i,j}=\begin{cases}1&i\mid j\\0&\text{otherwise}\end{cases}$
$i\mid j⇒i≤j$，所以$B$是上三角形矩阵，对角线上的元素全为1，所以$\det B=1$。
令$C=\operatorname{diag}(\psi(1),\ldots,\psi(n))$
矩阵乘法得$(B^tCB)_{i,j}=\sum_kb_{k,i}\,\psi(k)\,b_{k,j}$
$b_{k,i}\,b_{k,j}=\begin{cases}1&k|i,k|j\\0&\text{otherwise}\end{cases}\implies(B^tCB)_{i,j}=\sum_{k|i,k|j}\psi(k)$,
所以$A=B^tCB$,所以$\det A=(\det B)^2\det C=\psi(1)\cdots\psi(n).$$□$