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

Abstract

Let S= {x₁, x₂,...., x_n} be a set of distinct positive integers such that gcd(x_i, x_j)  ∈
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 e_ij = get(x_i, x_j) is det(E) = П^n_m=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 f_ij = lcm(x_i, x_j ) 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 LDL^T-Factorization of any matrix b_ij = f(gcd(x_i, x_j)), 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 g_ij= gcd(x_i, x_j)/ lcm(x_i, x_j) and h_ij = lcm(x_i, x_j)/ gcd(x_i, x_j).