Looking back over the series of all posts so far on infinite matroids, you might notice (as I did) that there is a central theme which has not yet been covered: that of representability. What should it mean for an infinite matroid to be representable over a field $k$? In this post we will explore a few ideas for how one could try to define this. It will be a fraught journey, with some false starts and paths that get lost in rocky ground, but eventually we will arrive at a satisfying definition.

The obvious thing to try is to just define representability of infinite matroids the same way we define it for finite matroids: take a set $E$ of vectors in some vector space $V$ over $k$, and say that a subset of $E$ is independent if it is linearly independent in $V$. If $E$ is infinite then we have an infinite matroid, and such matroids should certainly count as representable over $k$.

Unfortunately this definition doesn’t cover all the examples of matroids which ought to be representable. For example, in this post we saw a bunch of examples that look like infinite graphic matroids, and graphic matroids should be representable over every field. But these examples are not covered by the definition above. Nor are the examples from this post. Why not? A set of vectors is linearly independent as soon as all of its finite subsets are, so all the circuits of these matroids will necessarily be finite. In other words, all these matroids are finitary.

This might remind of you of the issues which got this whole series of posts started, here and here. It is easy to find axioms for the collection of finitary infinite matroids, but that doesn’t include all the examples of things that look like infinite matroids, and in particular the collection of finitary matroids is not closed under duality. Finding natural axioms for a class of infinite matroids closed under duality was a much trickier problem. Now we are running into exactly the same problem with representability. Not only have we failed to cover the important examples, this definition of representability is not even closed under duality.

Still, we have made some progress. We have identified which finitary matroids should count as representable over $k$, and so whatever our definition turns out to be it should give this collection of matroids as the finitary representable matroids. Since cofinitary matroids are just the duals of finitary matroids, we have also identified which cofinitary matroids should count as representable over $k$, namely the duals of these finitary representable matroids. Taking the union of these two classes would give a class of matroids closed under duality, but this is pretty crude and still doesn’t cover some of the interesting examples.

We need a way to allow infinite linear combinations of our vectors. One natural idea, which quickly turns out to be a dead end, is to use the infinite sums defined in Hilbert spaces (the notion of independence given this way does not give rise to a matroid). A more fertile approach was found by Bruhn and Georgakopoulos [4]. You can understand the basic idea by considering the following list of vectors in $\mathbb{R}^{\mathbb{N}}$:

$$\begin{array}{rrrrrrrrr}(&1,&0,&0,&0,&0,&0,&\ldots&)\\(&-1,&1,&0,&0,&0,&0,&\ldots&)\\(&0,&-1,&1,&0,&0,&0,&\ldots&)\\(&0,&0,&-1,&1,&0,&0,&\ldots&)\\(&0,&0,&0,&-1,&1,&0,&\ldots&)\\&&&\vdots&&&&&\end{array}$$

Although this list is infinite, if we pick any particular column and take the sum of the entries in that column it evaluates to 0. So there is a sense in which this infinite list of vectors sums to 0. More precisely, given a set $I$, we can consider the vector space $k^I$ of functions from $I$ to $k$. Then we say that a set $U$ of vectors in $k^I$ is thinly dependent if we can find coefficients $\lambda_u \in k$ for each $u \in U$, not all zero, such that for any $i \in I$ we have $$\sum_{u \in U} \lambda_u u(i) = 0\,.$$ There is of course the problem that some of these sums might not be defined, in that they might have infinitely many nonzero summands. We say that $U$ is thin if such sums are necessarily well-defined, that is, if for each $i \in I$ there are only finitely many $u \in U$ with $u(i) \neq 0$.

This suggests a new idea for how to define representable matroids. We take the ground set $E$ to be a thin set of vectors in $k^I$, and as dependent sets we take the thinly dependent subsets of $E$. The matroids we get this way need not be finitary, but now we have some new problems. A typical set of vectors in $k^I$ will not be thin, so it isn’t clear that all of the finitary representable matroids we saw above can be presented in this way. And in fact they cannot! Together with Afzali, I showed in [1] that all such matroids are cofinitary, and in fact they are exactly the duals of the finitary representable matroids.

So now we understand representability for finitary and for cofinitary matroids. To make any more progress we need to find a way to squeeze more juice out of the idea of thin dependency. The reason we took $E$ to be a thin family above was to ensure that thin dependency would always be defined for subsets of $E$, but we could drop that requirement if we take more care in our notion of dependency. More precisely, we take as our ground set $E$ any set of vectors in $k^I$, and we say that a subset $X$ of $E$ is dependent if it has a subset $Y$ which is thinly dependent (here $Y$ must be thin, even if $X$ need not be). Matroids arising in this way are called thin sums matroids.

This now includes all the cofinitary representable matroids, and it also includes all the finitary representable matroids (that’s less obvious, but it was shown in [1]). What’s more, it includes all the examples of things we wanted to be representable matroids. But there are some new problems. The systems of dependent sets defined in this way are not always matroids [1]. Even if they are matroids, their duals are not always thin sums representable [2]. Closure under duality is one of the main things we should hope for from a definition of representability. It seems we have hit a dead end.

However, there is a way forward. All of the examples that we cared about, and wanted to cover with our definition of representable matroids, had the property that they were tame, meaning that any intersection of a circuit with a cocircuit is finite. On the other hand, the bad examples where duality breaks down are not tame, but wild. This distinction was already discussed in an earlier post of the series. So we should restrict our attention to tame matroids.

And there we have it: we say that a matroid is representable over $k$ if it is tame and is a thin sums matroid over $k$. Suddenly, magically, everything works. This class is closed under duality [1]. All of the motivating examples are covered. Even better, all the usual theory of representable matroids can be extended to infinite representable matroids. For example, the various standard characterisations of binary and ternary matroids still work in this setting, including the characterisations via excluded minors [3].

Indeed, there is a very general principle which allows the lifting of excluded minor characterisations from finite to infinite matroids. For any finite field $k$, a tame infinite matroid $M$ is representable over $k$ precisely when all of its finite minors are [3]. This principle allows us to lift all kinds of other statements easily from finite to infinite matroids. For example, an infinite matroid which is representable over both $GF(3)$ and $GF(5)$ is necessarily representable over $GF(p)$ for all primes $p$ (since all its finite minors are). 

For those readers who have come across partial fields and tracts, that last statement might have got you wondering whether we can define representations of infinite matroids over those objects, in the spirit of this post. For example, what might it mean for an infinite matroid to be orientable? This is a thorny problem, which will have to wait for a future post.

Although we now have a good definition of representability, there is one open problem in this area that has been nagging at me for years. Binary matroids can be defined as tame matroids with no $U_{2,4}$-minor. But do we really need to impose the condition of tameness here? To put it another way, must every wild matroid have a $U_{2,4}$-minor? All the examples we know of do.

[1] S. Hadi Afzali Borujeni and Nathan Bowler, Thin sums matroids and duality, Advances in Mathematics, Volume 271, 2015, Pages 1-29.
[2] Nathan Bowler and Johannes Carmesin, Matroids with an infinite circuit–cocircuit intersection, Journal of Combinatorial Theory, Series B, Volume 107, 2014, Pages 78-91.
[3] Nathan Bowler and Johannes Carmesin, An excluded minors method for infinite matroids, Journal of Combinatorial Theory, Series B, Volume 128, 2018, Pages 104-113
[4] Henning Bruhn and Agelos Georgakopoulos, Bases and closures under infinite sums, Linear Algebra and its Applications, Volume 435, Issue 8, 2011, Pages 2007-2018.