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 ( E , I ) {\displaystyle (E,{\mathcal {I}})} is defined by a finite set E {\displaystyle E} (the elements of the matroid) and a non-empty family I {\displaystyle {\mathcal {I}}} of the subsets of E {\displaystyle E} , 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 A {\displaystyle A} is larger than a second independent set B {\displaystyle B} then there exists an element x ∈ A ∖ B {\displaystyle x\in A\setminus B} that can be added to B {\displaystyle B} 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 E {\displaystyle E} is a finite set or multiset of vectors, and I {\displaystyle {\mathcal {I}}} is the family of linearly independent subsets of E {\displaystyle E} , then ( E , I ) {\displaystyle (E,{\mathcal {I}})} is a matroid. More generally, if ( E , I ) {\displaystyle (E,{\mathcal {I}})} is any matroid, then a representation of ( E , I ) {\displaystyle (E,{\mathcal {I}})} may be defined as a function f {\displaystyle f} that maps E {\displaystyle E} to a vector space V {\displaystyle V} , with the property that a subset A {\displaystyle A} of E {\displaystyle E} is independent if and only if f | A {\displaystyle f|_{A}} is injective and f ( A ) {\displaystyle f(A)} is linearly independent. A matroid with a representation is called a linear matroid, and if V {\displaystyle V} 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 f {\displaystyle f} 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 U
4 2 {\displaystyle U{}_{4}^{2}} 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 U
4 2 {\displaystyle U{}_{4}^{2}} , 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.
… excerpt ends here. Continue reading the full article.
