The wikipedia gives us a formula for the [determinant of a circulant matrix](https://en.wikipedia.org/wiki/Circulant_matrix#Determinant). That is:


$$\mathrm{det}(C) 
= \prod\_{j=0}^{n-1} (c\_0 + c\_{n-1} \omega\_j + c\_{n-2} \omega\_j^2 + \dots + c\_1\omega\_j^{n-1})= \prod\_{j=0}^{n-1} f(\omega\_j),$$


with $\omega\_j=\exp(2\pi {\rm i}j/n)$ the $n$-th root of unity. 


Assuming a circulant matrix with only entries from $\{-1,1\}$, is there a number theoretic version of this formula which will enable you to compute the determinant exactly and efficiently using only operations on integers?


[This question was also posted to <https://math.stackexchange.com/questions/1616049/exact-determinant-of-a-circulant-matrix> previously.]



Exact determinant of a circulant matrix
We need to pick a prime $p$ and integer $k \ge 2$ such that $p = nk + 1$. (Alternatively you can choose a positive integer $p > 2n$ (not necessarily prime) such that $n$ divides $\phi(p)$, where $\phi$ is the Euler Totient function. However, I am not sure you can use FFT in the subsequent steps, and may have to resort to manual matrix vector multiplications.)


Next, we need to find a primitive $n$-th root of unity mod $p$. This root can be reused if you have many different circulant matrices of size $n$. This root, which we call $\omega \in \mathbb Z \_p$, is needed in the next step when you compute the FFT. Various fast heuristics exist, but note that even a worst case brute force search still runs in $O(p^2 \log(p))$


Using $\omega$, we will compute the number theoretic (mod $p$) FFT of $v$, where $v = (c\_0, ... c\_{n-1})$. Call the resulting vector $w$. This runs in $O(n \log(n))$


The entries of $w$ are in $\mathbb Z\_p$. In your notation, they represent $f(\omega\_j)$ mod $p$. Note that your $f(\omega\_j)$ are bounded to be in $\{-n, \ldots, n\}$. We will pick integer representatives for the entries of $w$ in $\{-n, \ldots, n\}$, and write that as $\hat w$. The product of the entries in $\hat w$ is your determinant. 


