GCD matrix

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 Template:Harvtxt.

Definition

Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color
Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color
Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color
Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color
Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color
Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color
Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color
Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color
Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color
Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color	Template:Color
GCD matrix of (1,2,3,...,10)

Let $S=(x_1,x_2,\dots ,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 least common multiple (LCM) matrix $[S]$ is defined analogously.Template:R

The study of GCD type matrices originates from Template:Harvtxt 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 $\varphi (1)\varphi (2)\cdots \varphi (n)$, where $\varphi$ is Euler's totient function.Template:R

Bourque–Ligh conjecture

Template:Harvtxt conjectured that the LCM matrix on a GCD-closed set $S$ is nonsingular.Template:R This conjecture was shown to be false by Template:Harvtxt and subsequently by Template:Harvtxt.Template:R A lattice-theoretic approach is provided by Template:Harvtxt.Template:R

The counterexample presented in Template:Harvtxt is $S=\{1,2,3,4,5,6,10,45,180\}$ and that in Template:Harvtxt 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 Template:Harvtxt.

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

Divisibility

Let $S=(x_1,x_2,\dots ,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 Template:Harvtxt. 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,\dots ,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\ge 1$ and showed that the corresponding LCM–GCD result holds for $n\le 4$, but fails in general for $n>4$.Template:R

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\}$. Template:R

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

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

Let $S=\{1,2,\dots ,n\}$. If $p\ge 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\ge 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,\dots ,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\mathrm{\Delta }{E}^T,$

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

$e_{ij}=\{\begin{array}{cc}1& \text{if }{x}_j\mid x_i,\\ 0& \text{otherwise}\end{array}$

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

${\delta }_i=\sum _{\genfrac{}{}{0ex}{}{d\mid x_i}{\genfrac{}{}{0ex}{}{d\nmid x_t}{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=\mathrm{\Lambda }E{\mathrm{\Delta }}^{\prime }{E}^T\mathrm{\Lambda },$

where $\mathrm{\Lambda }$ and ${\mathrm{\Delta }}^{\prime }$ are the $n\times n$ diagonal matrices, whose diagonal elements are ${\lambda }_i=f(x_i)$ and

${{\delta }_i}^{\prime }=\sum _{\genfrac{}{}{0ex}{}{d|x_i}{\genfrac{}{}{0ex}{}{d\nmid x_t}{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)$. Template:R