<p>There are clasical algorithms <a href="http://en.wikipedia.org/wiki/Determinant#Further_methods" rel="nofollow">[1]</a>, <a href="http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra" rel="nofollow">[2]</a>, <a href="http://www.ams.org/journals/mcom/1974-28-125/S0025-5718-1974-0331751-8/home.html" rel="nofollow">[3]</a> to compute the determinant of a $k\times k$  matrix using $O(k^\omega)$ floating-point operations, where $O(k^\omega)$ is the number of operations that you need for matrix multiplication.  Therefore, you can get a better bound 
$$\textstyle O(\binom{n}{k}^2 k^\omega )$$
, which is the cost of computing all of them individually and listing. You can let $\omega=2.3727$. For implementations the Strassen algorithm is often used with has $\omega=2.807$.</p>

<p>In particular, the <a href="http://www.ams.org/journals/mcom/1974-28-125/S0025-5718-1974-0331751-8/home.html" rel="nofollow">third reference</a> uses the Strassen algorithm, but explicitly mentions:</p>

<blockquote>
  <p>In Section 5 we show that matrix multiplication, triangular factorization, and
  inversion are equivalent in computational complexity.</p>
</blockquote>

CC BY-SA 3.0
2012-03-13T11:03:28.720Z
That's *exactly* what I said.
Juan Bermejo Vega
CC BY-SA 3.0
2012-03-13T11:06:41.973Z
My answer is algorithmic independent. The OP explicitly asked for some names of particular algorithm so I talked about Strassen because is practical for implementations.
Juan Bermejo Vega
CC BY-SA 3.0
2012-03-08T21:27:37.763Z
2012-03-09T08:31:33.493Z
2012-03-09T08:31:33.493Z
Juan Bermejo Vega
<p>For $k=n-1$ you can do better than $O(\binom{n}{k}k^{\omega}) = O(n^{\omega+1})$ by taking advantage of the fact that the determinants of $k \times k$ minors are exactly the $(n-k)$-th order partial derivatives of the determinant of your matrix, and then applying Baur--Strassen. </p>

<p>Baur--Strassen says that if a function $f$ can be computed by an arithmetic circuit of size $s$, then there is a (multi-output) circuit of size $4s$ computing $(\partial f / \partial x_1, \dotsc, \partial f / \partial x_n)$. As the original determinant can be computed in time $O(n^\omega)$, the $(n-1) \times (n-1)$ minors can  be computed using the above trick in time $O(4n^{\omega}) = O(n^{\omega})$, instead of $O(n^{\omega+1})$ the other way.</p>

<p>(I believe finding a useful extension of Baur--Strassen to higher partial derivatives is an open question.)</p>

CC BY-SA 3.0
2013-06-01T03:28:09.087Z
2013-06-01T03:28:09.087Z
Joshua Grochow
<p>Let $A$ be an $n \times n$-matrix, and let $1 \leq k \leq n$. Which algorithms do exist, or what is know about the complexity of computing determinants of all $k \times k$-minors?</p>

<p>The naive algorithm has complexity $\Theta( {n \choose k}^2 k! )$. If we apply Gaussian elemination for each minor $\Theta( {n \choose k}^2 k^3 )$. Of course, there is a dynamic programming approach, too, but I am not firm enough to compute its complexity.</p>

<p>I am also interested whether there is a lower bound actually known. </p>

CC BY-SA 3.0
2012-03-08T17:50:04.557Z
Doesn't cofactor expansion and dynamic programming immediately give you $O(\binom{n}{k}^2 k)$ time?
Jeffε
CC BY-SA 3.0
2013-06-01T03:45:30.407Z
@JeffE: I'm not sure exactly what you have in mind; can you elaborate? For $k=n$ the bound you state is $O(n)$ (which is so good as to be impossible, as it would imply $\omega=1$!), though already for $k=n-1$ it becomes the clearly legal bound of $O(n^3)$. But maybe what you're thinking only works for $k=O(1)$ or $k=o(n)$ (or even just $k < n$)?
Joshua Grochow
<ds.algorithms>
Complexity of determinant of k-minors
shuhalo
# Complexity of determinant of k-minors

(Asked by: username_0 on 2012-03-08)

Let $A$ be an $n \times n$-matrix, and let $1 \leq k \leq n$. Which algorithms do exist, or what is know about the complexity of computing determinants of all $k \times k$-minors?

The naive algorithm has complexity $\Theta( {n \choose k}^2 k! )$. If we apply Gaussian elemination for each minor $\Theta( {n \choose k}^2 k^3 )$. Of course, there is a dynamic programming approach, too, but I am not firm enough to compute its complexity.

I am also interested whether there is a lower bound actually known.

**Tags:** ds.algorithms
> **Comments:**
> **username_1**: Doesn't cofactor expansion and dynamic programming immediately give you $O(\binom{n}{k}^2 k)$ time?  
> **username_2**: @JeffE: I'm not sure exactly what you have in mind; can you elaborate? For $k=n$ the bound you state is $O(n)$ (which is so good as to be impossible, as it would imply $\omega=1$!), though already for $k=n-1$ it becomes the clearly legal bound of $O(n^3)$. But maybe what you're thinking only works for $k=O(1)$ or $k=o(n)$ (or even just $k < n$)?  

---

## 2 answers

### Answer by username_3 on 2012-03-08. Score: 2 | Accepted answer

There are clasical algorithms [[1]](http://en.wikipedia.org/wiki/Determinant#Further_methods), [[2]](http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra), [[3]](http://www.ams.org/journals/mcom/1974-28-125/S0025-5718-1974-0331751-8/home.html) to compute the determinant of a $k\times k$ matrix using $O(k^\omega)$ floating-point operations, where $O(k^\omega)$ is the number of operations that you need for matrix multiplication. Therefore, you can get a better bound
$$\textstyle O(\binom{n}{k}^2 k^\omega )$$
, which is the cost of computing all of them individually and listing. You can let $\omega=2.3727$. For implementations the Strassen algorithm is often used with has $\omega=2.807$.

In particular, the [third reference](http://www.ams.org/journals/mcom/1974-28-125/S0025-5718-1974-0331751-8/home.html) uses the Strassen algorithm, but explicitly mentions:

> In Section 5 we show that matrix multiplication, triangular factorization, and
> inversion are equivalent in computational complexity.

> **Comments:**
> **username_3**: That's *exactly* what I said.  
> **username_3**: My answer is algorithmic independent. The OP explicitly asked for some names of particular algorithm so I talked about Strassen because is practical for implementations.  

---

### Answer by username_2 on 2013-06-01. Score: 3

For $k=n-1$ you can do better than $O(\binom{n}{k}k^{\omega}) = O(n^{\omega+1})$ by taking advantage of the fact that the determinants of $k \times k$ minors are exactly the $(n-k)$-th order partial derivatives of the determinant of your matrix, and then applying Baur--Strassen.

Baur--Strassen says that if a function $f$ can be computed by an arithmetic circuit of size $s$, then there is a (multi-output) circuit of size $4s$ computing $(\partial f / \partial x\_1, \dotsc, \partial f / \partial x\_n)$. As the original determinant can be computed in time $O(n^\omega)$, the $(n-1) \times (n-1)$ minors can be computed using the above trick in time $O(4n^{\omega}) = O(n^{\omega})$, instead of $O(n^{\omega+1})$ the other way.

(I believe finding a useful extension of Baur--Strassen to higher partial derivatives is an open question.)


---

