Solver for uniform matroid isomorphism

Question

I want to solve the following coNP-complete problem efficiently in practice: Given a linear matroid represented as $k \times n$ matrix over a finite field $\mathbb{F}_p$ (where $p$ is large prime), test if the matroid is isomorphic to the uniform matroid with $n$ elements and rank $k$. In other words, test if all $k \times k$ submatrices have rank $k$.

Is there some algebraic software that can solve this problem potentially much faster than brute-force? In particular I am interested in methods that are able to beat the ${n\choose k}$ brute-force on at least some yes-instances.

I have tried reducing to integer programming and solving with CPLEX, but it is worse than brute-force already on two-digit primes.

Answer 1

You can get a square-root speed-up with a time-space tradeoff if you are working in $\mathbb{F}_2$.

The matrix $M$ is a no-instance iff there exists a non-zero vector $v$ of Hamming weight $\le k$ (i.e., with at most $k$ non-zero coordinates) such that $Mv=0$. This is equivalent to saying that there exist $t,u$ of Hamming weight $\le k/2$ such that $Mt=Mu$ (since then $M(t-u)=0$ and $t-u$ has Hamming weight $\le k$).

Now you can enumerate all such $t$ and store $Mt$ in a hashtable, and look for collisions (or, sort the values $Mt$ and look for repeats). This requires approximately ${n \choose k/2}$ time and space, which is better than your brute-force method. But again it only works over $\mathbb{F}_2$.

You can improve this a bit further as follows. Randomly partition the $n$ coordinates into two groups of $n/2$ coordinates, and restrict $t$ to be non-zero only on the first group (its zero on the second group), and $u$ to be non-zero only on the second group (it is zero on the first group). Then if such $v$ exists, with probability ${k \choose k/2}/2^k \approx 1/\sqrt{\pi k/2}$, there exist $t,u$ that satisfy this restriction. So, enumerate all such $t$, store $Mt$ in a hashtable, and for each $u$, look up $Mu$ in the hashtable (or, merge a sorted list of $Mt$ values and a sorted list of $Mu$ values). If you repeat $40 \sqrt{\pi k/2}$ times, with a different partition each time, then you'll have an overwhelming probability of finding a solution if one exists. This requires $40 \sqrt{\pi k/2} {n/2 \choose k/2}$ time and space, which is better than the above.

It's possible you might be able to apply other algorithms for finding a low-weight codeword in a linear code to this problem, if you are working in $\mathbb{F}_2$.

If you are working over $\mathbb{F}_p$ with $p>2$, then you can still do this method, and the running time will be something like $40 \sqrt{\pi k/2} {n/2 \choose k/2} (p-1)^{k/2}$ time and space. We can compare this to the brute-force approach of enumerating all subsets of $k$ of the columns, then using Gaussian elimination to compute its rank; that will have running time ${n \choose k} k^3$. The brute-force approach is better when $n/k \ll p$, and my approach is better when $n/k \gg p$.