In mathematics, a basis of a matroid is a maximal independent set of the matroid—that is, an independent set that is not contained in any other independent set.
As an example, consider the matroid over the ground-set R2 (the vectors in the two-dimensional Euclidean plane), with the following independent sets:
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]
All matroids satisfy the following properties, for any two distinct bases and : [2] [3]
However, a basis-exchange property that is both symmetric and bijective is not satisfied by all matroids: it is satisfied only by base-orderable matroids.
In general, in the symmetric basis-exchange property, the element need not be unique. Regular matroids have the unique exchange property, meaning that for some , the corresponding b is unique. [6]
It follows from the basis exchange property that no member of can be a proper subset of another.
Moreover, all bases of a given matroid have the same cardinality. In a linear matroid, the cardinality of all bases is called the dimension of the vector space.
It is conjectured that all matroids satisfy the following property: [2] For every integer t ≥ 1, If B and B' are two t-tuples of bases with the same multi-set union, then there is a sequence of symmetric exchanges that transforms B to B'.
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 to be a pair , where is the ground-set and is a collection of subsets of , called "bases", with the following properties: [7] [8]
(B2) implies that, given any two bases A and B, we can transform A into B by a sequence of exchanges of a single element. In particular, this implies that all bases must have the same cardinality.
If is a finite matroid, we can define the orthogonal or dual matroid by calling a set a basis in if and only if its complement is in . It can be verified that is indeed a matroid. The definition immediately implies that the dual of is . [9]: 32 [10]
Using duality, one can prove that the property (B2) can be replaced by the following:
(B2*) If and are distinct bases, and , then there exists an element such that 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 to be a pair , where is the ground-set and is a collection of subsets of , called "circuits", with the following properties: [8]
Another property of circuits is that, if a set is independent, and the set is dependent (i.e., adding the element makes it dependent), then contains a unique circuit , and it contains . This circuit is called the fundamental circuit of w.r.t. . It is analogous to the linear algebra fact, that if adding a vector to an independent vector set makes it dependent, then there is a unique linear combination of elements of that equals . [10]
In mathematics, a basis of a matroid is a maximal independent set of the matroid—that is, an independent set that is not contained in any other independent set.
As an example, consider the matroid over the ground-set R2 (the vectors in the two-dimensional Euclidean plane), with the following independent sets:
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]
All matroids satisfy the following properties, for any two distinct bases and : [2] [3]
However, a basis-exchange property that is both symmetric and bijective is not satisfied by all matroids: it is satisfied only by base-orderable matroids.
In general, in the symmetric basis-exchange property, the element need not be unique. Regular matroids have the unique exchange property, meaning that for some , the corresponding b is unique. [6]
It follows from the basis exchange property that no member of can be a proper subset of another.
Moreover, all bases of a given matroid have the same cardinality. In a linear matroid, the cardinality of all bases is called the dimension of the vector space.
It is conjectured that all matroids satisfy the following property: [2] For every integer t ≥ 1, If B and B' are two t-tuples of bases with the same multi-set union, then there is a sequence of symmetric exchanges that transforms B to B'.
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 to be a pair , where is the ground-set and is a collection of subsets of , called "bases", with the following properties: [7] [8]
(B2) implies that, given any two bases A and B, we can transform A into B by a sequence of exchanges of a single element. In particular, this implies that all bases must have the same cardinality.
If is a finite matroid, we can define the orthogonal or dual matroid by calling a set a basis in if and only if its complement is in . It can be verified that is indeed a matroid. The definition immediately implies that the dual of is . [9]: 32 [10]
Using duality, one can prove that the property (B2) can be replaced by the following:
(B2*) If and are distinct bases, and , then there exists an element such that 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 to be a pair , where is the ground-set and is a collection of subsets of , called "circuits", with the following properties: [8]
Another property of circuits is that, if a set is independent, and the set is dependent (i.e., adding the element makes it dependent), then contains a unique circuit , and it contains . This circuit is called the fundamental circuit of w.r.t. . It is analogous to the linear algebra fact, that if adding a vector to an independent vector set makes it dependent, then there is a unique linear combination of elements of that equals . [10]