# The GCD-matrix: generalizing a result of Smith?

Let $M$ be the $n\times n$ matrix, known as the GCD matrix, of entries $M_{ij}=\gcd(i,j)$. In the paper

H J S Smith, On the value of a certain arithmetical determinant, Proc. London Math. Soc. 7:208-212 (1875-76)

it is shown that $\det M=\prod_{k=1}^n\varphi(k)$; where $\varphi(k)$ is the Euler totient function.

Lucas introduced the family of sequences defined recursively by $L_0(s,t)=0, L_1(s,t)=1$ and $$L_n(s,t)=s\cdot L_{n-1}(s,t)+t\cdot L_{n-2}(s,t).$$ Remark. My interest in these numbers lies in the fact that they are gcd-compatibile: $$\gcd(L_i,L_j)=L_{\gcd(i,j)}.$$

Question 1. Can Smith's result be extended to the determinantal evaluation $$\det\left[\gcd(L_i(s,t),L_j(s,t))\right]_{i,j=1}^n \,\,?$$

Update. On the basis of Max Alekseyev's calculations depicted below, I state the following claim.

Conjecture. Define a modified Euler's totient function $\varphi_L(k):=\sum_{d\vert n}L_d(s,t)\cdot\mu\left(\frac{k}d\right)$. Then $$\det\left[\gcd(L_i(s,t),L_j(s,t))\right]_{i,j=1}^n=\prod_{k=1}^n\varphi_L(k).$$

Remark. Observe that $L_n(2,-1)=n$, therefore Question 1 is already answered by Smith. In this case, $\varphi_L=\varphi$.

Question 2. We may start modest. If $s=2, t=1$ then $L_n(2,1)=P_n$ is the Pell sequence. What is the value of $$\det\left[\gcd(P_i,P_j)\right]_{i,j=1}^n\,\,?$$

• These results are related to the following result of Lindström and Wilf: Let $L$ be a finite lattice (or meet-semilattice), and let $f(s,v)$ be a function (say with values in a commutative ring) defined for all $s,v\in L$. Set $F(s,v)=\sum_{u\leq s}f(u,v)$. Then $$\det[F(s\wedge t,s]_{s,t\in L} = \prod_{s\in L}f(s,s).$$ See Enumerative Combinatorics, vol. 1, 2nd ed., Exercise 3.96(a). – Richard Stanley Feb 14 '17 at 19:13
• In case it's useful in tracking down references, sequences that satisfy $\gcd(L_i,L_j)=L_{\gcd(i,j)}$ are often called strong divisibility sequences. In addition to the Fibonacci-type sequences defined by Lucas, another interesting class of strong divisibility sequences are elliptic divisibility sequences. – Joe Silverman Mar 1 '17 at 1:27
• @JoeSilverman: That's useful, thank you! – T. Amdeberhan Mar 1 '17 at 1:35

For Pell numbers, the answer appears to be $$\det\left[\gcd(P_i,P_j)\right]_{i,j=1}^n = \prod_{k=1}^n \sum_{d|k} \mu(\frac{k}{d})\cdot P_d,$$ i.e. the product of first $n$ terms of the Moebius transform of Pell numbers. At least, this equality holds for all $n\leq 100$.

UPDATE

A more general statement holds:

Theorem. For any integer $n>0$ and any variables $v_1,v_2,\dots,v_n$, $$\det [v_{\gcd(i,j)}]_{i,j=1}^n = \prod_{k=1}^n \sum_{d|k} \mu(k/d)\cdot v_d.$$

The statement for Lucas sequences directly follows from this theorem, thanks to the property $\gcd(L_i,L_j)=L_{\gcd(i,j)}$.

The theorem can be proved using the following lemma:

Lemma. For any integers $0<m<n$, $$\sum_{d|n} \mu(n/d)\cdot v_{\gcd(m,d)} = 0.$$

Indeed, in matrix $V=[v_{\gcd(i,j)}]_{i,j=1}^n$, one can replace the row $V_n$ with the linear combination $\sum_{d|n} \mu(n/d)\cdot V_d$ (which does not change the determinant, and nullifies the $n$-th row except for its rightmost element), and then use induction on $n$.

• This is very encouraging. Thanks. Please see my update. – T. Amdeberhan Feb 14 '17 at 4:08

Suppose $A_n$ is the set of natural numbers that divide $L_n(s,t)$ but don't divide any $L_m(s,t)$ for $m<n$. Then corollary 1 to theorem 1 in GCD closed sets and determinants of GCD matrices by Beslin and Leigh shows that $$\det\left[\gcd(L_i(s,t),L_j(s,t))\right]_{i,j=1}^n =\prod_{i=1}^n \left(\sum_{d\in A_i}\varphi(d)\right).$$ Showing that $\sum_{d\in A_n}\varphi(d)=\sum_{d\vert n}L_d(s,t)\cdot\mu\left(\frac{k}d\right)$ is a quick application of Mobius inversion and the identity $n=\sum_{d|n} \varphi(d)$.

• This is nice. I wish more details could be added. – T. Amdeberhan Feb 15 '17 at 2:05