Complexity of determinant of k-minors

Question

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.

Answer 1

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.

Answer 2

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.

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