An analysis of GCD and LCM matrices via the LDL^T-factorization

Main Article Content

Jeffrey S. Ovall


Let S= {x1, x2,...., xn} be a set of distinct positive integers such that gcd(xi, xj)  ∈
S for 1 ≤ i, j ≤ n. Such a set is called GCD-closed. In 1875/1876, H.J.S. Smith showed that, if the set S is "factored-closed", then the determinant of the amtrix eij = get(xi, xj) is det(E) = Пnm=1 φ(xm), where φ denotes Euler’s Phi-function. Since the early 1990’s there has been a rebirth of interest in matrices defined in terms of arithmetic functions defined on S. In 1992, Bourque and Ligh conjectured that the matrix fij = lcm(xi, xj ) is nonsingular. Several authors have shown that, although the conjecture holds for n ≤ 7, it need not hold in general. At present there are no known necessary conditions for F to be nonsingular, but many have offered sufficient conditions.

In this note, a simple algorithm is offered for computing the LDLT-Factorization of any matrix bij = f(gcd(xi, xj)), where f: S→C. this factoriation gives us an easy way of answering the question of singularity, computing its determinant, and determining its inertia (the number of positive negative and zero eigenvalues). Using this factorization, it is argued that E is positive definite regardless of whether or not S is GCD-closed (a known result), and that F is indefinite for n ≥ 2. Also revisited are some of the known sufficient conditions for the invertibility of F, which are justified in the present framework, and then a few new sufficient conditions are offered. Similar statements are made for the reciprocal matrices gij= gcd(xi, xj)/ lcm(xi, xj) and hij = lcm(xi, xj)/ gcd(xi, xj). 

Article Details