GCD matrix

Last updated June 15, 2024

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. A brief review of papers on GCD type matrices before that time is presented in Haukkanen, Wang & Sillanpää (1997).

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

Bourque–Ligh conjecture

Bourque & Ligh (1992) conjectured that the LCM matrix on a GCD-closed set $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 $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\}.$ A counterexample consisting of odd numbers is $S=\{1,3,5,7,195,291,1407,4025,1020180525\}$ . 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).

The Hasse diagram of an odd GCD closed set whose LCM matrix is singular Counterexample.png — The Hasse diagram of an odd GCD closed set whose LCM matrix is singular

Divisibility

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

Matrix norms

Some results on matrix norms of GCD type matrices are presented in the literature. Two basic results concern the asymptotic behaviour of the $\ell _{p}$ norm of the GCD and LCM matrix on $S=\{1,2,\dots ,n\}$ . ^[6]

Given $p\in \mathbb {N} ^{+}$ , the $\ell _{p}$ norm of an $n\times n$ matrix $A$ is defined as

\Vert A\Vert _{p}=\left(\sum _{i=1}^{n}\sum _{j=1}^{n}|a_{ij}|^{p}\right)^{1/p}.

Let $S=\{1,2,\dots ,n\}$ . If $p\geq 2$ , then

\Vert (S)\Vert _{p}=C_{p}^{1/p}n^{1+(1/p)}+O((n^{(1/p)-p}E_{p}(n)),

where

C_{p}:={\frac {2\zeta (p)-\zeta (p+1)}{(p+1)\zeta (p+1)}}

and $E_{p}(x)=x^{p}$ for $p>2$ and $E_{2}(x)=x^{2}\log x$ . Further, if $p\geq 1$ , then

\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}),

where

D_{p}:={\frac {\zeta (p+2)}{(p+1)^{2}\zeta (p)}}.

Factorizations

Let $f$ be an arithmetical function, and let $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}))$ is referred to as the GCD matrix on $S$ associated with $f$ . The LCM matrix $[S]_{f}$ on $S$ associated with $f$ is defined analogously. One may also use the notations $(S)_{f}=f(S)$ and $[S]_{f}=f[S]$ .

Let $S$ be a GCD-closed set. Then

(S)_{f}=E\Delta E^{T},

where $E$ is the $n\times n$ matrix defined by

e_{ij}={\begin{cases}1&{\mbox{if }}x_{j}\,\mid \,x_{i},\\0&{\mbox{otherwise}}\end{cases}}

and $\Delta$ is the $n\times n$ diagonal matrix, whose diagonal elements are

\delta _{i}=\sum _{d\mid x_{i} \atop {d\nmid x_{t} \atop x_{t}<x_{i}}}(f\star \mu )(d).

Here $\star$ is the Dirichlet convolution and $\mu$ is the Möbius function.

Further, if $f$ is a multiplicative function and always nonzero, then

[S]_{f}=\Lambda E\Delta ^{\prime }E^{T}\Lambda ,

where $\Lambda$ and $\Delta '$ are the $n\times n$ diagonal matrices, whose diagonal elements are $\lambda _{i}=f(x_{i})$ and

\delta _{i}^{\prime }=\sum _{d\vert x_{i} \atop {d\nmid x_{t} \atop x_{t}<x_{i}}}({\frac {1}{f}}\star \mu )(d).

If $S$ is factor-closed, then $\delta _{i}=(f\star \mu )(x_{i})$ and $\delta _{i}^{\prime }=({\frac {1}{f}}\star \mu )(x_{i})$ . ^[6]

Related Research Articles

In number theory, an arithmetic, arithmetical, or number-theoretic function is generally any function f(n) whose domain is the positive integers and whose range is a subset of the complex numbers. Hardy & Wright include in their definition the requirement that an arithmetical function "expresses some arithmetical property of n". There is a larger class of number-theoretic functions that do not fit this definition, for example, the prime-counting functions. This article provides links to functions of both classes.

In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers $x$ , $y$ , the greatest common divisor of $x$ and $y$ is denoted $. For example, the GCD of 8 and 12 is 4, that is, gcd(8, 12) = 4 .$

In physics, the Lorentz transformations are a six-parameter family of linear transformations from a coordinate frame in spacetime to another frame that moves at a constant velocity relative to the former. The respective inverse transformation is then parameterized by the negative of this velocity. The transformations are named after the Dutch physicist Hendrik Lorentz.

The Riemann zeta function or Euler–Riemann zeta function, denoted by the Greek letter $ζ$ (zeta), is a mathematical function of a complex variable defined as

<span class="mw-page-title-main">Euler's totient function</span> Number of integers coprime to and not exceeding n

In number theory, Euler's totient function counts the positive integers up to a given integer $n$ that are relatively prime to $n$ . It is written using the Greek letter phi as $or, and may also be called Euler's phi function . In other words, it is the number of integers k in the range 1 \leq k \leq n for which the greatest common divisor gcd(n, k) is equal to 1. The integers k of this form are sometimes referred to as totatives of n .$

In order theory, a field of mathematics, an incidence algebra is an associative algebra, defined for every locally finite partially ordered set and commutative ring with unity. Subalgebras called reduced incidence algebras give a natural construction of various types of generating functions used in combinatorics and number theory.

In mechanics and geometry, the 3D rotation group, often denoted SO(3), is the group of all rotations about the origin of three-dimensional Euclidean space $under the operation of composition.$

In mathematics, particularly in linear algebra, tensor analysis, and differential geometry, the Levi-Civita symbol or Levi-Civita epsilon represents a collection of numbers; defined from the sign of a permutation of the natural numbers $1, 2, ..., n$ , for some positive integer $n$ . It is named after the Italian mathematician and physicist Tullio Levi-Civita. Other names include the permutation symbol, antisymmetric symbol, or alternating symbol, which refer to its antisymmetric property and definition in terms of permutations.

In mathematics, the Bernoulli polynomials, named after Jacob Bernoulli, combine the Bernoulli numbers and binomial coefficients. They are used for series expansion of functions, and with the Euler–MacLaurin formula.

In mathematics, the Hodge star operator or Hodge star is a linear map defined on the exterior algebra of a finite-dimensional oriented vector space endowed with a nondegenerate symmetric bilinear form. Applying the operator to an element of the algebra produces the Hodge dual of the element. This map was introduced by W. V. D. Hodge.

In mathematics, a Dirichlet series is any series of the form

In mathematics, the Smith normal form is a normal form that can be defined for any matrix with entries in a principal ideal domain (PID). The Smith normal form of a matrix is diagonal, and can be obtained from the original matrix by multiplying on the left and right by invertible square matrices. In particular, the integers are a PID, so one can always calculate the Smith normal form of an integer matrix. The Smith normal form is very useful for working with finitely generated modules over a PID, and in particular for deducing the structure of a quotient of a free module. It is named after the Irish mathematician Henry John Stephen Smith.

In probability theory and mathematical physics, a random matrix is a matrix-valued random variable—that is, a matrix in which some or all of its entries are sampled randomly from a probability distribution. Random matrix theory (RMT) is the study of properties of random matrices, often as they become large. RMT provides techniques like mean-field theory, diagrammatic methods, the cavity method, or the replica method to compute quantities like traces, spectral densities, or scalar products between eigenvectors. Many physical phenomena, such as the spectrum of nuclei of heavy atoms, the thermal conductivity of a lattice, or the emergence of quantum chaos, can be modeled mathematically as problems concerning large, random matrices.

In mathematics, the von Mangoldt function is an arithmetic function named after German mathematician Hans von Mangoldt. It is an example of an important arithmetic function that is neither multiplicative nor additive.

In mathematics, the Selberg class is an axiomatic definition of a class of L-functions. The members of the class are Dirichlet series which obey four axioms that seem to capture the essential properties satisfied by most functions that are commonly called L-functions or zeta functions. Although the exact nature of the class is conjectural, the hope is that the definition of the class will lead to a classification of its contents and an elucidation of its properties, including insight into their relationship to automorphic forms and the Riemann hypothesis. The class was defined by Atle Selberg in, who preferred not to use the word "axiom" that later authors have employed.

In number theory, Ramanujan's sum, usually denoted c_q(n), is a function of two positive integer variables q and n defined by the formula

In number theory, an average order of an arithmetic function is some simpler or better-understood function which takes the same values "on average".

In number theory, Jordan's totient function, denoted as $, where is a positive integer, is a function of a positive integer,, that equals the number of -tuples of positive integers that are less than or equal to and that together with form a coprime set of integers$

In mathematics, Montgomery's pair correlation conjecture is a conjecture made by Hugh Montgomery that the pair correlation between pairs of zeros of the Riemann zeta function is

The purpose of this page is to catalog new, interesting, and useful identities related to number-theoretic divisor sums, i.e., sums of an arithmetic function over the divisors of a natural number $, or equivalently the Dirichlet convolution of an arithmetic function with one:$

References

1 2 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 .
1 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 .
↑ 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.
1 2 Haukkanen, P.; Toth, L. (2018). "Inertia, positive definiteness and ℓp norm of GCD and LCM matrices and their unitary analogs". Linear Algebra and Its Applications. 558: 1–24. doi: 10.1016/j.laa.2018.08.022 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[borque-ligh-1] 1 2 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 .

[hong-2] 1 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 .

[smith-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.

[haukkanen-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 .

[korkee-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.

[haukkanen-toth-6] 1 2 Haukkanen, P.; Toth, L. (2018). "Inertia, positive definiteness and ℓp norm of GCD and LCM matrices and their unitary analogs". Linear Algebra and Its Applications. 558: 1–24. doi: 10.1016/j.laa.2018.08.022 .

[1]

[2]

[3]

[4]

[5]

[6]