// Workers AI · dad joke modeWhat did the GCD matrix say? "I've got a common bond.

Heatmap of GCD Matrix

In mathematics, a greatest common divisor matrix (sometimes abbreviated as GCD matrix) is a matrix that may also be referred to as Smith's matrix. The study was initiated by H.J.S. Smith (1875). A new inspiration was begun from the paper of Bourque & Ligh (1992). This led to intensive investigations on singularity and divisibility of GCD type matrices. A brief review of papers on GCD type matrices before that time is presented in Haukkanen, Wang & Sillanpää (1997).

Definition

1	1	1	1	1	1	1	1	1	1
1	2	1	2	1	2	1	2	1	2
1	1	3	1	1	3	1	1	3	1
1	2	1	4	1	2	1	4	1	2
1	1	1	1	5	1	1	1	1	5
1	2	3	2	1	6	1	2	3	2
1	1	1	1	1	1	7	1	1	1
1	2	1	4	1	2	1	8	1	2
1	1	3	1	1	3	1	1	9	1
1	2	1	2	5	2	1	2	1	10
GCD matrix of (1,2,3,...,10)

Let $S=(x_{1},x_{2},\ldots ,x_{n})$ be a list of positive integers. Then the $n\times n$ matrix $(S)$ having the greatest common divisor $\gcd(x_{i},x_{j})$ as its $ij$ entry is referred to as the GCD matrix on $S$.The LCM matrix $[S]$ is defined analogously.

The study of GCD type matrices originates from Smith (1875) who evaluated the determinant of certain GCD and LCM matrices. Smith showed among others that the determinant of the $n\times n$ matrix $(\gcd(i,j))$ is $\phi (1)\phi (2)\cdots \phi (n)$, where $\phi$ is Euler's totient function.

Bourque–Ligh conjecture

Bourque & Ligh (1992) conjectured that the LCM matrix on a GCD-closed set $S$ is nonsingular. This conjecture was shown to be false by Haukkanen, Wang & Sillanpää (1997) and subsequently by Hong (1999). A lattice-theoretic approach is provided by Korkee, Mattila & Haukkanen (2019).

The counterexample presented in Haukkanen, Wang & Sillanpää (1997) is $S=\{1,2,3,4,5,6,10,45,180\}$ and that in Hong (1999) is $S=\{1,2,3,5,36,230,825,227700\}.$ A counterexample consisting of odd numbers is $S=\{1,3,5,7,195,291,1407,4025,1020180525\}$. Its Hasse diagram is presented on the right below.

The cube-type structures of these sets with respect to the divisibility relation are explained in Korkee, Mattila & Haukkanen (2019).

The Hasse diagram of an odd GCD closed set whose LCM matrix is singular

Divisibility

Let $S=(x_{1},x_{2},\ldots ,x_{n})$ be a factor closed set. Then the GCD matrix $(S)$ divides the LCM matrix $[S]$ in the ring of $n\times n$ matrices over the integers, that is there is an integral matrix $B$ such that $[S]=B(S)$, see Bourque & Ligh (1992). Since the matrices $(S)$ and $[S]$ are symmetric, we have $[S]=(S)B^{T}$. Thus, divisibility from the right coincides with that from the left. We may thus use the term divisibility.

There is in the literature a large number of generalizations and analogues of this basic divisibility result.

Generalized eigenvalues

For $S=\{1,2,\ldots ,n\}$, the generalized eigenvalues of the LCM matrix $[S]$ with respect to the corresponding GCD matrix $(S)$ are the values $\lambda$ satisfying

$\det([S]-\lambda (S))=0.$

Merikoski, Haukkanen, Sasaki, and Tossavainen compared this problem with the analogous generalized eigenvalue problem for MAX and MIN matrices. They determined the MAX–MIN generalized eigenvalues for every $n\geq 1$ and showed that the corresponding LCM–GCD result holds for $n\leq 4$, but fails in general for $n>4$.

Matrix norms

Some results on matrix norms of GCD type matrices are presented in the literature. Two basic results concern the asymptotic behaviour of the $\ell _{p}$ norm of the GCD and LCM matrix on $S=\{1,2,\dots ,n\}$.

Given $p\in \mathbb {N} ^{+}$, the $\ell _{p}$ norm of an $n\times n$ matrix $A$ is defined as

$\Vert A\Vert _{p}=\left(\sum _{i=1}^{n}\sum _{j=1}^{n}|a_{ij}|^{p}\right)^{1/p}.$

Let $S=\{1,2,\dots ,n\}$. If $p\geq 2$, then

$\Vert (S)\Vert _{p}=C_{p}^{1/p}n^{1+(1/p)}+O((n^{(1/p)-p}E_{p}(n)),$

where

$C_{p}:={\frac {2\zeta (p)-\zeta (p+1)}{(p+1)\zeta (p+1)}}$

and $E_{p}(x)=x^{p}$ for $p>2$ and $E_{2}(x)=x^{2}\log x$. Further, if $p\geq 1$, then

$\Vert [S]\Vert _{p}=D_{p}^{1/p}n^{2+(2/p)}+O((n^{(2/p)+1}(\log n)^{2/3}(\log \log n)^{4/3}),$

where

$D_{p}:={\frac {\zeta (p+2)}{(p+1)^{2}\zeta (p)}}.$

Factorizations

Let $f$ be an arithmetical function, and let $S=(x_{1},x_{2},\ldots ,x_{n})$ be a set of distinct positive integers. Then the matrix $(S)_{f}=(f(\gcd(x_{i},x_{j}))$ is referred to as the GCD matrix on $S$ associated with $f$. The LCM matrix $[S]_{f}$ on $S$ associated with $f$ is defined analogously. One may also use the notations $(S)_{f}=f(S)$ and $[S]_{f}=f[S]$.

Let $S$ be a GCD-closed set. Then

$(S)_{f}=E\Delta E^{T},$

where $E$ is the $n\times n$ matrix defined by

$e_{ij}={\begin{cases}1&{\mbox{if }}x_{j}\,\mid \,x_{i},\\0&{\mbox{otherwise}}\end{cases}}$

and $\Delta$ is the $n\times n$ diagonal matrix, whose diagonal elements are

$\delta _{i}=\sum _{d\mid x_{i} \atop {d\nmid x_{t} \atop x_{t}<x_{i}}}(f\star \mu )(d).$

Here $\star$ is the Dirichlet convolution and $\mu$ is the Möbius function.

Further, if $f$ is a multiplicative function and always nonzero, then

$[S]_{f}=\Lambda E\Delta ^{\prime }E^{T}\Lambda ,$

where $\Lambda$ and $\Delta '$ are the $n\times n$ diagonal matrices, whose diagonal elements are $\lambda _{i}=f(x_{i})$ and

$\delta _{i}^{\prime }=\sum _{d\vert x_{i} \atop {d\nmid x_{t} \atop x_{t}<x_{i}}}({\frac {1}{f}}\star \mu )(d).$

If $S$ is factor-closed, then $\delta _{i}=(f\star \mu )(x_{i})$ and $\delta _{i}^{\prime }=({\frac {1}{f}}\star \mu )(x_{i})$.