# Complexity of determinant of k-minors

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.

-
Doesn't cofactor expansion and dynamic programming immediately give you $O(\binom{n}{k}^2 k)$ time? – Jeffε Mar 8 '12 at 17:50
@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 Jun 1 '13 at 3:45

There are clasical algorithms [1], [2], [3] 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 uses the Strassen algorithm, but explicitly mentions:

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

-
Bunch and Hopcroft result is well-known to reduce important linear algebra operations to $O(n^\omega)$ matrix multiplication time independently of Strassen or any specific matrix multiplication algorithm. – user17 Mar 13 '12 at 1:04
That's exactly what I said. – Juan Bermejo Vega Mar 13 '12 at 11:03
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 Mar 13 '12 at 11:06

Not quite answering what you want, but if you want the gcd of all $k\times k$ minors, then you can compute it in $O(n^\omega)$ or up to logarithmic factors. This is known as Smith Normal Form. For any matrix over principal ideal ring (or PID), the $k$ invariant factor of Smith normal form is the ${\rm gcd}$ of all $k\times k$ minors.

-
Nice, but this is of interest for integer matrices. The question in its current formulation seems to concern real matrices. – Juan Bermejo Vega Mar 13 '12 at 12:28
Also, it's not actually known how to compute Smith normal form in $O(n^\omega)$ or even $O(n^3)$ time. – Jeffε Jun 2 '13 at 3:27

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.)

-