# Determinant of a generalized Vandermonde matrix

Moore matrix is similar to Vandermonde matrix but has a slightly modified definition. http://en.wikipedia.org/wiki/Moore_matrix

What is the complexity of computing the determinant of a given $n \times n$ full rank Moore matrix modulo some integer?

Can Moore determinant be reduced from $O(n^{3})$ using FFT techniques to $O(n\log^{a}n)$ for some $a \in \mathbb{R}_{+} \cup \{0\}$?

Is complexity of Moore det modulo an integer and Vandermonde det the same? Complexity of Vandermonde determinant is $O(n\log^{2}n)$ (Page 644 in Handbook of Theoretical Computer Science: Algorithms and complexity By Jan Leeuwen)

Post similar to the current one: Determinant modulo m

• Can the Moore determinant even be computed in O(n^3) time (on an integer RAM)? Jan 7 '12 at 18:42
• @JɛﬀE That is why I mentioned modulo random $N \in \mathbb{N}$.
– Mr.
Jan 8 '12 at 0:14
• By the way, and I'm just curious, are there known applications that would benefit of such "superfast" algorithm? Mar 6 '12 at 1:01
• @J$\varepsilon$ffE, do you happen to know if computing a double modular exponentiation over $N$ is in BPP for trivial $N$?. Because that's a problem to compute the coefficients of the matrix. Mar 6 '12 at 1:03

In general, there is a theoretical $O(n^{2.376})$ time algorithm for finding the LU decomposition of an arbitrary matrix using the Coppersmith–Winograd algorithm, which then obviously yields the determinant (adding $O(n)$ time). There is a problem however that the Coppersmith–Winograd algorithm isn't considered usable in practice. Afaik, people mostly use the $O(n^{2.807})$ time Strassen algorithm. Doesn't Boost UBLAS's lu_factorize use this?

In you case, the Moore matrix should admit considerable optimizations because basically any Gaussian elimination like procedure like LU decomposition can be done abstractly. Indeed, you'll find a nice $O(n)$ formula for computing the Moore determinant referenced by wikipedia, which presumably one proves by simply working out the LU decomposition in general.

• Hi Jeff: Which reference are you refererring for the O(n^2) formula. I think Vandermonde det can be calculated in O(nlogn) but I cannot find reference. So should Moore det also be in O(nlogn)?
– Mr.
Jan 7 '12 at 2:55
• Yes, I should've said O(n) obviously, really O(n log n) for large n. Jan 7 '12 at 4:35
• Hi Jeff: Do you have a reference?
– Mr.
Jan 7 '12 at 5:27
• @JeffBurdges: If the running time is O(n log n) "for large n", then by definition, the running time is O(n log n), not O(n). Jan 7 '12 at 18:44
• I don't see a $O(n)$ formula referenced by Wikipedia. At best it looks $\Theta(n^2)$. Mar 5 '12 at 14:25

It is important that, in the definition you provide, the matrix lives in a finite field, say $\mathbb{Z}_m$ where $m$ is prime. This allows you to use Euler's theorem to compute the double-exponentials $a^{q^e}\mod m$ that appear in the matrix in time $O(\log (mn) \; M(\log m))$. $$a^{q^i}\equiv a^{q^i\pmod{\varphi(m)}}\pmod m$$ Otherwise, it seems hard even to compute the matrix coefficients without factorising $m$.

If $m$ is prime or can be efficiently factorised, the worst-case complexity is dominated by the number of steps you need for matrix multiplication $O(n^\omega)$. For instance, the Smith normal form approach I mentioned in the partner post would compute the determinant in time $O\left( n^\omega \; \log^2m\; \log (mn) \right)$ if you use "slow" multiplication algorithms$^*$. $\omega$ can be chosen to be 2.373.

You get a slow-down in Moore vs Vandermonde since you must double-exponentiate the coefficients of the matrix. When you can factorise $m$ this slow-down is just polylogarithmic on $m$. If not, the algorithm presented gives you a Cook reduction to Double-Modular-Exponentiation on $\mathbb{Z}_m$.

Note *: faster algorithms for integer multiplication allow you to replace $\log^2 m$ with $M(\log m \log\log m)$ .

Update: on the possibility of achieving $O(n\log^a n)$.

I have no definite answer for this, but I found some information that may tighten your search.

Algorithms for structured matrices that compute quantities like determinants in time $O(n\log^a n)$ are called "superfast" in the literature. All known "superfast" algorithms for structured matrices (Vandermonde, Toeplitz, Hankel) seem to rely on a common property of this matrices known as low "displacement rank". Confer the discussion on the first chapter of this book (open access pages), or in this article [ACM],[PDF].

From what I read, given a $m\times n$ Moore matrix $M$, if you were able to find matrices $A$, $B$ such that the new matrix $L(M)=AM-MB$ (or alternatively $L(M)=M- AMB$) has the following structure

$$L(M) = \sum_{k=1}^r g_k h_k^T$$

, and the rank $r>0$ is small (either constant or bounded by $o(\text{min} \;\{m,n\})$), then you can apply existing techniques (check chapter 5 of the book, open-access pages) to triangularise $M$ and, hence, compute $\det{M}$, using $O(n\log^2 n)$. Above, the $g_k$, $h_k$ denote vectors. If you can not find the book above to read the whole thing, this article has also a lot of information about these methods.

Unfortunately, I have no been able to find a low-displacement-rank structure for the Moore matrix (Vandermonde has). The main complication here seems to arise from the "non-linear" nature of the double exponential. If it helps, the cases for Vandermonde, Cauchy, Toeplitz, Hankel are worked out in the book.

• I can make my matrix live in a field of char $3$. However, the size of alphabets for my intended application will be large. So $m$ is of form $3^{k}$ for some large enough $k$.
– Mr.
Mar 4 '12 at 20:13
• That's fine, since you can compute the totient function of $3^k$ :) Mar 4 '12 at 20:34
• well that does not simplify the complexity, I would say since the field is very very large.
– Mr.
Mar 4 '12 at 20:35
• It does simplify the problems I mention with the double-exponentiation. Since $\varphi(3^k)=3^k-3^{k-1}$, you can use Euler's theorem to double exponentiate $a^{q^i}\mod m$: first, compute $b=q^i\mod \varphi(3^k)$, then $a^b\mod 3^k$. You can do this in time $O(\log(n3^k)M(k \log3))$. Using school-multiplication algorithm, $M(n)=n^2$, and you would get a final "netto" cost of $O(n^\omega k^2 log^2 3 (\log n + k\log 3))$ which is efficient. Mar 4 '12 at 21:22
• Can we replace $\omega$ by $1 + \epsilon$? That is the cost saving I curious in (may be possible from the matrix structure). With $\omega \ge 2$, I don't gain anything for my purpose.
– Mr.
Mar 5 '12 at 5:13