GCD matrix

In mathematics, a greatest common divisor matrix (sometimes abbreviated as GCD matrix) is a matrix.

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 ${\displaystyle S=(x_{1},x_{2},\ldots ,x_{n})}$  be a list of positive integers. Then the ${\displaystyle n\times n}$  matrix ${\displaystyle (S)}$  having the greatest common divisor ${\displaystyle \gcd(x_{i},x_{j})}$  as its ${\displaystyle ij}$  entry is referred to as the GCD matrix on ${\displaystyle S}$ .The LCM matrix ${\displaystyle [S]}$  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 ${\displaystyle n\times n}$  matrix ${\displaystyle (\gcd(i,j))}$  is ${\displaystyle \phi (1)\phi (2)\cdots \phi (n)}$ , where ${\displaystyle \phi }$  is Euler's totient function.^[3]

Bourque–Ligh conjecture

Bourque & Ligh (1992) conjectured that the LCM matrix on a GCD-closed set ${\displaystyle S}$  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 ${\displaystyle S=\{1,2,3,4,5,6,10,45,180\}}$  and that in Hong (1999) is ${\displaystyle S=\{1,2,3,5,36,230,825,227700\}.}$  The cube-type structures of these sets with respect to the divisibility relation are explained in Korkee, Mattila & Haukkanen (2019).

Divisibility

Let ${\displaystyle S=(x_{1},x_{2},\ldots ,x_{n})}$  be a factor closed set. Then the GCD matrix ${\displaystyle (S)}$  divides the LCM matrix ${\displaystyle [S]}$  in the ring of ${\displaystyle n\times n}$  matrices over the integers, that is there is an integral matrix ${\displaystyle B}$  such that ${\displaystyle [S]=B(S)}$ , see Bourque & Ligh (1992). Since the matrices ${\displaystyle (S)}$  and ${\displaystyle [S]}$  are symmetric, we have ${\displaystyle [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.

References

1. 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. 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.