GCD matrix

class=wikitable style="float:right"
{{color|#c0c0c0|1}}	{{color|#c0c0c0|1}}	{{color|#c0c0c0|1}}	{{color|#c0c0c0|1}}	{{color|#c0c0c0|1}}	{{color|#c0c0c0|1}}	{{color|#c0c0c0|1}}	{{color|#c0c0c0|1}}	{{color|#c0c0c0|1}}	{{color|#c0c0c0| 1}}
{{color|#c0c0c0|1}}	{{color|#c00000|2}}	{{color|#c0c0c0|1}}	{{color|#c00000|2}}	{{color|#c0c0c0|1}}	{{color|#c00000|2}}	{{color|#c0c0c0|1}}	{{color|#c00000|2}}	{{color|#c0c0c0|1}}	{{color|#c00000| 2}}
{{color|#c0c0c0|1}}	{{color|#c0c0c0|1}}	{{color|#0000c0|3}}	{{color|#c0c0c0|1}}	{{color|#c0c0c0|1}}	{{color|#0000c0|3}}	{{color|#c0c0c0|1}}	{{color|#c0c0c0|1}}	{{color|#0000c0|3}}	{{color|#c0c0c0| 1}}
{{color|#c0c0c0|1}}	{{color|#c00000|2}}	{{color|#c0c0c0|1}}	{{color|#c00000|4}}	{{color|#c0c0c0|1}}	{{color|#c00000|2}}	{{color|#c0c0c0|1}}	{{color|#c00000|4}}	{{color|#c0c0c0|1}}	{{color|#c00000| 2}}
{{color|#c0c0c0|1}}	{{color|#c0c0c0|1}}	{{color|#c0c0c0|1}}	{{color|#c0c0c0|1}}	{{color|#00c000|5}}	{{color|#c0c0c0|1}}	{{color|#c0c0c0|1}}	{{color|#c0c0c0|1}}	{{color|#c0c0c0|1}}	{{color|#00c000| 5}}
{{color|#c0c0c0|1}}	{{color|#c00000|2}}	{{color|#0000c0|3}}	{{color|#c00000|2}}	{{color|#c0c0c0|1}}	{{color|#c000c0|6}}	{{color|#c0c0c0|1}}	{{color|#c00000|2}}	{{color|#0000c0|3}}	{{color|#c00000| 2}}
{{color|#c0c0c0|1}}	{{color|#c0c0c0|1}}	{{color|#c0c0c0|1}}	{{color|#c0c0c0|1}}	{{color|#c0c0c0|1}}	{{color|#c0c0c0|1}}	{{color|#000000|7}}	{{color|#c0c0c0|1}}	{{color|#c0c0c0|1}}	{{color|#c0c0c0| 1}}
{{color|#c0c0c0|1}}	{{color|#c00000|2}}	{{color|#c0c0c0|1}}	{{color|#c00000|4}}	{{color|#c0c0c0|1}}	{{color|#c00000|2}}	{{color|#c0c0c0|1}}	{{color|#c00000|8}}	{{color|#c0c0c0|1}}	{{color|#c00000| 2}}
{{color|#c0c0c0|1}}	{{color|#c0c0c0|1}}	{{color|#0000c0|3}}	{{color|#c0c0c0|1}}	{{color|#c0c0c0|1}}	{{color|#0000c0|3}}	{{color|#c0c0c0|1}}	{{color|#c0c0c0|1}}	{{color|#0000c0|9}}	{{color|#c0c0c0| 1}}
{{color|#c0c0c0|1}}	{{color|#c00000|2}}	{{color|#c0c0c0|1}}	{{color|#c00000|2}}	{{color|#00c000|5}}	{{color|#c00000|2}}	{{color|#c0c0c0|1}}	{{color|#c00000|2}}	{{color|#c0c0c0|1}}	{{color|#c0c000|10}} |+ | COLSPAN=10 ALIGN=CENTER | GCD matrix of (1,2,3,...,10)

Let $S=(x\_1,\; x\_2,\backslash ldots,\; x\_n)$ be a list of positive integers. Then the $n\backslash times\; n$ matrix $(S)$ having the greatest common divisor $\backslash 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.{{r|borque-ligh|hong}}

The study of GCD type matrices originates from {{harvtxt|Smith|1875}} who evaluated the determinant of certain GCD and LCM matrices.

Smith showed among others that the determinant of the $n\backslash times\; n$ matrix $(\backslash gcd(i,j))$ is $\backslash phi(1)\backslash phi(2)\backslash cdots\backslash phi(n)$, where $\backslash phi$ is Euler's totient function.{{r|smith}}

{{harvtxt|Bourque|Ligh|1992}} conjectured that the LCM matrix on a GCD-closed set $S$ is nonsingular.{{r|borque-ligh}} This conjecture was shown to be false by {{harvtxt|Haukkanen|Wang|Sillanpää|1997}} and subsequently by {{harvtxt|Hong|1999}}.{{r|haukkanen|hong}} A lattice-theoretic approach is provided by {{harvtxt|Korkee|Mattila|Haukkanen|2019}}.{{r|korkee}}

The counterexample presented in {{harvtxt|Haukkanen|Wang|Sillanpää|1997}} is $S\; =\; \backslash \{1,2,3,4,5,6,\; 10,45,180\backslash \}$ and that in {{harvtxt|Hong|1999}} is

$S=\backslash \{1,2,3,5,36,230,825,227700\backslash \}.$ A counterexample consisting of odd numbers is $S\; =\; \backslash \{1,\; 3,\; 5,\; 7,\; 195,\; 291,\; 1407,\; 4025,\; 1020180525\; \backslash \}$. 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 {{harvtxt|Korkee|Mattila|Haukkanen|2019}}. File:Counterexample.png

Let $S=(x\_1,\; x\_2,\backslash ldots,\; x\_n)$ be a factor closed set.

Then the GCD matrix $(S)$ divides the LCM matrix $[S]$ in the ring of $n\backslash times\; n$ matrices over the integers, that is there is an integral matrix $B$ such that $[S]=B(S)$,

see {{harvtxt|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.

Some results on matrix norms of GCD type matrices are presented in the literature.

Two basic results concern the asymptotic behaviour of the $\backslash ell\_p$ norm of

the GCD and LCM matrix on $S=\backslash \{1,\; 2,\backslash dots,\; n\backslash \}$. {{r|haukkanen-toth}}

Given $p\backslash in\backslash N^+$, the $\backslash ell\_p$ norm of an $n\backslash 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=\backslash \{1,\; 2,\backslash dots,\; n\backslash \}$. If $p\backslash 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\backslash log\; x$.

Further, if $p\backslash 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)}.

Let $f$ be an arithmetical function, and let $S=(x\_1,\; x\_2,\backslash ldots,\; x\_n)$ be a set of distinct positive integers. Then the matrix $(S)\_f=(f(\backslash 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\backslash times\; n$ matrix defined by

:$$

e_{ij}=

\begin{cases}

1 & \mbox{if } x_j\,\mid\, x_i,\\

0 & \mbox{otherwise}

\end{cases}

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

:$$

\delta_i=\sum_{d\mid x_i\atop {d\nmid x_t\atop x_t

(f\star\mu)(d).

Here $\backslash star$ is the Dirichlet convolution and $\backslash 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 $\backslash Lambda$ and $\backslash Delta\text{'}$ are the $n\backslash times\; n$ diagonal matrices, whose diagonal elements are

$\backslash lambda\_i=f(x\_i)$

and

:$$

\delta_i^\prime=\sum_{d\vert x_i\atop {d\nmid x_t\atop x_t

(\frac{1}{f}\star\mu)(d).

If $S$ is factor-closed, then $\backslash delta\_i=(f\backslash star\backslash mu)(x\_i)$ and

$\backslash delta\_i^\backslash prime=(\backslash frac\{1\}\{f\}\backslash star\backslash mu)(x\_i)$. {{r|haukkanen-toth}}

{{reflist|refs =

{{cite journal

|last1 = Bourque |first1 = K.

|last2 = Ligh |first2 = S.

|title = On GCD and LCM matrices

|journal = Linear Algebra and Its Applications

|year = 1992

|volume = 174

|pages = 65–74

|doi = 10.1016/0024-3795(92)90042-9

|doi-access = free }}

{{cite journal

|last1 = Haukkanen |first1 = P.

|last2 = Toth |first2 = L.

|title = Inertia, positive definiteness and ℓp norm of GCD and LCM matrices and their unitary analogs

|journal = Linear Algebra and Its Applications

|year = 2018

|volume = 558

|pages = 1–24

|doi = 10.1016/j.laa.2018.08.022

|doi-access = free|url= https://trepo.tuni.fi/bitstream/10024/104222/1/Inertia_positive_definiteness_2018.pdf

}}

{{cite journal

|last1 = Haukkanen |first1 = P.

|last2 = Wang |first2 = J.

|last3 = Sillanpää |first3 = J.

|title = On Smith's determinant

|journal = Linear Algebra and Its Applications

|year = 1997

|volume = 258

|pages = 251–269

|doi = 10.1016/S0024-3795(96)00192-9

|doi-access = free}}

{{cite journal

|last = Hong |first = S.

|title = On the Bourque–Ligh conjecture of least common multiple matrices

|journal = Journal of Algebra

|year = 1999

|volume = 218

|pages = 216–228

|doi = 10.1006/jabr.1998.7844

|doi-access = free}}

{{cite journal

|last1 = Korkee |first1 = I.

|last2 = Mattila |first2 = M.

|last3 = Haukkanen |first3 = P.

|title = A lattice-theoretic approach to the Bourque–Ligh conjecture

|journal = Linear and Multilinear Algebra

|year = 2019

|volume = 67

|issue = 12

|pages = 2471–2487

|doi = 10.1080/03081087.2018.1494695

|s2cid = 117112282

|url = https://trepo.tuni.fi/handle/10024/117430|arxiv= 1403.5428

}}

{{cite journal

|last = Smith |first = H. J. S.

|title = On the value of a certain arithmetical determinant

|journal = Proceedings of the London Mathematical Society

|year = 1875

|volume = 1

|pages = 208–213

|doi = 10.1112/plms/s1-7.1.208|url = https://zenodo.org/record/1709912

}}

}}

Category:Matrix theory

Category:Number theory