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/行列式

---

题外话：

第一次翻译英文的数学文章，但愿没翻译错。