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 [math]\displaystyle{ S=(x_1, x_2,\ldots, x_n) }[/math] be a list of positive integers. Then the [math]\displaystyle{ n\times n }[/math] matrix [math]\displaystyle{ (S) }[/math] having the greatest common divisor [math]\displaystyle{ \gcd(x_i, x_j) }[/math] as its [math]\displaystyle{ ij }[/math] entry is referred to as the GCD matrix on [math]\displaystyle{ S }[/math].The LCM matrix [math]\displaystyle{ [S] }[/math] 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 [math]\displaystyle{ n\times n }[/math] matrix [math]\displaystyle{ (\gcd(i,j)) }[/math] is [math]\displaystyle{ \phi(1)\phi(2)\cdots\phi(n) }[/math], where [math]\displaystyle{ \phi }[/math] is Euler's totient function.[3]
Bourque–Ligh conjecture
(Bourque Ligh) conjectured that the LCM matrix on a GCD-closed set [math]\displaystyle{ S }[/math] is nonsingular.[1] This conjecture was shown to be false by (Haukkanen Wang) and subsequently by (Hong 1999).[4][2] A lattice-theoretic approach is provided by (Korkee Mattila).[5]
References
- ↑ 1.0 1.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.0 2.1 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. https://zenodo.org/record/1709912.
- ↑ 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. doi:10.1080/03081087.2018.1494695. https://trepo.tuni.fi/handle/10024/117430.
![]() | Original source: https://en.wikipedia.org/wiki/GCD matrix.
Read more |