Editing Matroid (section)

===Matroids from linear algebra===
[[File:fano plane.svg|thumb|The Fano matroid, derived from the [[Fano plane]]. It is [[GF(2)]]-linear but not real-linear.]]
[[File:Vamos matroid.svg|thumb|The [[Vámos matroid]], not linear over any field]]
Matroid theory developed mainly out of a deep examination of the properties of independence and dimension in vector spaces. There are two ways to present the matroids defined in this way:
: If <math>E</math> is any finite subset of a [[vector space]] <math>V</math>, then we can define a matroid <math>M</math> on <math>E</math> by taking the independent sets of <math>M</math> to be the [[linear independence|linearly independent]] subsets of <math>E</math>.
The validity of the independent set axioms for this matroid follows from the [[Steinitz exchange lemma]].

: If <math>M</math> is a matroid that can be defined in this way, we say the set <math>E</math> ''[[matroid representation|represents]]'' <math>M</math>.

: Matroids of this kind are called ''vector matroids''.

An important example of a matroid defined in this way is the Fano matroid, a rank&nbsp;three matroid derived from the [[Fano plane]], a [[finite geometry]] with seven points (the seven elements of the matroid) and seven lines (the proper nontrivial flats of the matroid). It is a linear matroid whose elements may be described as the seven nonzero points in a three&nbsp;dimensional vector space over the [[finite field]] [[GF(2)]]. However, it is not possible to provide a similar representation for the Fano matroid using the [[real number]]s in place of GF(2).

A [[matrix (mathematics)|matrix]] <math>A</math> with entries in a [[field (mathematics)|field]] gives rise to a matroid <math>M</math> on its set of columns. The dependent sets of columns in the matroid are those that are linearly dependent as vectors.
: This matroid is called the ''column matroid'' of <math>A</math>, and <math>A</math> is said to ''represent'' <math>M</math>.

For instance, the Fano matroid can be represented in this way as a 3&nbsp;&times;&nbsp;7 [[Logical matrix|(0,1)&nbsp;matrix]]. Column matroids are just vector matroids under another name, but there are often reasons to favor the matrix representation.{{efn|
There is one technical difference: A column matroid can have distinct elements that are the same vector, but a vector matroid as defined above cannot. Usually this difference is insignificant and can be ignored, but by letting <math>E</math> be a [[multiset]] of vectors one brings the two definitions into complete agreement.
}}

A matroid that is equivalent to a vector matroid, although it may be presented differently, is called ''representable'' or ''linear''. If <math>M</math> is equivalent to a vector matroid over a [[field (mathematics)|field]] <math>F</math>, then we say <math>M</math> is ''representable over'' {{nobreak|<math>F</math>;}} in particular, <math>M</math> is ''real representable'' if it is representable over the real numbers. For instance, although a graphic matroid (see below) is presented in terms of a graph, it is also representable by vectors over any field.

A basic problem in matroid theory is to characterize the matroids that may be represented over a given field <math>F</math>; [[Rota's conjecture]] describes a possible characterization for every [[finite field]].  The main results so far are characterizations of [[binary matroid]]s (those representable over GF(2)) due to [[W. T. Tutte|Tutte]] (1950s), of ternary matroids (representable over the 3&nbsp;element field) due to Reid and Bixby, and separately to [[Paul Seymour (mathematician)|Seymour]] (1970s), and of quaternary matroids (representable over the 4&nbsp;element field) due to {{harvp|Geelen|Gerards|Kapoor|2000}}. A proof of Rota's conjecture was announced, but not published, in 2014 by Geelen, Gerards, and Whittle.<ref>{{cite journal|title=Solving Rota's conjecture|journal=Notices of the American Mathematical Society|url=http://www.ams.org/notices/201407/rnoti-p736.pdf|date=Aug 17, 2014|pages=736–743}}</ref>

A [[regular matroid]] is a matroid that is representable over all possible fields. The [[Vámos matroid]] is the simplest example of a matroid that is not representable over any field.