I am wondering what is the (computationally) best way to tell if a matroid of size $n$ and rank $r$ is binary(or whether it has a $U^2_4$ minor) given either one of these: 1) An independence oracle 2) Its rank vector 3) A basis oracle
I want to implement $U^2_4$/binary detection(Most likely given a basis oracle which will be in form of the reverse-lexicographic encoding in [3]).
What I know(or what I think I know):
1) can't be solved by asking polynomial number of questions to the oracle which is due to Seymour[1].
2) and 3) One can write a brute force implementation which would compute and check all minors of size 4.
Also, I considered following ideas:
a) For problem (3), given a matroid $M$ one can start with an $r\times r$ Identity matrix and assign its columns to elements of some basis say $B^*$. Now we expand this matrix by adding columns that correspond to $e\in E(M)\setminus B^*$. We now fill r entries in this new column with $0$ or $1$. For filling $i^{th}$ entry in the column, we ask the basis oracle if $(B^*\setminus i)\cup e$ is a basis. If it is, we put a $1$ in that entry, $0$ otherwise. When we are done constructing all $n-r$ columns this way we have the only binary matrix that correctly reflects if an $r$-subset S of $E(M)$ with $|S\cap B^*|=r-1$ is a basis or not. As for other $r$-subsets, we can test their rank in the matrix and ask basis oracle whether each of them is a basis. If the two results don't match for any $r$-subset, we conclude that the matroid is not binary representable. This way seems better than the brute-force 'compute and check all minors' in terms of complexity.
b) One can compute all $r-1$ flats of $M$ from bases(Using an algorithm again due to Seymour [2]). Then compute all $r-2$ flats. Then use scum theorem(i.e. check if any $r-2$ flat is contained in more than three $r-1$ flats).
EDIT Some extra info: Here is what I am really trying to do: Much on the lines of [3] and [4] I am trying to enumerate(list) matroids, but only the binary ones using single element extensions(by simply not extending any non-binary matroids produced). This list(scalar binary codes) and more lists created after pairing of bits(vector binary codes) are then to be used for computer assisted achievability proofs of rate regions of multisource network coding problems. Matsumoto [3] was very generous to share his c++ code which I am parallelizing using OpenMPI(My C $U^2_4$ check which is currently brute-force seamlessly goes into this scheme). Since the binary matroids are so less in number[5] compared to all matroids, I am expecting to go much farther. I have to care about computational efficiency because there are millions of matroids to be tested just at ground set size 14.
Given all this, although I appreciate and have been following sage-matroid library, I am not much of a Python guy I am not very sure how sage's code will go into my OpenMPI-C++ code(well, I won't exclude the possibility of existence of some hack that will let me do this). Hence, what I am looking for is pointers to best algorithms around which Dr. Royle's answer does tell.
[1] Seymour, P. D.; Walton, P. N. (1981), "Detecting matroid minors", Journal of the London Mathematical Society, Second Series 23 (2): 193–203
[2] P.D. Seymour, A Note on Hyperplane Generation, Journal of Combinatorial Theory, Series B, Volume 61, Issue 1, May 1994, Pages 88-91
[3] Yoshitake Matsumoto, Sonoko Moriyama, Hiroshi Imai, and David Bremner. Matroid enumeration for incidence geometry. Discrete & Computational Geometry, 47(1):17–43, 2012
[4] Dillon Mayhew and Gordon F. Royle. Matroids with nine elements. Journal of Combinatorial Theory, Series B, 98(2):415 – 431, 2008
[5] Marcel Wild: The Asymptotic Number of Binary Codes and Binary Matroids. SIAM J. Discrete Math. 19(3): 691-699 (2005)
