Matroid representation
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.
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
is a finite set or multiset of vectors, and
is the family of linearly independent subsets of
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.
[4] 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.
, the Fano plane (a binary matroid with seven elements), or the dual matroid of the Fano plane as minors.
[5][7] Alternatively, a matroid is regular if and only if it can be represented by a totally unimodular matrix.
[8] 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.
[9] As of 2012, it has been proven only for fields of four or fewer elements.
[13] 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.
[14] The characteristic set of a linear matroid is defined as the set of characteristics of the fields over which it is linear.
[17] 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.
elements, and its independent sets consist of all subsets of up to
Uniform matroids may be represented by sets of vectors in general position in an
The field of representation must be large enough for there to exist
vectors in general position in this vector space, so uniform matroids are F-linear for all but finitely many fields F.[21] 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.[8] 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
[24] 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.
