8
$\begingroup$

The wikipedia gives us a formula for the determinant of a circulant matrix. 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.]

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Well, there is the standard cofactor expansion of the determinant, which involves only the entries (and signs) … what do you mean by 'efficient'? $\endgroup$
    – LSpice
    Commented Jan 19, 2016 at 14:36
  • $\begingroup$ @LSpice I meant something that for large matrices has a similar computational complexity to the direct (but inexact in practice) method given by the formula. Essentially, can we do the operations over a finite field instead? $\endgroup$
    – Simd
    Commented Jan 19, 2016 at 14:43
  • 1
    $\begingroup$ $\omega_1$ is a root of the $n$-th cyclotomic polynomial $\Phi_n \in \mathbb{Z}\left[X\right]$, which is monic. Thus, $\mathbb{Z}\left[\omega_1\right] \cong \mathbb{Z}\left[X\right] / \Phi_n$, and in the latter ring you can easily calculate. Now, is this efficient? I don't know. $\endgroup$
    – darij grinberg
    Commented Jan 21, 2016 at 4:29
  • $\begingroup$ You might be able to adapt "black-box linear algebra" a la Wiedemann to do this. See also oeis.org/A215897 $\endgroup$
    – Steve Huntsman
    Commented Jan 21, 2016 at 15:55
  • 2
    $\begingroup$ This determinant is also equal to the resultant of $X^n-1$ and $P:=c0+...+c_{n-1}X^{n-1}$. This resultant can be computed efficiently by modular algorithms (as mentionned on wikipedia for example, en.wikipedia.org/wiki/Resultants#Computation). There are also so-called subresultant algorithms (variation on using Euclid algorithm to compute the resultant but avoiding to work in the rationals). $\endgroup$
    – Oblomov
    Commented Jan 22, 2016 at 13:41

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

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