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 formula_1 is defined by a finite set formula_2 (the elements of the matroid) and a non-empty family formula_3 of the subsets of formula_2, 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 formula_5 is larger than a second independent set formula_6 then there exists an element formula_7 that can be added to formula_6 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 formula_2 is a finite set or multiset of vectors, and formula_3 is the family of linearly independent subsets of formula_2, then formula_1 is a matroid.
More generally, if formula_1 is any matroid, then a representation of formula_1 may be defined as a function formula_15 that maps formula_2 to a vector space formula_17, with the property that a subset formula_5 of formula_2 is independent if and only if formula_20 is injective and formula_21 is linearly independent. A matroid with a representation is called a linear matroid, and if formula_17 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 formula_15 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.
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 formula_24 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 formula_24, 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 formula_26 has formula_27 elements, and its independent sets consist of all subsets of up to formula_28 of the elements. Uniform matroids may be represented by sets of vectors in general position in an formula_28-dimensional vector space. The field of representation must be large enough for there to exist formula_27 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 formula_31-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 formula_27 elements may be represented over every field that has at least formula_33 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.
References.
 ;templatestyles src="Reflist/styles.css" / ;