In mathematics, an algebraic matroid is a

matroid In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...

, a

combinatorial Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ap ...

structure, that expresses an abstraction of the relation of

algebraic independence In abstract algebra, a subset S of a field L is algebraically independent over a subfield K if the elements of S do not satisfy any non- trivial polynomial equation with coefficients in K. In particular, a one element set \ is algebraically i ...

Definition

Given 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 ...

''L''/''K'', Zorn's lemma can be used to show that there always exists a maximal algebraically independent subset of ''L'' over ''K''. Further, all the maximal algebraically independent subsets have the same

cardinality In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...

, known as the

transcendence degree In abstract algebra, the transcendence degree of a field extension ''L'' / ''K'' is a certain rather coarse measure of the "size" of the extension. Specifically, it is defined as the largest cardinality of an algebraically independent subset of ...

of the extension. For every finite set ''S'' of elements of ''L'', the algebraically independent subsets of ''S'' satisfy the axioms that define the independent sets of a

. In this matroid, the rank of a set of elements is its transcendence degree, and the flat generated by a set ''T'' of elements is the intersection of ''L'' with the field ''K'' 'T''Oxley (1992) p.216 A matroid that can be generated in this way is called ''algebraic'' or ''algebraically representable''.Oxley (1992) p.218 No good characterization of algebraic matroids is known,Oxley (1992) p.215 but certain matroids are known to be non-algebraic; the smallest is the

Vámos matroid In mathematics, the Vámos matroid or Vámos cube is a matroid over a set of eight elements that cannot be represented as a matrix over any field. It is named after English mathematician Peter Vámos, who first described it in an unpublished ma ...

Relation to linear matroids

Many finite matroids may be represented by a

matrix Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** '' The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchi ...

over a field ''K'', in which the matroid elements correspond to matrix columns, and a set of elements is independent if the corresponding set of columns is

linearly independent In the theory of vector spaces, a set of vectors is said to be if there is a nontrivial linear combination of the vectors that equals the zero vector. If no such linear combination exists, then the vectors are said to be . These concepts ...

. Every matroid with a linear representation of this type over a field ''F'' may also be represented as an algebraic matroid over ''F'',Oxley (1992) p.220White (1987) p.24 by choosing an

indeterminate Indeterminate may refer to: In mathematics * Indeterminate (variable), a symbol that is treated as a variable * Indeterminate system, a system of simultaneous equations that has more than one solution * Indeterminate equation, an equation that ha ...

for each row of the matrix, and by using the matrix coefficients within each column to assign each matroid element a linear combination of these transcendentals. 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;. indeed the non-Pappus matroid is algebraic over any finite field, but not linear and not algebraic over any field of characteristic zero. However, if a matroid is algebraic over a field ''F'' of characteristic zero then it is linear over ''F''(''T'') for some finite set of transcendentals ''T'' over ''F''Oxley (1992) p.221 and over the

algebraic closure In mathematics, particularly abstract algebra, an algebraic closure of a field ''K'' is an algebraic extension of ''K'' that is algebraically closed. It is one of many closures in mathematics. Using Zorn's lemmaMcCarthy (1991) p.21Kaplansky ...

of ''F''.

Closure properties

If a matroid is algebraic over a

simple extension In field theory, a simple extension is a field extension which is generated by the adjunction of a single element. Simple extensions are well understood and can be completely classified. The primitive element theorem provides a characterization of ...

''F''(''t'') then it is algebraic over ''F''. It follows that the class of algebraic matroids is closed under

contraction Contraction may refer to: Linguistics * Contraction (grammar), a shortened word * Poetic contraction, omission of letters for poetic reasons * Elision, omission of sounds ** Syncope (phonology), omission of sounds in a word * Synalepha, merged ...

,Oxley (1992) p.222 and that a matroid algebraic over ''F'' is algebraic over the

prime field In mathematics, the characteristic of a ring , often denoted , is defined to be the smallest number of times one must use the ring's multiplicative identity (1) in a sum to get the additive identity (0). If this sum never reaches the additive id ...

of ''F''.Oxley (1992) p.224 The class of algebraic matroids is closed under truncation and matroid union. It is not known whether the dual of an algebraic matroid is always algebraicOxley (1992) p.223 and there is no excluded minor characterisation of the class.

Characteristic set

The (algebraic) characteristic set ''K''(''M'') of a matroid ''M'' is the set of possible characteristics of fields over which ''M'' is algebraically representable. * If 0 is in ''K''(''M'') then all sufficiently large primes are in ''K''(''M''). * Every prime occurs as the unique characteristic for some matroid. * If ''M'' is algebraic over ''F'' then any contraction of ''M'' is algebraic over ''F'' and hence so is any minor of ''M''.White (1987) p.25

Notes

References

* * *{{citation , editor-last=White , editor-first=Neil , title=Combinatorial geometries , series=Encyclopedia of Mathematics and its Applications , volume=29 , location=Cambridge , publisher=

Cambridge University Press Cambridge University Press is the university press of the University of Cambridge. Granted letters patent by Henry VIII of England, King Henry VIII in 1534, it is the oldest university press in the world. It is also the King's Printer. Cambr ...

, year=1987 , isbn=0-521-33339-3 , zbl=0626.00007 , url-access=registration , url=https://archive.org/details/combinatorialgeo0000unse Matroid theory