17
$\begingroup$

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

$\endgroup$
5
  • 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

16
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ This is very encouraging. Thanks. Please see my update. $\endgroup$ Commented Feb 14, 2017 at 4:08
9
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .