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

edit
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   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.[1][2]

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   matrix   is  , where   is Euler's totient function.[3]

Bourque–Ligh conjecture

edit

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

The counterexample presented in Haukkanen, Wang & Sillanpää (1997) is   and that in Hong (1999) is   A counterexample consisting of odd numbers is  . 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

edit

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 Bourque & Ligh (1992). 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

edit

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  . [6]


Given  , the   norm of an   matrix   is defined as

 

Let  . If  , then

 

where

 

and   for   and  . Further, if  , then

 

where

 

Factorizations

edit

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

 

and   is the   diagonal matrix, whose diagonal elements are

 

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

 

If   is factor-closed, then   and  . [6]

References

edit
  1. ^ a b Bourque, K.; Ligh, S. (1992). "On GCD and LCM matrices". Linear Algebra and Its Applications. 174: 65–74. doi:10.1016/0024-3795(92)90042-9.
  2. ^ a b Hong, S. (1999). "On the Bourque–Ligh conjecture of least common multiple matrices". Journal of Algebra. 218: 216–228. doi:10.1006/jabr.1998.7844.
  3. ^ Smith, H. J. S. (1875). "On the value of a certain arithmetical determinant". Proceedings of the London Mathematical Society. 1: 208–213. doi:10.1112/plms/s1-7.1.208.
  4. ^ Haukkanen, P.; Wang, J.; Sillanpää, J. (1997). "On Smith's determinant". Linear Algebra and Its Applications. 258: 251–269. doi:10.1016/S0024-3795(96)00192-9.
  5. ^ Korkee, I.; Mattila, M.; Haukkanen, P. (2019). "A lattice-theoretic approach to the Bourque–Ligh conjecture". Linear and Multilinear Algebra. 67 (12): 2471–2487. arXiv:1403.5428. doi:10.1080/03081087.2018.1494695. S2CID 117112282.
  6. ^ a b Haukkanen, P.; Toth, L. (2018). "Inertia, positive definiteness and ℓp norm of GCD and LCM matrices and their unitary analogs". Linear Algebra and Its Applications. 558: 1–24. doi:10.1016/j.laa.2018.08.022.