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\,\,?$$

  • 5
    $\begingroup$ 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). $\endgroup$ – Richard Stanley Feb 14 '17 at 19:13
  • $\begingroup$ 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. $\endgroup$ – Joe Silverman Mar 1 '17 at 1:27
  • $\begingroup$ @JoeSilverman: That's useful, thank you! $\endgroup$ – 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$.


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$.

| cite | improve this answer | |
  • $\begingroup$ This is very encouraging. Thanks. Please see my update. $\endgroup$ – 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)$.

| cite | improve this answer | |
  • $\begingroup$ This is nice. I wish more details could be added. $\endgroup$ – T. Amdeberhan Feb 15 '17 at 2:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.