<p>You can get a square-root speed-up with a time-space tradeoff if you are working in <span class="math-container">$\mathbb{F}_2$</span>.</p>
<p>The matrix <span class="math-container">$M$</span> is a no-instance iff there exists a non-zero vector <span class="math-container">$v$</span> of Hamming weight <span class="math-container">$\le k$</span> (i.e., with at most <span class="math-container">$k$</span> non-zero coordinates) such that <span class="math-container">$Mv=0$</span>.  This is equivalent to saying that there exist <span class="math-container">$t,u$</span> of Hamming weight <span class="math-container">$\le k/2$</span> such that <span class="math-container">$Mt=Mu$</span> (since then <span class="math-container">$M(t-u)=0$</span> and <span class="math-container">$t-u$</span> has Hamming weight <span class="math-container">$\le k$</span>).</p>
<p>Now you can enumerate all such <span class="math-container">$t$</span> and store <span class="math-container">$Mt$</span> in a hashtable, and look for collisions (or, sort the values <span class="math-container">$Mt$</span> and look for repeats).  This requires approximately <span class="math-container">${n \choose k/2}$</span> time and space, which is better than your brute-force method.  But again it only works over <span class="math-container">$\mathbb{F}_2$</span>.</p>
<p>You can improve this a bit further as follows.  Randomly partition the <span class="math-container">$n$</span> coordinates into two groups of <span class="math-container">$n/2$</span> coordinates, and restrict <span class="math-container">$t$</span> to be non-zero only on the first group (its zero on the second group), and <span class="math-container">$u$</span> to be non-zero only on the second group (it is zero on the first group).  Then if such <span class="math-container">$v$</span> exists, with probability <span class="math-container">${k \choose k/2}/2^k \approx 1/\sqrt{\pi k/2}$</span>, there exist <span class="math-container">$t,u$</span> that satisfy this restriction.  So, enumerate all such <span class="math-container">$t$</span>, store <span class="math-container">$Mt$</span> in a hashtable, and for each <span class="math-container">$u$</span>, look up <span class="math-container">$Mu$</span> in the hashtable (or, merge a sorted list of <span class="math-container">$Mt$</span> values and a sorted list of <span class="math-container">$Mu$</span> values).  If you repeat <span class="math-container">$40 \sqrt{\pi k/2}$</span> times, with a different partition each time, then you'll have an overwhelming probability of finding a solution if one exists.
This requires <span class="math-container">$40 \sqrt{\pi k/2} {n/2 \choose k/2}$</span> time and space, which is better than the above.</p>
<p>It's possible you might be able to apply other algorithms for <a href="https://decodingchallenge.org/low-weight" rel="nofollow noreferrer">finding a low-weight codeword in a linear code</a> to this problem, if you are working in <span class="math-container">$\mathbb{F}_2$</span>.</p>
<p>If you are working over <span class="math-container">$\mathbb{F}_p$</span> with <span class="math-container">$p&gt;2$</span>, then you can still do this method, and the running time will be something like <span class="math-container">$40 \sqrt{\pi k/2} {n/2 \choose k/2} (p-1)^{k/2}$</span> time and space.  We can compare this to the brute-force approach of enumerating all subsets of <span class="math-container">$k$</span> of the columns, then using Gaussian elimination to compute its rank; that will have running time <span class="math-container">${n \choose k} k^3$</span>.  The brute-force approach is better when <span class="math-container">$n/k \ll p$</span>, and my approach is better when <span class="math-container">$n/k \gg p$</span>.</p>

CC BY-SA 4.0
2021-03-31T08:15:04.097Z
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
CC BY-SA 4.0
2021-03-31T08:47:37.160Z
@Laakeri, OK, sorry about that.  I'll delete this answer shortly.  On further reflection, I doubt SVP is going to be useful.
D.W.
CC BY-SA 4.0
2021-04-01T05:21:51.707Z
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
CC BY-SA 4.0
2021-04-01T06:08:22.887Z
@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.
CC BY-SA 4.0
2021-03-31T07:45:11.347Z
2021-04-01T06:08:06.763Z
2021-04-01T06:08:06.763Z
D.W.
<p>I want to solve the following coNP-complete problem efficiently in practice: Given a linear matroid represented as <span class="math-container">$k \times n$</span> matrix over a finite field <span class="math-container">$\mathbb{F}_p$</span> (where <span class="math-container">$p$</span> is large prime), test if the matroid is isomorphic to the uniform matroid with <span class="math-container">$n$</span> elements and rank <span class="math-container">$k$</span>. In other words, test if all <span class="math-container">$k \times k$</span> submatrices have rank <span class="math-container">$k$</span>.</p>
<p>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 <span class="math-container">${n\choose k}$</span> brute-force on at least some yes-instances.</p>
<p>I have tried reducing to integer programming and solving with CPLEX, but it is worse than brute-force already on two-digit primes.</p>

CC BY-SA 4.0
2021-03-31T03:49:44.680Z
Do you want worst-case, or just in practice? Brute force is ~$\binom{n}{k}$, and UMI is W[1]-hard when parametrized by k (see eg paragraph before Thm 4 [here](https://doi.org/10.1007/978-3-319-21840-3_47), 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[1]=FPT).
Joshua Grochow
CC BY-SA 4.0
2021-03-31T05:12:41.243Z
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
CC BY-SA 4.0
2021-05-28T09:36:11.440Z
On further reflection, maybe an interesting way to frame this as a completely theoretical question would be to ask if we can solve isomorphism to $U_{2n,n}$ in time $O(1.999^n)$, or would it violate SETH?
Laakeri
CC BY-SA 4.0
2021-05-28T14:30:21.700Z
Interesting Q. But if you're interested in practice, one of the key things to take advantage of is that practical cases often aren't the worst cases.
Joshua Grochow
<linear-algebra><matrices><software>
Solver for uniform matroid isomorphism
Laakeri
# Solver for uniform matroid isomorphism

(Asked by: username_0 on 2021-03-30)

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.

**Tags:** linear-algebra, matrices, software
> **Comments:**
> **username_1**: Do you want worst-case, or just in practice? Brute force is ~$\binom{n}{k}$, and UMI is W[1]-hard when parametrized by k (see eg paragraph before Thm 4 [here](https://doi.org/10.1007/978-3-319-21840-3_47), 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[1]=FPT).  
> **username_0**: 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.  
> **username_0**: On further reflection, maybe an interesting way to frame this as a completely theoretical question would be to ask if we can solve isomorphism to $U_{2n,n}$ in time $O(1.999^n)$, or would it violate SETH?  
> **username_1**: Interesting Q. But if you're interested in practice, one of the key things to take advantage of is that practical cases often aren't the worst cases.  

---

## 1 answers

### Answer by username_2 on 2021-03-31. Score: 2

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](https://decodingchallenge.org/low-weight) 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$.

> **Comments:**
> **username_0**: 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.  
> **username_2**: @Laakeri, OK, sorry about that.  I'll delete this answer shortly.  On further reflection, I doubt SVP is going to be useful.  
> **username_1**: 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}$.  
> **username_2**: @JoshuaGrochow, good point.  I've updated the answer with that idea.  I doubt it will be useful unless $p$ is small, but who knows.  

---

