Smith’s determinant（GCD矩阵的行列式）
翻译&修改自英文原文 Smith’s determinant
Smith’s determinant： \[
\left|\begin{array}{cccc}
\operatorname{gcd}(1,1) & \operatorname{gcd}(1,2) & \ldots &
\operatorname{gcd}(1, n) \\
\operatorname{gcd}(2,1) & \operatorname{gcd}(2,2) & \ldots &
\operatorname{gcd}(2, n) \\
\vdots & \vdots & & \vdots \\
\operatorname{gcd}(n, 1) & \operatorname{gcd}(n, 2) & \ldots
& \operatorname{gcd}(n, n)
\end{array}\right|=\varphi(1) \varphi(2) \cdots \varphi(n)
\]
考虑一个 \(n\times n\) 的矩阵 \(A_1 = [a_{i,j}]\) ，其中 \(a_{i,j} = \gcd(i,j)\) 。
1875年，一位名叫 Henry J. Smith 的爱尔兰数学家发布了一篇论文（你可能从 Smith normal form 听说过他）
他证明了 \(\operatorname{det} A_1=\prod_{k=1}^n \varphi(k)\) ，其中 \(\varphi\) 表示数论中的欧拉函数。
有趣的是，他使用了 \(\psi\) 而不是 \(\varphi\) 来表示欧拉函数，当然这符合当时的习惯。
他的证明并不优雅。于是在过了很久后（长达一个世纪），Pólya 和 Szegö 给出了一个优雅的证明。
他们的思路是这样的：
将 \(m=\sum_{d \mid m}\varphi(d)\) 的性质（欧拉反演）作用于 \(m =\gcd(i,j)\) 的情况，找到 \(n\times n\) 的三角矩阵 \(B_1,C_1\) ，
其对角线分别为 \(\varphi(1),\varphi(2),\cdots,\varphi(n)\) 和 \(1,1,\cdots,1\) ，并使得 \(A_1 = B_1C_1\) ，则有 \[ \operatorname{det} A_1=\operatorname{det} B_1 \operatorname{det} C_1=\varphi(1) \varphi(2) \cdots \varphi(n) \] 在本文中，我们将通过以上办法推广 Smith 定理
即我们将找到矩阵 \(\left[a_{i,j}\right]\) 的行列式，其中 \(a_{i,j}=(\operatorname{gcd}(i, j))^r, r \in \mathbb{R}\) 。
不过首先...（省略若干），你要知道狄利克雷卷积的一些性质
比如若 \(f,g\) 为积性函数，则它们的狄利克雷卷积 \(f * g\) 同为积性函数，证明我之前写过，看这里
符号
设 \(r \in \mathbb{R}\) ，我们定义数论函数 \(J_r\) 如下：（这里定义 \(\mathbb{N}\) 为正整数集合） \[ J_r(n)=n^r \prod_{p \mid n}\left(1-\frac{1}{p^r}\right), \quad n \in \mathbb{N} \] 其中 \(p\) 是 \(n\) 的质因数。
注释
注意到 \(J_1=\varphi\) ，即欧拉函数。如果 \(r \in \mathbb{N}\) ，则 \(J_r\) 称为 Jordan 函数 (Jordan’s totient function) ，因此 Jordan 函数是欧拉函数的推广。
可以证明，如果 \(r,n \in \mathbb{N}\) ，则 \(J_r(n)\) 是满足 \(\operatorname{gcd}\left(a_1, \cdots, a_r, n\right)=1\) （ 其中 \(1 \le a_i \le n\) ）的 \(r\) - 元组 \((a_1,\cdots,a_r) \in \mathbb{N}^r\) 的个数，不过我们这里用不到这个结论。
引理
若 \(r \in \mathbb{R}\) ，则 \(\sum_{d \mid n} J_r(d)=n^r\) 对任何 \(n\in \mathbb{N}\) 恒成立。
证明：考虑数论函数 \(I(n)=1\) ，令
\(f := J_r * I\)
。（感觉这个公式好丑啊）
显然 \(I\) 和 \(J_r\) 都是积性函数，则 \(f\) 也是积性函数。
对于任意质数 \(p\) 和 \(m \in \mathbb{N}\) \[ J_r\left(p^m\right)=p^{m r}\left(1-\frac{1}{p^r}\right)=p^{m r}-p^{(m-1) r} \] 所以 \[ f\left(p^m\right)=\left(J_r * I\right)\left(p^m\right)=\sum_{d \mid p^m} J_r(d)=\sum_{j=0}^m J_r\left(p^j\right)=1+\sum_{j=1}^m\left(p^{j r}-p^{(j-1) r}\right)=p^{m r} \] 则若 \(\prod_{j=1}^k p_j^{m_j}\) 是 \(n\) 的完全分解形式，又因为 \(f\) 是积性的， \[ \sum_{d \mid n} J_r(d)=\left(J_r * I\right)(n)=f(n)=\prod_{j=1}^k f\left(p_j^{m_j}\right)=\prod_{j=1}^k p_j^{m_j r}=n^r \] 证毕。
现在我们可以开始证明 Smith 定理的一般形式了。
定理
令 \(n \in \mathbb{N},r \in \mathbb{R}\) ，考虑 \(n\times n\) 的矩阵 \(A=[a_{i,j}]\) ，其中 \(a_{i,j} = (\gcd(i,j))^r\) ，则 \(\operatorname{det} A=\prod_{k=1}^n J_r(k)\) 。
证明：考虑 \(n\times n\) 的矩阵 \[ B=\left[b_{i,j}\right], \quad b_{i,j}=\left\{\begin{array}{ll} J_r(i) & \text { if } i \mid j \\ 0 & \text { otherwise } \end{array}, \quad C=\left[c_{i,j}\right], \quad c_{i,j}= \begin{cases}1 & \text { if } i \mid j \\ 0 & \text { otherwise }\end{cases}\right. \] 注意到 \(B,C\) 均为上三角矩阵，并且他们的对角线分别为 \(J_r(1),J_r(2),\cdots,J_r(n)\) 和 \(1,1,\cdots,1\) 。因此 \[ \operatorname{det} B=\prod_{k=1}^n J_r(k), \quad \operatorname{det} C=1 \] 那么根据引理 \[ \sum_{\ell=1}^n b_{\ell ,i} c_{\ell ,j}=\sum_{\ell|i, \ell| j} J_r(\ell) \cdot I=\sum_{\ell \mid \operatorname{gcd}(i, j)} J_r(\ell)=(\operatorname{gcd}(i, j))^r=a_{i,j} \] 所以 \(A=B^{\mathrm{T}} C\) ，由此可得 \[ \operatorname{det} A=\operatorname{det} B^T \operatorname{det} C=\operatorname{det} B \operatorname{det} C=\prod_{k=1}^n J_r(k) \] 证毕。
如果你想进一步了解 Smith-type determinants，可以阅读这篇论文
练习1
用定理证明 \[ \left|\begin{array}{cccc} 1 & 1 & 1 & 1 \\ 1 & \sqrt{2} & 1 & \sqrt{2} \\ 1 & 1 & \sqrt{3} & 1 \\ 1 & \sqrt{2} & 1 & 2 \end{array}\right|=(3 \sqrt{2}-4)(\sqrt{3}-1) \]
练习2
证明 \[ \left|\begin{array}{ccccc} \operatorname{gcd}\left(x_1, x_1\right) & \operatorname{gcd}\left(x_1, x_2\right) & \operatorname{gcd}\left(x_1, x_3\right) & \ldots & \operatorname{gcd}\left(x_1, x_n\right) \\ \operatorname{gcd}\left(x_2, x_1\right) & \operatorname{gcd}\left(x_2, x_2\right) & \operatorname{gcd}\left(x_2, x_3\right) & \ldots & \operatorname{gcd}\left(x_2, x_n\right) \\ \operatorname{gcd}\left(x_3, x_1\right) & \operatorname{gcd}\left(x_3, x_2\right) & \operatorname{gcd}\left(x_3, x_3\right) & \ldots & \operatorname{gcd}\left(x_3, x_n\right) \\ \vdots & \vdots & \vdots & & \vdots \\ \operatorname{gcd}\left(x_n, x_1\right) & \operatorname{gcd}\left(x_n, x_2\right) & \operatorname{gcd}\left(x_n, x_3\right) & \ldots & \operatorname{gcd}\left(x_n, x_n\right) \end{array}\right|=\varphi\left(x_1\right) \varphi\left(x_2\right) \cdots \varphi\left(x_n\right) \] 其实就是这道题 SP4195 MSE08H - GCD Determinant
参考文献：
[1] https://zh.wikipedia.org/zh-hans/行列式
题外话：
第一次翻译英文的数学文章，但愿没翻译错。
