# 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? – JɛﬀE Mar 8 '12 at 17:50

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