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.
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]
![{\displaystyle [S]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/292bbb82029aa583c5d2ac5fa1d7e4fedf537d8b)
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).
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.
![{\displaystyle [S]=B(S)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eccbe588e4c7cba6a9d50af72170ee94ef34b47d)
![{\displaystyle [S]=(S)B^{T}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/94b023779216115bac0f64b4b537fbe6120e3407)
There is in the literature a large number of generalizations and analogues of this basic divisibility result.
References edit
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.