Basis of a matroid

As an example, consider the matroid over the ground-set R² (the vectors in the two-dimensional Euclidean plane), with the following independent sets:

{ {}, {(0,1)}, {(2,0)}, {(0,1),(2,0)}, {(0,3)}, {(0,3),(2,0)} }.

It has two bases, which are the sets {(0,1),(2,0)} , {(0,3),(2,0)}. These are the only independent sets that are maximal under inclusion.

The basis has a specialized name in several specialized kinds of matroids:[1]

• In a graphic matroid, where the independent sets are the forests, the bases are called the spanning forests of the graph.
• In a transversal matroid, where the independent sets are endpoints of matchings in a given bipartite graph, the bases are called transversals.
• In a linear matroid, where the independent sets are the linearly-indepenent sets of vectors in a given vector-space, the bases are just called bases of the vector space. Hence, the concept of basis of a matroid generalizes the concept of basis from linear algebra.
• In a uniform matroid, where the independent sets are all sets with cardinality at most k (for some integer k), the bases are all sets with cardinality exactly k.
• In a partition matroid, where elements are partitioned into categories and the independent sets are all sets containing at most k_c elements from each category c, the bases are all sets which contain exactly k_c elements from category c.
• In a free matroid, where all subsets of the ground-set E are independent, the unique basis is E.

The bases of a matroid characterize the matroid completely: a set is independent if and only if it is a subset of a basis. Moreover, one may define a matroid ${\displaystyle M}$ to be a pair ${\displaystyle (E,{\mathcal {B}})}$, where ${\displaystyle E}$ is the ground-set and ${\displaystyle {\mathcal {B}}}$ is a collection of subsets of ${\displaystyle E}$, called "bases", with the following properties:[5][6]

(B1) There is at least one base -- ${\displaystyle {\mathcal {B}}}$ is nonempty;

(B2) If ${\displaystyle A}$ and ${\displaystyle B}$ are distinct bases, and ${\displaystyle a\in A\setminus B}$, then there exists an element ${\displaystyle b\in B\setminus A}$ such that ${\displaystyle (A\setminus \{a\})\cup \{b\}}$ is a basis (this is the basis-exchange property).

If ${\displaystyle (E,{\mathcal {B}})}$ is a finite matroid, we can define the orthogonal or dual matroid ${\displaystyle (E,{\mathcal {B}}^{*})}$ by calling a set a basis in ${\displaystyle {\mathcal {B}}^{*}}$ if and only if its complement is in ${\displaystyle {\mathcal {B}}}$. It can be verified that ${\displaystyle (E,{\mathcal {B}}^{*})}$ is indeed a matroid. The definition immediately implies that the dual of ${\displaystyle (E,{\mathcal {B}}^{*})}$ is ${\displaystyle (E,{\mathcal {B}})}$.[7]^:32[8]

Using duality, one can prove that the property (B2) can be replaced by the following:

(B2*) If ${\displaystyle A}$ and ${\displaystyle B}$ are distinct bases, and ${\displaystyle b\in B\setminus A}$, then there exists an element ${\displaystyle a\in A\setminus B}$ such that ${\displaystyle (A\setminus \{a\})\cup \{b\}}$ is a basis.

A dual notion to a basis is a circuit. A circuit in a matroid is a minimal dependent set—that is, a dependent set whose proper subsets are all independent. The terminology arises because the circuits of graphic matroids are cycles in the corresponding graphs.

one may define a matroid ${\displaystyle M}$ to be a pair ${\displaystyle (E,{\mathcal {C}})}$, where ${\displaystyle E}$ is the ground-set and ${\displaystyle {\mathcal {C}}}$ is a collection of subsets of ${\displaystyle E}$, called "circuits", with the following properties:[6]

(C1) The empty set is not a circuit;

(C2) A subset of a circuit is not a circuit;

(C3) If C₁ and C₂ are circuits, and x is an element in their intersection, then ${\displaystyle C_{1}\cup C_{2}\setminus \{x\}}$ contains a circuit.

Another property of circuits is that, if a set J is independent, and the set J u {x} is dependent (i.e., adding the element x makes it dependent), then J u {x} contains a unique circuit C(x,J), and it contains x. This circuit is called the fundamental circuit of x w.r.t. J. It is analogous to the linear algebra fact, that if adding a vector x to an independent vector set J makes it dependent, then there is a unique linear combination of elements of J that equals x.[8]