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 representation
In the mathematical field of representation theory, group representations describe abstract groups in terms of bijective linear transformations of a vector space to itself (i.e. vector space automorphisms); in particular, they can be used ...
s; both types of representation provide abstract algebraic structures (matroids and groups respectively) with concrete descriptions in terms of
linear algebra
Linear algebra is the branch of mathematics concerning linear equations such as:
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as:
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matrice ...
.
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
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called ''scalars''. Scalars are often real numbers, but can ...
over ''F''. Matroid representation theory studies the existence of representations and the properties of linear matroids.
Definitions
A (finite)
matroid is defined by a
finite set
In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,
:\
is a finite set with five elements. T ...
(the elements of the matroid) and a non-empty
family
Family (from la, familia) is a group of people related either by consanguinity (by recognized birth) or affinity (by marriage or other relationship). The purpose of the family is to maintain the well-being of its members and of society. Idea ...
of the subsets of
, 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
is larger than a second independent set
then there exists an element
that can be added to
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
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called ''scalars''. Scalars are often real numbers, but can ...
: if
is a finite set or multiset of vectors, and
is the family of linearly independent subsets of
, then
is a matroid.
More generally, if
is any matroid, then a representation of
may be defined as a function
that maps
to a vector space
, with the property that a subset
of
is independent if and only if
is injective and
is linearly independent. A matroid with a representation is called a linear matroid, and if
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
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word i ...
to the matroids defined from sets or multisets of vectors. The function
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
In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it. Thus, a line has a dimension of one (1D) because only one coord ...
of the
linear span
In mathematics, the linear span (also called the linear hull or just span) of a set of vectors (from a vector space), denoted , pp. 29-30, §§ 2.5, 2.8 is defined as the set of all linear combinations of the vectors in . It can be characterized ...
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
In geometry, the Perles configuration is a system of nine points and nine lines in the Euclidean plane for which every combinatorially equivalent realization has at least one irrational number as one of its coordinates. It can be constructed from ...
is representable over the
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
s but not over the
rational number
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ra ...
s.
Binary matroids are the matroids that can be represented over the
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
GF(2)
(also denoted \mathbb F_2, or \mathbb Z/2\mathbb Z) is the finite field of two elements (GF is the initialism of ''Galois field'', another name for finite fields). Notations and \mathbb Z_2 may be encountered although they can be confused wit ...
; they are exactly the matroids that do not have the
uniform matroid
In mathematics, a uniform matroid is a matroid in which the independent sets are exactly the sets containing at most ''r'' elements, for some fixed integer ''r''. An alternative definition is that every permutation of the elements is a symmetry. ...
as a
minor.
[.] The unimodular or
regular matroid
In mathematics, a regular matroid is a matroid that can be represented over all fields.
Definition
A matroid is defined to be a family of subsets of a finite set, satisfying certain axioms. The sets in the family are called "independent sets". ...
s are the matroids that can be represented over all fields;
[White (1987) p.2] they can be characterized as the matroids that have none of
, the
Fano plane (a binary matroid with seven elements), or the
dual matroid of the Fano plane as minors.
[White (1987) p.12] 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 number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
s) no such characterization is possible.
Field of definition
For every
algebraic number field
In mathematics, an algebraic number field (or simply number field) is an extension field K of the field of rational numbers such that the field extension K / \mathbb has finite degree (and hence is an algebraic field extension).
Thus K is a f ...
and every
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
''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
A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
''p'' there exist infinitely many matroids whose characteristic set is the singleton set , and for every
finite set
In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,
:\
is a finite set with five elements. T ...
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.
[, p. 225.] Hence the only possible characteristic sets are finite sets not containing zero, and cofinite sets containing zero.
[, p. 226.] Indeed, all such sets do occur.
[, p. 228.]
Related classes of matroids
A
uniform matroid
In mathematics, a uniform matroid is a matroid in which the independent sets are exactly the sets containing at most ''r'' elements, for some fixed integer ''r''. An alternative definition is that every permutation of the elements is a symmetry. ...
has
elements, and its independent sets consist of all subsets of up to
of the elements. Uniform matroids may be represented by sets of vectors in
general position
In algebraic geometry and computational geometry, general position is a notion of genericity for a set of points, or other geometric objects. It means the ''general case'' situation, as opposed to some more special or coincidental cases that are ...
in an
-dimensional vector space. 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''. 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
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...
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
Degrees of freedom (often abbreviated df or DOF) refers to the number of independent variables or parameters of a thermodynamic system. In various scientific fields, the word "freedom" is used to describe the limits to which physical movement or ...
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 number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
s with a structure similar to that of the
incidence matrix of the underlying graph, and hence are
-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
elements may be represented over every field that has at least
elements.
The
algebraic matroids are matroids defined from sets of elements of a
field extension
In mathematics, particularly in algebra, a field extension is a pair of fields E\subseteq F, such that the operations of ''E'' are those of ''F'' restricted to ''E''. In this case, ''F'' is an extension field of ''E'' and ''E'' is a subfield of ...
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
{{reflist, colwidth=30em
Representation