Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
GCD matrix
open-in-new
<h2 id="definition">Definition</h2> <table><tbody><tr><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td> 1</td></tr><tr><td>1</td><td>2</td><td>1</td><td>2</td><td>1</td><td>2</td><td>1</td><td>2</td><td>1</td><td> 2</td></tr><tr><td>1</td><td>1</td><td>3</td><td>1</td><td>1</td><td>3</td><td>1</td><td>1</td><td>3</td><td> 1</td></tr><tr><td>1</td><td>2</td><td>1</td><td>4</td><td>1</td><td>2</td><td>1</td><td>4</td><td>1</td><td> 2</td></tr><tr><td>1</td><td>1</td><td>1</td><td>1</td><td>5</td><td>1</td><td>1</td><td>1</td><td>1</td><td> 5</td></tr><tr><td>1</td><td>2</td><td>3</td><td>2</td><td>1</td><td>6</td><td>1</td><td>2</td><td>3</td><td> 2</td></tr><tr><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>7</td><td>1</td><td>1</td><td> 1</td></tr><tr><td>1</td><td>2</td><td>1</td><td>4</td><td>1</td><td>2</td><td>1</td><td>8</td><td>1</td><td> 2</td></tr><tr><td>1</td><td>1</td><td>3</td><td>1</td><td>1</td><td>3</td><td>1</td><td>1</td><td>9</td><td> 1</td></tr><tr><td>1</td><td>2</td><td>1</td><td>2</td><td>5</td><td>2</td><td>1</td><td>2</td><td>1</td><td>10</td></tr></tbody><tbody><tr><td colspan="10">GCD matrix of (1,2,3,...,10)</td></tr></tbody></table> <p>Let S = ( x 1 , x 2 , … , x n ) {\displaystyle S=(x_{1},x_{2},\ldots ,x_{n})} be a list of positive integers. Then the n × n {\displaystyle n\times n} matrix ( S ) {\displaystyle (S)} having the <a href="/facts/Greatest_common_divisor/kNFvBuKl">greatest common divisor</a> gcd ( x i , x j ) {\displaystyle \gcd(x_{i},x_{j})} as its i j {\displaystyle ij} entry is referred to as the GCD matrix on S {\displaystyle S} .The LCM matrix [ S ] {\displaystyle [S]} is defined analogously.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a><a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> </p><p>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 n × n {\displaystyle n\times n} matrix ( gcd ( i , j ) ) {\displaystyle (\gcd(i,j))} is ϕ ( 1 ) ϕ ( 2 ) ⋯ ϕ ( n ) {\displaystyle \phi (1)\phi (2)\cdots \phi (n)} , where ϕ {\displaystyle \phi } is <a href="/facts/Euler%2527s_totient_function/mIQwXYzj">Euler's totient function</a>.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> </p> <h2 id="bourqueligh-conjecture">Bourque–Ligh conjecture</h2> <p>Bourque & Ligh (1992) conjectured that the LCM matrix on a GCD-closed set S {\displaystyle S} is nonsingular.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> This conjecture was shown to be false by Haukkanen, Wang & Sillanpää (1997) and subsequently by Hong (1999).<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a><a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> A lattice-theoretic approach is provided by Korkee, Mattila & Haukkanen (2019).<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> </p><p>The counterexample presented in Haukkanen, Wang & Sillanpää (1997) is S = { 1 , 2 , 3 , 4 , 5 , 6 , 10 , 45 , 180 } {\displaystyle S=\{1,2,3,4,5,6,10,45,180\}} and that in Hong (1999) is S = { 1 , 2 , 3 , 5 , 36 , 230 , 825 , 227700 } . {\displaystyle S=\{1,2,3,5,36,230,825,227700\}.} A counterexample consisting of odd numbers is S = { 1 , 3 , 5 , 7 , 195 , 291 , 1407 , 4025 , 1020180525 } {\displaystyle S=\{1,3,5,7,195,291,1407,4025,1020180525\}} . Its Hasse diagram is presented on the right below. </p><p> The cube-type structures of these sets with respect to the divisibility relation are explained in Korkee, Mattila & Haukkanen (2019). </p> <h2 id="divisibility">Divisibility</h2> <p>Let S = ( x 1 , x 2 , … , x n ) {\displaystyle S=(x_{1},x_{2},\ldots ,x_{n})} be a factor closed set. Then the GCD matrix ( S ) {\displaystyle (S)} divides the LCM matrix [ S ] {\displaystyle [S]} in the ring of n × n {\displaystyle n\times n} matrices over the integers, that is there is an integral matrix B {\displaystyle B} such that [ S ] = B ( S ) {\displaystyle [S]=B(S)} , see Bourque & Ligh (1992). Since the matrices ( S ) {\displaystyle (S)} and [ S ] {\displaystyle [S]} are symmetric, we have [ S ] = ( S ) B T {\displaystyle [S]=(S)B^{T}} . Thus, divisibility from the right coincides with that from the left. We may thus use the term divisibility. </p><p>There is in the literature a large number of generalizations and analogues of this basic divisibility result. </p> <h2 id="matrix-norms">Matrix norms</h2> <p>Some results on matrix norms of GCD type matrices are presented in the literature. Two basic results concern the asymptotic behaviour of the ℓ p {\displaystyle \ell _{p}} norm of the GCD and LCM matrix on S = { 1 , 2 , … , n } {\displaystyle S=\{1,2,\dots ,n\}} . <a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> </p><p> Given p ∈ N + {\displaystyle p\in \mathbb {N} ^{+}} , the ℓ p {\displaystyle \ell _{p}} norm of an n × n {\displaystyle n\times n} matrix A {\displaystyle A} is defined as </p> ‖ A ‖ p = ( ∑ i = 1 n ∑ j = 1 n | a i j | p ) 1 / p . {\displaystyle \Vert A\Vert _{p}=\left(\sum _{i=1}^{n}\sum _{j=1}^{n}|a_{ij}|^{p}\right)^{1/p}.} <p>Let S = { 1 , 2 , … , n } {\displaystyle S=\{1,2,\dots ,n\}} . If p ≥ 2 {\displaystyle p\geq 2} , then </p> ‖ ( S ) ‖ p = C p 1 / p n 1 + ( 1 / p ) + O ( ( n ( 1 / p ) − p E p ( n ) ) , {\displaystyle \Vert (S)\Vert _{p}=C_{p}^{1/p}n^{1+(1/p)}+O((n^{(1/p)-p}E_{p}(n)),} <p>where </p> C p := 2 ζ ( p ) − ζ ( p + 1 ) ( p + 1 ) ζ ( p + 1 ) {\displaystyle C_{p}:={\frac {2\zeta (p)-\zeta (p+1)}{(p+1)\zeta (p+1)}}} <p>and E p ( x ) = x p {\displaystyle E_{p}(x)=x^{p}} for p > 2 {\displaystyle p>2} and E 2 ( x ) = x 2 log x {\displaystyle E_{2}(x)=x^{2}\log x} . Further, if p ≥ 1 {\displaystyle p\geq 1} , then </p> ‖ [ S ] ‖ p = D p 1 / p n 2 + ( 2 / p ) + O ( ( n ( 2 / p ) + 1 ( log n ) 2 / 3 ( log log n ) 4 / 3 ) , {\displaystyle \Vert [S]\Vert _{p}=D_{p}^{1/p}n^{2+(2/p)}+O((n^{(2/p)+1}(\log n)^{2/3}(\log \log n)^{4/3}),} <p>where </p> D p := ζ ( p + 2 ) ( p + 1 ) 2 ζ ( p ) . {\displaystyle D_{p}:={\frac {\zeta (p+2)}{(p+1)^{2}\zeta (p)}}.} <h2 id="factorizations">Factorizations</h2> <p>Let f {\displaystyle f} be an arithmetical function, and let S = ( x 1 , x 2 , … , x n ) {\displaystyle S=(x_{1},x_{2},\ldots ,x_{n})} be a set of distinct positive integers. Then the matrix ( S ) f = ( f ( gcd ( x i , x j ) ) {\displaystyle (S)_{f}=(f(\gcd(x_{i},x_{j}))} is referred to as the GCD matrix on S {\displaystyle S} associated with f {\displaystyle f} . The LCM matrix [ S ] f {\displaystyle [S]_{f}} on S {\displaystyle S} associated with f {\displaystyle f} is defined analogously. One may also use the notations ( S ) f = f ( S ) {\displaystyle (S)_{f}=f(S)} and [ S ] f = f [ S ] {\displaystyle [S]_{f}=f[S]} . </p><p>Let S {\displaystyle S} be a GCD-closed set. Then </p> ( S ) f = E Δ E T , {\displaystyle (S)_{f}=E\Delta E^{T},} <p>where E {\displaystyle E} is the n × n {\displaystyle n\times n} matrix defined by </p> e i j = { 1 if x j ∣ x i , 0 otherwise {\displaystyle e_{ij}={\begin{cases}1&{\mbox{if }}x_{j}\,\mid \,x_{i},\\0&{\mbox{otherwise}}\end{cases}}} <p>and Δ {\displaystyle \Delta } is the n × n {\displaystyle n\times n} diagonal matrix, whose diagonal elements are </p> δ i = ∑ d ∣ x i d ∤ x t x t < x i ( f ⋆ μ ) ( d ) . {\displaystyle \delta _{i}=\sum _{d\mid x_{i} \atop {d\nmid x_{t} \atop x_{t}<x_{i}}}(f\star \mu )(d).} <p>Here ⋆ {\displaystyle \star } is the Dirichlet convolution and μ {\displaystyle \mu } is the Möbius function. </p><p>Further, if f {\displaystyle f} is a multiplicative function and always nonzero, then </p> [ S ] f = Λ E Δ ′ E T Λ , {\displaystyle [S]_{f}=\Lambda E\Delta ^{\prime }E^{T}\Lambda ,} <p>where Λ {\displaystyle \Lambda } and Δ ′ {\displaystyle \Delta '} are the n × n {\displaystyle n\times n} diagonal matrices, whose diagonal elements are λ i = f ( x i ) {\displaystyle \lambda _{i}=f(x_{i})} and </p> δ i ′ = ∑ d | x i d ∤ x t x t < x i ( 1 f ⋆ μ ) ( d ) . {\displaystyle \delta _{i}^{\prime }=\sum _{d\vert x_{i} \atop {d\nmid x_{t} \atop x_{t}<x_{i}}}({\frac {1}{f}}\star \mu )(d).} <p>If S {\displaystyle S} is factor-closed, then δ i = ( f ⋆ μ ) ( x i ) {\displaystyle \delta _{i}=(f\star \mu )(x_{i})} and δ i ′ = ( 1 f ⋆ μ ) ( x i ) {\displaystyle \delta _{i}^{\prime }=({\frac {1}{f}}\star \mu )(x_{i})} . <a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> </p> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>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 href="https://doi.org/10.1016%2F0024-3795%2892%2990042-9" target="_blank">https://doi.org/10.1016%2F0024-3795%2892%2990042-9</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>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. <a href="https://doi.org/10.1006%2Fjabr.1998.7844" target="_blank">https://doi.org/10.1006%2Fjabr.1998.7844</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>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. <a href="https://zenodo.org/record/1709912" target="_blank">https://zenodo.org/record/1709912</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>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 href="https://doi.org/10.1016%2F0024-3795%2892%2990042-9" target="_blank">https://doi.org/10.1016%2F0024-3795%2892%2990042-9</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>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. <a href="https://doi.org/10.1016%2FS0024-3795%2896%2900192-9" target="_blank">https://doi.org/10.1016%2FS0024-3795%2896%2900192-9</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>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. <a href="https://doi.org/10.1006%2Fjabr.1998.7844" target="_blank">https://doi.org/10.1006%2Fjabr.1998.7844</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>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. <a href="https://trepo.tuni.fi/handle/10024/117430" target="_blank">https://trepo.tuni.fi/handle/10024/117430</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Haukkanen, P.; Toth, L. (2018). "Inertia, positive definiteness and ℓp norm of GCD and LCM matrices and their unitary analogs" (PDF). Linear Algebra and Its Applications. 558: 1–24. doi:10.1016/j.laa.2018.08.022. <a href="https://trepo.tuni.fi/bitstream/10024/104222/1/Inertia_positive_definiteness_2018.pdf" target="_blank">https://trepo.tuni.fi/bitstream/10024/104222/1/Inertia_positive_definiteness_2018.pdf</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Haukkanen, P.; Toth, L. (2018). "Inertia, positive definiteness and ℓp norm of GCD and LCM matrices and their unitary analogs" (PDF). Linear Algebra and Its Applications. 558: 1–24. doi:10.1016/j.laa.2018.08.022. <a href="https://trepo.tuni.fi/bitstream/10024/104222/1/Inertia_positive_definiteness_2018.pdf" target="_blank">https://trepo.tuni.fi/bitstream/10024/104222/1/Inertia_positive_definiteness_2018.pdf</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> </ol>