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

POSTSCRIPT. Following Max Alekseyev's generalized statement, I thought we might still upgrade the theorem slighly.

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

  • 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$ Commented Feb 14, 2017 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$ Commented Mar 1, 2017 at 1:27
  • $\begingroup$ @JoeSilverman: That's useful, thank you! $\endgroup$ Commented Mar 1, 2017 at 1:35
  • $\begingroup$ The postscript follows from Max's answer too. $\endgroup$ Commented May 29, 2023 at 15:10
  • $\begingroup$ Does it? I must have missed something. In that case, what are the variables $v_1,\dots,v_n$? $\endgroup$ Commented May 29, 2023 at 15:14

2 Answers 2


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

  • $\begingroup$ This is very encouraging. Thanks. Please see my update. $\endgroup$ Commented Feb 14, 2017 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)$.

  • $\begingroup$ This is nice. I wish more details could be added. $\endgroup$ Commented Feb 15, 2017 at 2:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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