Let $\mathcal{M}$ be a rank-$d$ matroid on $[n]$. Say a matroid $\mathcal{N}$ is a *relaxation* of $\mathcal{M}$ if $\mathrm{rank}(\mathcal{N})=d$, $\mathrm{groundset}(\mathcal{N})=[n]$, and every independent set of $\mathcal{M}$ is an independent set of $\mathcal{N}$ (observe that this notion of relaxation is in the labeled sense).



> 
> Has anyone seen the set of all relaxations of $\mathcal{M}$ naturally show up in some context? 
> 
> 
> 


I'm particularly interested in the algorithmic task of listing all relaxations of a given matroid $\mathcal{M}$, and in any heuristic to make an implementation more efficient than performing the enumeration by brute force; it would be even better if such an implementation already exists.


Actually, I only care about those relaxations of $\mathcal{M}$ that are realizable over a fixed field, say $\mathbb{C}$, which brings me to the next question:



> 
> Does anyone know of an implementation of a (finite) algorithm that decides whether a matroid is representable and provides a representation in case it is? (that such a finite algorithm exists can be proved using Groebner bases) 
> 
> 
> 


Here I'm explicitly disregarding any complexity issues; I just want to be able to do compute a realization for some small matroids.


**Note:** the first question is different from the "opposite" one of listing all matroids that *specialize* a fixed matroid, which has been asked [here](https://mathoverflow.net/questions/107138/finding-the-matroids-with-a-specified-set-of-non-bases). I wonder how different the task of listing all relaxations is.




---


**Update:** I implemented the following brute-force algorithm in sage to enumerate the relaxations of a rank-$d$ matroid on $[n]$:


`For every subset` $\mathcal{F}$ `of the nonbases of` $\mathcal{M}$, `check whether` $bases(\mathcal{M})\cup \mathcal{F}$`is the collection of bases of a matroid.`


According to sage's method `.is_valid()` for matroids, the outcome for all the matroids I tested was that all $2^{\#\{nonbases(\mathcal{M})\}}$ subsets of $\binom{[n]}{d}$ obtained form the bases of a matroid, which wasn't what I expected.



> 
> Can it be that there's a bug in sage's `.is_valid()` method, or is it actually to be expected that most naive relaxations of a matroid (as enumerated above) are actually matroids?
> 
> 
> 


(the reward is independent from the update in the question)



Matroids relaxations of a given matroid
You are describing what are usually called "weak maps" between matroids.


So a bijection $\varphi: E(\mathcal{N}) \to E(\mathcal{M})$ is called a *weak map* if for every independent set $I$ of $\mathcal{M}$ the inverse image $\varphi^{-1}(I)$ is independent in $\mathcal{N}$. In your case, you are asking when the *identity function* is a weak map, which just requires every independent set of $\mathcal{M}$ to be independent in $\mathcal{N}$. 


There is lots of stuff known about weak maps (and strong maps) and other things. Given a bunch of matroids on the same ground set, the weak-map relation is a partial order. The best place to start is around page 280 of the second edition of Oxley's book *Matroid Theory*, which refers to the original papers.


The "minimal" relaxation that can be done is to take a single non-basis $N$ of $\mathcal{M}$ and form a matroid whose bases are ${\mathrm{bases}} (\mathcal{M}) \cup \{N\}$. This will work if (and, I think, only if) $N$ is a circuit-hyperplane of $\mathcal{M}$. 


So you certainly *do not* expect all of your relaxations to pass Sage's `is_valid` routine.


In fact, I wanted to do a test to convince myself that it was working ok, so I ran the following code, just testing all the relaxations of a single randomly chosen matroid (in this case the matroid called `J`). All this does is create an array of matroids, each of which are specified by their bases, for which I am using the bases of `J` together with one of the non-bases. Then I ask `is_valid()` which of those matroids are valid.



```
m = matroids.named_matroids.J()
bases = [x for x in m.bases()]
nonbases = [x for x in m.nonbases()]
circuithyps = [x for x in m.circuits() if x in m.hyperplanes()]
tstsets = [bases + [nonbases[i]] for i in [0..len(nonbases)-1]]
tstmats = [Matroid(x) for x in tstsets]
tstcheck = [m.is_valid() for m in tstmats]
tstcheck

```

and I obtained the following result:



```
[True, False, False, False, False, False, False, False, False, False, False, False, False, True, False, False, False, False, False, False]

```

which when we check the number of circuit-hyperplanes, is exactly what we expected.



```
[frozenset(['c', 'b', 'e', 'd']), frozenset(['h', 'e', 'g', 'f'])]

```

You should let us see the code that you used that produced the incorrect answers, so we can tell whether it is a Sage bug, a sage.matroids bug, or user-error!


Finally, Stefan van Zwam has written a Mathematica program using Groebner bases to determine whether a matroid is representable, but the problem is hard unless you only want to know about matroids with less than 10 elements. I am not sure if he intends to add it to the Sage code-base or whether he even has it still. Ask him: `https://www.math.lsu.edu/~svanzwam/programming.html`


