Matroid representation

Short description: Vectors with given pattern of independence

In the mathematical theory of matroids, a matroid representation is a family of vectors whose linear independence relation is the same as that of a given matroid. Matroid representations are analogous to group representations; both types of representation provide abstract algebraic structures (matroids and groups respectively) with concrete descriptions in terms of linear algebra.

A linear matroid is a matroid that has a representation, and an F-linear matroid (for a field F) is a matroid that has a representation using a vector space over F. Matroid representation theory studies the existence of representations and the properties of linear matroids.

Definitions

A (finite) matroid [math]\displaystyle{ (E,\mathcal{I}) }[/math] is defined by a finite set [math]\displaystyle{ E }[/math] (the elements of the matroid) and a non-empty family [math]\displaystyle{ \mathcal{I} }[/math] of the subsets of [math]\displaystyle{ E }[/math], called the independent sets of the matroid. It is required to satisfy the properties that every subset of an independent set is itself independent, and that if one independent set [math]\displaystyle{ A }[/math] is larger than a second independent set [math]\displaystyle{ B }[/math] then there exists an element [math]\displaystyle{ x\in A\setminus B }[/math] that can be added to [math]\displaystyle{ B }[/math] to form a larger independent set. One of the key motivating examples in the formulation of matroids was the notion of linear independence of vectors in a vector space: if [math]\displaystyle{ E }[/math] is a finite set or multiset of vectors, and [math]\displaystyle{ \mathcal{I} }[/math] is the family of linearly independent subsets of [math]\displaystyle{ E }[/math], then [math]\displaystyle{ (E,\mathcal{I}) }[/math] is a matroid.

More generally, if [math]\displaystyle{ (E,\mathcal{I}) }[/math] is any matroid, then a representation of [math]\displaystyle{ (E,\mathcal{I}) }[/math] may be defined as a function [math]\displaystyle{ f }[/math] that maps [math]\displaystyle{ E }[/math] to a vector space [math]\displaystyle{ V }[/math], with the property that a subset [math]\displaystyle{ A }[/math] of [math]\displaystyle{ E }[/math] is independent if and only if [math]\displaystyle{ f|_A }[/math] is injective and [math]\displaystyle{ f(A) }[/math] is linearly independent. A matroid with a representation is called a linear matroid, and if [math]\displaystyle{ V }[/math] is a vector space over field F then the matroid is called an F-linear matroid. Thus, the linear matroids are exactly the matroids that are isomorphic to the matroids defined from sets or multisets of vectors. The function [math]\displaystyle{ f }[/math] will be one-to-one if and only if the underlying matroid is simple (having no two-element dependent sets). Matroid representations may also be described more concretely using matrices over a field F, with one column per matroid element and with a set of elements being independent in the matroid if and only if the corresponding set of matrix columns is linearly independent. The rank function of a linear matroid is given by the matrix rank of submatrices of this matrix, or equivalently by the dimension of the linear span of subsets of vectors.

Characterization of linear matroids

The Vámos matroid, not linear over any field

The Perles configuration, linear over the reals but not the rationals

Not every matroid is linear; the eight-element Vámos matroid is one of the smallest matroids that is unrepresentable over all fields. If a matroid is linear, it may be representable over some but not all fields. For instance, the nine-element rank-three matroid defined by the Perles configuration is representable over the real numbers but not over the rational numbers.

Binary matroids are the matroids that can be represented over the finite field GF(2); they are exactly the matroids that do not have the uniform matroid [math]\displaystyle{ U{}^2_4 }[/math] as a minor. The unimodular or regular matroids are the matroids that can be represented over all fields; they can be characterized as the matroids that have none of [math]\displaystyle{ U{}^2_4 }[/math], the Fano plane (a binary matroid with seven elements), or the dual matroid of the Fano plane as minors. Alternatively, a matroid is regular if and only if it can be represented by a totally unimodular matrix.

Rota's conjecture states that, for every finite field F, the F-linear matroids can be characterized by a finite set of forbidden minors, similar to the characterizations described above for the binary and regular matroids. As of 2012, it has been proven only for fields of four or fewer elements. For infinite fields (such as the field of the real numbers) no such characterization is possible.

Field of definition

For every algebraic number field and every finite field F there is a matroid M for which F is the minimal subfield of its algebraic closure over which M can be represented: M can be taken to be of rank 3.

Characteristic set

The characteristic set of a linear matroid is defined as the set of characteristics of the fields over which it is linear. For every prime number p there exist infinitely many matroids whose characteristic set is the singleton set {p}, and for every finite set of prime numbers there exists a matroid whose characteristic set is the given finite set.

If the characteristic set of a matroid is infinite, it contains zero; and if it contains zero then it contains all but finitely many primes. Hence the only possible characteristic sets are finite sets not containing zero, and cofinite sets containing zero. Indeed, all such sets do occur.

Related classes of matroids

A uniform matroid [math]\displaystyle{ U{}^r_n }[/math] has [math]\displaystyle{ n }[/math] elements, and its independent sets consist of all subsets of up to [math]\displaystyle{ r }[/math] of the elements. Uniform matroids may be represented by sets of vectors in general position in an [math]\displaystyle{ r }[/math]-dimensional vector space. The field of representation must be large enough for there to exist [math]\displaystyle{ n }[/math] vectors in general position in this vector space, so uniform matroids are F-linear for all but finitely many fields F. The same is true for the partition matroids, the direct sums of the uniform matroids, as the direct sum of any two F-linear matroids is itself F-linear.

A graphic matroid is the matroid defined from the edges of an undirected graph by defining a set of edges to be independent if and only if it does not contain a cycle. Every graphic matroid is regular, and thus is F-linear for every field F.

The rigidity matroids describe the degrees of freedom of mechanical linkages formed by rigid bars connected at their ends by flexible hinges. A linkage of this type may be described as a graph, with an edge for each bar and a vertex for each hinge, and for one-dimensional linkages the rigidity matroids are exactly the graphic matroids. Higher-dimensional rigidity matroids may be defined using matrices of real numbers with a structure similar to that of the incidence matrix of the underlying graph, and hence are [math]\displaystyle{ \mathbb{R} }[/math]-linear.

Like uniform matroids and partition matroids, the gammoids, matroids representing reachability in directed graphs, are linear over every sufficiently large field. More specifically, a gammoid with [math]\displaystyle{ n }[/math] elements may be represented over every field that has at least [math]\displaystyle{ 2^n }[/math] elements.

The algebraic matroids are matroids defined from sets of elements of a field extension using the notion of algebraic independence. Every linear matroid is algebraic, and for fields of characteristic zero (such as the real numbers) linear and algebraic matroids coincide, but for other fields there may exist algebraic matroids that are not linear.