Jump to content

GCD matrix

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by David Eppstein (talk | contribs) at 06:07, 8 October 2022 (rm overbroad cat). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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

GCD matrix example

Let be a set 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 HJS 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.

Conjectures

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

References

K. Bourque; S. Ligh (1992). "On GCD and LCM matrices". Linear Algebra and Its Applications. 174: 65–74. doi:10.1016/0024-3795(92)90042-9.

P. Haukkanen; J. Wang; J. Sillanpää (1997). "On Smith's determinant". Linear Algebra and Its Applications. 258: 251–269. doi:10.1016/S0024-3795(96)00192-9.

S. Hong (1999). "On the Bourque–Ligh conjecture of least common multiple matrices". Journal of Algebra. 218: 216–228. doi:10.1006/jabr.1998.7844.

I. Korkee; M. Mattila; P. Haukkanen (2019). "A lattice-theoretic approach to the Bourque–Ligh conjecture". Linear and Multilinear Algebra. 67 (12): 2471–2487. doi:10.1080/03081087.2018.1494695. S2CID 117112282.

H. J. S. Smith (1875). "On the value of a certain arithmetical determinant". Proceedings of the London Mathematical Society. 1: 208–213.