Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Doesn't cofactor expansion and dynamic programming immediately give you $O(\binom{n}{k}^2 k)$ time? –  JɛffE 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
add comment

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer
1  
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
1  
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
add comment

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.

share|improve this answer
    
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
1  
Also, it's not actually known how to compute Smith normal form in $O(n^\omega)$ or even $O(n^3)$ time. –  JɛffE Jun 2 '13 at 3:27
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.