# Solver for uniform matroid isomorphism

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.

• Do you want worst-case, or just in practice? Brute force is ~$\binom{n}{k}$, and UMI is W-hard when parametrized by k (see eg paragraph before Thm 4 here, so while you might be able to do better than brute force, there's unlikely to be an algorithm that completely pulls k out of the exponent (unless W=FPT). – Joshua Grochow Mar 31 at 3:49
• Just in practice. To me it seems quite difficult to beat ${n}\choose{k}$ even in the best case if the answer is yes. Also thanks for the reference, I hadn't seen that before. – Laakeri Mar 31 at 5:12

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

• Thanks, but I'm afraid that the case of $\mathbb{F}_2$ is not relevant to me. In particular the problem is originally over rationals, but to avoid big numbers I work on $\mathbb{F}_p$ for a randomly chosen large prime $p$. (I hope that this does not make the problem harder.) I'll look into SVP. – Laakeri Mar 31 at 8:15
• @Laakeri, OK, sorry about that. I'll delete this answer shortly. On further reflection, I doubt SVP is going to be useful. – D.W. Mar 31 at 8:47
• What goes wrong if you try to do your first trick over Fp? Seems to work in time and space roughly $\binom{n}{k/2}p^{k/2}$. – Joshua Grochow Apr 1 at 5:21
• @JoshuaGrochow, good point. I've updated the answer with that idea. I doubt it will be useful unless $p$ is small, but who knows. – D.W. Apr 1 at 6:08