<p>In general, there is a theoretical $O(n^{2.376})$ time algorithm for finding the <a href="http://en.wikipedia.org/wiki/LU_decomposition#Algorithms" rel="nofollow noreferrer">LU decomposition</a> of an arbitrary matrix using the <a href="http://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm" rel="nofollow noreferrer">Coppersmith–Winograd algorithm</a>, 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 <a href="https://stackoverflow.com/questions/1419681/boost-library-how-to-get-determinant-from-lu-factorize">lu_factorize</a> use this?</p>

<p>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 <a href="http://en.wikipedia.org/wiki/Moore_matrix" rel="nofollow noreferrer">referenced by wikipedia</a>, which presumably one proves by simply working out the LU decomposition in general.</p>

CC BY-SA 3.0
2012-01-07T02:55:18.210Z
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)?
Turbo
CC BY-SA 3.0
2012-01-07T04:35:01.747Z
Yes, I should've said O(n) obviously, really O(n log n) for large n.
Jeff Burdges
CC BY-SA 3.0
2012-01-07T05:27:50.550Z
Hi Jeff: Do you have a reference?
Turbo
CC BY-SA 3.0
2012-01-07T18:44:41.223Z
@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).
Jeffε
CC BY-SA 3.0
2012-03-05T14:25:22.653Z
I don't see a $O(n)$ formula referenced by Wikipedia. At best it looks $\Theta(n^2)$.
Peter Taylor
CC BY-SA 3.0
2012-01-06T16:39:33.017Z
2012-01-07T04:32:49.907Z
2017-05-23T12:40:09.333Z
Jeff Burdges
<p>It is important that, in the <a href="http://en.wikipedia.org/wiki/Moore_matrix" rel="nofollow noreferrer">definition</a> you provide, the matrix lives in a finite field, say $\mathbb{Z}_m$ where $m$ is prime. This allows you to use <a href="http://en.wikipedia.org/wiki/Euler%27s_totient_function#Euler.27s_theorem" rel="nofollow noreferrer">Euler's theorem</a> 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$.</p>

<p>If $m$ is prime or can be efficiently factorised,  the worst-case <strong>complexity</strong> is dominated by the number of steps you need for matrix multiplication $O(n^\omega)$. For instance, the <a href="https://cstheory.stackexchange.com/a/10418/7286">Smith normal form approach</a> I mentioned in the <a href="https://cstheory.stackexchange.com/q/10393/7286">partner post</a> 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.</p>

<p>You get a <strong>slow-down</strong> 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 <a href="https://cstheory.stackexchange.com/a/10418/7286">algorithm presented</a> gives you a <a href="http://en.wikipedia.org/wiki/Turing_reduction" rel="nofollow noreferrer">Cook reduction</a> to Double-Modular-Exponentiation on $\mathbb{Z}_m$.</p>

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

<hr>

<p><strong>Update</strong>: on the possibility of achieving $O(n\log^a n)$.</p>

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

<p>Algorithms for <em>structured</em> 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 <a href="http://books.google.de/books?id=I00HeGu8qicC&amp;lpg=PP1&amp;hl=de&amp;pg=PP1#v=onepage&amp;q&amp;f=false" rel="nofollow noreferrer">book</a> (open access pages), or in this article <a href="http://dl.acm.org/citation.cfm?id=606709" rel="nofollow noreferrer">[ACM]</a>,<a href="http://comet.lehman.cuny.edu/vpan/pdf/38627.pdf" rel="nofollow noreferrer">[PDF]</a>.</p>

<p>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</p>

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

<p>, and the rank $r&gt;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, <a href="http://comet.lehman.cuny.edu/vpan/pdf/38627.pdf" rel="nofollow noreferrer">this article</a> has also a lot of information about these methods.</p>

<p>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.</p>

CC BY-SA 3.0
2012-03-04T20:13:06.483Z
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$.
Turbo
CC BY-SA 3.0
2012-03-04T20:34:50.280Z
That's fine, since you can compute the totient function of $3^k$ :)
Juan Bermejo Vega
CC BY-SA 3.0
2012-03-04T20:35:59.250Z
well that does not simplify the complexity, I would say since the field is very very large.
Turbo
CC BY-SA 3.0
2012-03-04T21:22:38.723Z
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.
Juan Bermejo Vega
CC BY-SA 3.0
2012-03-05T05:13:35.193Z
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.
Turbo
CC BY-SA 3.0
2012-03-05T12:43:30.533Z
It seems not as easy as in the Vandermonde case. I gathered some new information which might be helpful. I will update my answer.
Juan Bermejo Vega
CC BY-SA 3.0
2012-03-05T23:23:22.900Z
I think something is missing in your comments A=B=I will give M-AMB=0.
Turbo
CC BY-SA 3.0
2012-03-06T00:54:50.390Z
That case is not useful for the method used in the book, but I agree, I was not very clear. I corrected that and added a second reference about these displacement operator methods which may help. You may take a look now to see if the techniques are applicable.
Juan Bermejo Vega
CC BY-SA 3.0
2012-03-04T13:57:17.087Z
2012-03-06T00:51:39.130Z
2017-04-13T12:32:28.117Z
Juan Bermejo Vega
<p>Moore matrix is similar to Vandermonde matrix but has a slightly modified definition.
<a href="http://en.wikipedia.org/wiki/Moore_matrix" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Moore_matrix</a></p>

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

<p>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\}$?</p>

<p>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)</p>

<p>Post similar to the current one: <a href="https://cstheory.stackexchange.com/questions/10393/determinant-modulo-m">Determinant modulo m</a></p>

CC BY-SA 3.0
2012-01-07T18:42:41.397Z
Can the Moore determinant even be computed in O(n^3) time (on an integer RAM)?
Jeffε
CC BY-SA 3.0
2012-01-08T00:14:41.780Z
@JɛﬀE That is why I mentioned modulo random $N \in \mathbb{N}$.
Turbo
CC BY-SA 3.0
2012-03-06T01:01:51.253Z
By the way, and I'm just curious, are there known applications that would benefit of such "superfast" algorithm?
Juan Bermejo Vega
CC BY-SA 3.0
2012-03-06T01:03:35.917Z
@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.
Juan Bermejo Vega
<cc.complexity-theory><algebraic-complexity>
Determinant of a generalized Vandermonde matrix
Turbo
# Determinant of a generalized Vandermonde matrix

(Asked by: username_0 on 2012-01-06)

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](https://cstheory.stackexchange.com/questions/10393/determinant-modulo-m)

**Tags:** cc.complexity-theory, algebraic-complexity
> **Comments:**
> **username_1**: Can the Moore determinant even be computed in O(n^3) time (on an integer RAM)?  
> **username_0**: @JɛﬀE That is why I mentioned modulo random $N \in \mathbb{N}$.  
> **username_2**: By the way, and I'm just curious, are there known applications that would benefit of such "superfast" algorithm?  
> **username_2**: @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.  

---

## 2 answers

### Answer by username_3 on 2012-01-06. Score: 4

In general, there is a theoretical $O(n^{2.376})$ time algorithm for finding the [LU decomposition](http://en.wikipedia.org/wiki/LU_decomposition#Algorithms) of an arbitrary matrix using the [Coppersmith–Winograd algorithm](http://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_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](https://stackoverflow.com/questions/1419681/boost-library-how-to-get-determinant-from-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](http://en.wikipedia.org/wiki/Moore_matrix), which presumably one proves by simply working out the LU decomposition in general.

> **Comments:**
> **username_0**: 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)?  
> **username_3**: Yes, I should've said O(n) obviously, really O(n log n) for large n.  
> **username_0**: Hi Jeff: Do you have a reference?  
> **username_1**: @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).  
> **username_4**: I don't see a $O(n)$ formula referenced by Wikipedia. At best it looks $\Theta(n^2)$.  

---

### Answer by username_2 on 2012-03-04. Score: 3

It is important that, in the [definition](http://en.wikipedia.org/wiki/Moore_matrix) 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](http://en.wikipedia.org/wiki/Euler%27s_totient_function#Euler.27s_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](https://cstheory.stackexchange.com/a/10418/7286) I mentioned in the [partner post](https://cstheory.stackexchange.com/q/10393/7286) 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](https://cstheory.stackexchange.com/a/10418/7286) gives you a [Cook reduction](http://en.wikipedia.org/wiki/Turing_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](http://books.google.de/books?id=I00HeGu8qicC&lpg=PP1&hl=de&pg=PP1#v=onepage&q&f=false) (open access pages), or in this article [[ACM]](http://dl.acm.org/citation.cfm?id=606709),[[PDF]](http://comet.lehman.cuny.edu/vpan/pdf/38627.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](http://comet.lehman.cuny.edu/vpan/pdf/38627.pdf) 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.

> **Comments:**
> **username_0**: 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$.  
> **username_2**: That's fine, since you can compute the totient function of $3^k$ :)  
> **username_0**: well that does not simplify the complexity, I would say since the field is very very large.  
> **username_2**: 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.  
> **username_0**: 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.  
> **username_2**: It seems not as easy as in the Vandermonde case. I gathered some new information which might be helpful. I will update my answer.  
> **username_0**: I think something is missing in your comments A=B=I will give M-AMB=0.  
> **username_2**: That case is not useful for the method used in the book, but I agree, I was not very clear. I corrected that and added a second reference about these displacement operator methods which may help. You may take a look now to see if the techniques are applicable.  

---

