# On the determinant $\det[\gcd(i-j,n)]_{1\le i,j\le n}$

In Sept. 2013, I investigated the determinant $$D_n=\det[\gcd(i-j,n)]_{1\le i,j\le n}$$ and computed the values $$D_1,\ldots,D_{100}$$ (cf. http://oeis.org/A228884). To my surprise, they are all positive!

Question. Does $$D_n>0$$ hold for all $$n=1,2,3,\ldots$$?

I believe that $$D_n$$ is always positive. How to prove this?

It is easy to see that $$D_n$$ is divisible by $$\sum_{k=1}^n\gcd(k,n)=\sum_{d\mid n}\varphi(d)\frac nd$$. It seems that $$\varphi(n)^{\varphi(n)}\sum_{k=1}^n\gcd(k,n)$$ divides $$D_n$$. Maybe there is a simple explanation for this.

Denote $$f(k)={\rm gcd}(k,n)$$. Clearly $$f$$ is an $$n$$-periodic function. $$D_n$$ is the circulant $$D_n=\det(f(i-j):0\leqslant i,j\leqslant n-1)$$ which equals $$\prod_{k=0}^{n-1}h(\omega^k)$$ where $$\omega=e^{2\pi i/n}$$ and $$h(t)=f(0)+f(1)t+\ldots+f(n-1)t^{n-1}$$. We have $$h(t)=\sum_{d|n} \varphi(d)(1+t^d+t^{2d}+\ldots+t^{(n/d-1)d}).$$ If $$t=\omega^k$$, the sum $$1+t^d+t^{2d}+\ldots+t^{(n/d-1)d}$$ either equals $$n/d$$ (if $$n$$ divides $$kd$$) or equals $$(1-\omega^{kn})/(1-\omega^{kd})=0$$ otherwise. In any case it is a non-negative integer, and for $$d=n$$ it is strictly positive.