I attended a talk which generalized matroid realizability over a field to matroid realizability over division rings, and showed that the question of realizability is undecidable. However, they used a word problem arising from the division ring.


Is it known whether the question of "Is a matroid M realizable over any field F" is computable?


It seems to me that it shouldn't be, because they you would have a prover of all theorems akin to the Pappus theorem, but that's just my intuition.



Is matroid realizability computable?
Contra my suspicions, the Internet is telling me that Vámos proved in "A necessary and sufficient condition for a matroid to be linear" (citation below) that it is decidable if a matroid is representable over a field. See quote on pg. 3 of [Solving Rota’s Conjecture](https://homepages.ecs.vuw.ac.nz/~whittle/pubs/solving-rotas-conjecture.pdf) which says "The first exception is the algorithmic problem of determining when a given matroid is representable over an unspecified field, which was proved to be decidable by Vámos [28]."


*Vamos, P.*, A necessary and sufficient condition for a matroid to be linear, Möbius Algebras, Conf. Proc. Waterloo 1971, 162-169 (1975). [ZBL0374.05017](https://zbmath.org/?q=an:0374.05017).


**EDIT**:


Since the Vámos reference seems hard to track down, let me quote from the MathReviews [MR0349447] by J. E. Graver, which gives more details about the result:



> 
> The author gives a necessary and sufficient condition for a matroid to be $f$-linear, i.e., representable over some field. Let $E$ be a set and $\scr{E}$ a collection of subsets of $E$ satisfying the conditions for the independent sets of a matroid on $E$. We denote this matroid by the pair $(E,\mathscr{E})$. Fix $B\in \mathscr{E}$, a basis for the matroid. For each $x\in E$ define $S(a)$ as follows: $S(a)=\varnothing$ if $\{a\}\notin \mathscr{E}$; $S(a)=\{a\}$ if $a\in B$; otherwise $S(a)$ is the unique subset of $B$ such that $S(a)∪\{a\}$ is a circuit. Let $\Gamma=\{(a,b):a\in E,b\in S(a)\}$, and consider $R=Z[X\_{\gamma}]$, the ring of polynomials over the integers in variables $\{X\_\gamma: \gamma \in \Gamma\}$. A finite subset $A \subseteq E$ is said to be regular if $|A|=|\bigcup\_{a \in A}S(a)|$. For each regular set $A$ a polynomial in $R$ is constructed as follows: Let $r\_{(a,b)}=X\_{(a,b)}$ if $a \in A$ and $b \in S(a)$, and $r\_{(a,b)}=0$ if $a\in A$ and $b\in A−S(a)$. Ordering the elements of $A$, constructing the $|A|\times |A|$ matrix $[r\_{(a,b)}]$ and taking the determinant yield a polynomial $P(A)$, unique up to sign. However, the ideal $I$ generated by $\{P(A):\textrm{$A$ is regular}, A\notin \mathscr{E}\}$ and the multiplicatively closed set $T$ generated by $\{P(A):\textrm{$A$ is regular}, A\in \mathscr{E}\}$ are uniquely determined. We may now state the main result. Theorem: The matroid $E, \mathscr{E}$ is $f$-linear if and only if $T\cap I=\varnothing$.
> 
> 
> 


Note that in the review there is a confusing typo where it describes $T$ as generated by $\{P(A):\textrm{$A$ is regular}, A\notin \mathscr{E}\}$ rather than $\{P(A):\textrm{$A$ is regular}, A\in \mathscr{E}\}$. Note also, as pointed out in the comments by Geva Yashfe, that this result appears as Theorem 6.8.9 in the 2nd edition of Oxley's Matroid Theory text, which is probably a more accessible source. To deduce decidability from this algebraic crieterion, Oxley appeals to Gröbner basis theory.


