ELA, Volume 11, pp. 51-58, February 2004, abstract.

An Analysis of GCD and LCM Matrices via the 
LDL^T-Factorization

Jeffrey S. Ovall

Let S={x_1,x_2,...,x_n} be a set of distinct positive integers 
such that gcd(x_i,x_j) belongs to 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 ``factor-closed'', then the determinant of the 
matrix e_{ij}=gcd(x_i,x_j) is det(E)=prod_{m=1}^n phi(x_m), 
where phi 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 
is a funcion from S to the complex numbers. This factorization 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).