GCD matrix explained
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 .
Definition
| - | | | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | | + | COLSPAN=10 ALIGN=CENTER | GCD matrix of (1,2,3,...,10) | |
Let
be a list of positive integers. Then the
matrix
having the
greatest common divisor
as its
entry is referred to as the GCD matrix on
.The LCM matrix
is defined analogously.
The study of GCD type matrices originates from who evaluated the determinant of certain GCD and LCM matrices. Smith showed among others that the determinant of the
matrix
is
, where
is
Euler's totient function.
Bourque–Ligh conjecture
conjectured that the LCM matrix on a GCD-closed set
is nonsingular. This conjecture was shown to be false by and subsequently by . A lattice-theoretic approach is provided by .
The counterexample presented in is
S=\{1,2,3,4,5,6,10,45,180\}
and that in 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 .
Divisibility
Let
be a factor closed set. Then the GCD matrix
divides the LCM matrix
in the ring of
matrices over the integers, that is there is an integral matrix
such that
, see . Since the matrices
and
are symmetric, we have
. 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.
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
norm of the GCD and LCM matrix on
.
Given
, the
norm of an
matrix
is defined as
\VertA\Vertp
=\left(\sum
|aij|p\right)1/p.
Let
. If
, then
\Vert(S)\Vertp=C
n1+(1/p)+O((n(1/p)-pEp(n)),
where
| C | |
| | p:= | 2\zeta(p)-\zeta(p+1) | | (p+1)\zeta(p+1) |
|
and
for
and
. Further, if
, then
\Vert[S]\Vertp=D
n2+(2/p)+O((n(2/p)+1(logn)2/3(loglogn)4/3),
where
| D | |
| | p:= | \zeta(p+2) | | (p+1)2\zeta(p) |
|
.
Factorizations
Let
be an arithmetical function, and let
be a set of distinct positive integers. Then the matrix
is referred to as the GCD matrix on
associated with
.The LCM matrix
on
associated with
is defined analogously. One may also use the notations
and
.
Let
be a GCD-closed set. Then
where
is the
matrix defined by
eij=
\begin{cases}
1&ifxj\midxi,\\
0&otherwise
\end{cases}
and
is the
diagonal matrix, whose diagonal elements are
\deltai=\sum
| |
| d\midxi\atop{d\nmidxt\atopxt<xi |
}(f\star\mu)(d).Here
is the
Dirichlet convolution and
is the
Möbius function.
Further, if
is a
multiplicative function and always nonzero,then
where
and
are the
diagonal matrices, whose diagonal elements are
and
| \prime=\sum |
| \delta | |
| d\vertxi\atop{d\nmidxt\atopxt<xi |
}(\frac\star\mu)(d).If
is factor-closed, then
and
.
References
[1] [2]
[3]
[4]
[5]
[6]
Notes and References
- Bourque . K. . Ligh . S. . On GCD and LCM matrices . Linear Algebra and Its Applications . 1992 . 174 . 65–74 . 10.1016/0024-3795(92)90042-9 . free .
- Haukkanen . P. . Toth . L. . Inertia, positive definiteness and ℓp norm of GCD and LCM matrices and their unitary analogs . Linear Algebra and Its Applications . 2018 . 558 . 1–24 . 10.1016/j.laa.2018.08.022 . free.
- Haukkanen . P. . Wang . J. . Sillanpää . J. . On Smith's determinant . Linear Algebra and Its Applications . 1997 . 258 . 251–269 . 10.1016/S0024-3795(96)00192-9 . free.
- Hong . S. . On the Bourque–Ligh conjecture of least common multiple matrices . Journal of Algebra . 1999 . 218 . 216–228 . 10.1006/jabr.1998.7844 . free.
- Korkee . I. . Mattila . M. . Haukkanen . P. . A lattice-theoretic approach to the Bourque–Ligh conjecture . Linear and Multilinear Algebra . 2019 . 67 . 12 . 2471–2487 . 10.1080/03081087.2018.1494695 . 117112282 . 1403.5428 .
- Smith . H. J. S. . On the value of a certain arithmetical determinant . Proceedings of the London Mathematical Society . 1875 . 1 . 208–213 . 10.1112/plms/s1-7.1.208.