# Find the determinant of the $n\times n$ matrix $A_n$ with $(A_n)_{i,j}={n\choose |i-j|}$.

I'd like to find the determinant of the matrix $$A_n$$ given by $$(A_n)_{i,j}={n\choose |i-j|}$$ for all $$n\in\mathbb{Z}_{\ge 1}$$ and $$i,j\in\{1,2,\ldots,n\}$$. Here is what I know so far:

• $$\det(A_n)=0$$ if and only if $$6\mid n$$.
• $$2^n-1$$ is an eigenvalue of all $$A_n$$, with eigenvector $$(1,1,\ldots,1)$$
• If $$n$$ is prime, then $$\det(A_n)\equiv 1\pmod n$$
• If $$n+1$$ is prime and $$n>2$$, then $$\det(A_n)\equiv 0\pmod {n+1}$$
• It might be useful to observe that your matrix is Toeplitz, and that we could express your matrix as $$A = (M + I)^n + (M^T + I)^n - I$$ where $M$ is the matrix with $1$s on the superdiagonal and $0$s in the other entries. – Omnomnomnom Dec 19 '18 at 19:21
• @Omnomnomnom Yes, I've been searching for determinants of symmetric Toeplitz matrices for the past two hours or so. The expression is new to me, so thank you for that. – Mastrem Dec 19 '18 at 19:31
• It appears this matrix is something called a circulant matrix, which has a nice formula for the determinant – Mastrem Dec 19 '18 at 19:58
• well spotted, I'm disappointed that I missed that – Omnomnomnom Dec 19 '18 at 20:00

As you noted, your matrix is circulant. In particular, if we take $$P$$ to be the permutation matrix described here, then we have $$A = \sum_{k=0}^{n-1} \binom nk P^k = (I + P)^n - I$$ Thus, we may compute your determinant as the product of all eigenvalues, namely $$\det(A) = \prod_{j=0}^{n-1} [(1 + e^{(2 \pi j/n) i})^n - 1]$$
• We can see from this equation that the determinant will be zero whenever $z^n = 1$ has a solution satisfying $(1 + z)^n = 1$. That is, the determinant will be zero if and only if the polynomials $z^n - 1$ and $(1 + z)^n - 1$ fail to be relatively prime. I would be interested in seeing why this should be true iff $6 \mid n$. – Omnomnomnom Dec 19 '18 at 20:13
• Suppose the polynomials $X^n-1$ and $(X+1)^n-1$ have some common root $z\in\mathbb{C}$, then $|z|=|z+1|$, so $\Re z=-\frac12$, but $z$ is also of the form $\cos\left(\frac{2\pi k}n\right)+i\sin\left(\frac{2\pi k}n\right)$, which gives $\cos\left(\frac{2\pi k}n\right)=-\frac12$, so $k=\pm\frac n3$, which gives $3\mid n$ and $z=\exp\left(\pm\frac{2\pi i}3\right)$. Writing $n=3m$, we must have $\left(1+\exp\left(\pm\frac{2\pi i}3\right)\right)^{3m}=(-1)^m=1$, so $m$ is even and $6\mid n$. Conversely, it's easy to check that if $6\mid n$, $X^2+X+1$ is a common divisor of $(X+1)^n-1$ and $X^n-1$ – Mastrem Dec 19 '18 at 20:34
• I should add, I'm trying to find for which primes $p$ the polynomials $x^n-1$ and $(x+1)^n-1$ are coprime in $\mathbb{F}_p[x]$, and that's how I arrived at the matrix in question – Mastrem Dec 19 '18 at 20:37