Fundamentals of Matroid Theory

Matroid, a combinatorial object that was first introduced by Whitney in 1935 and has been studied extensively by mathematicians ever since then, is one of the most important topics and glorious triumphs of combinatorics.

Matroid is thought to be the product when linear algebra meets graph theory. Initially, it was an abstraction and generalization of linear independence of linear algebra. This is also how it got its name, "something similar to matrix". However, it was then found to be strongly connected to graph theory: there are many graph theoretic objects found to be matroids; while graph theory provides metaphors and algorithms, for interpreting matroids and performing matroid operations.

However, despite the fact that linear algebra and graph theory establishes the language of matroid theory, there's no isolated island in mathematics, and matroid is also found to be related to other fields of combinatorics, as well as algebra, geometry, and topology.

On the other hand, matroid has a bunch of published results in combinatorial optimized algorithms, so studying matroid can also improve problem-solving in computer science.

Independent Sets and Bases

As is said, that matroids are abstract linear independence, let's recall what linear independence can do.

First, we know a linearly independent set is a set of vectors such that no vector can be represented by the linear combination of other vectors.

It won't be hard to find any subset of a linearly independent set is also a linearly independent set, since otherwise the linear combination evidence in the subset can also be carried out to the superset, rendering the superset not to be linearly independent. A property present in the superset is said to be hereditary, if it is preserved when pruning to any of its subsets. The linear independence is an example of hereditary property.

The next one is not so obvious but still simple for those familiar with linear algebra, that for two linearly independent sets (of the same vector space), if , then there exists a vector , such that is linearly independent. To prove, it suffices to show some vectors in can't be represented by the linear combination of . This can be simply shown by Gaussian elmination. If not so, let and , represent all as the linear combination of :

This can be viewed as a system of linear equations with variables. We may use Gaussian elimination to wipe the -th equation out, to . But this is accomplished by subtracting coefficients scalar-multiplying the first rows from the -th row, that for some coefficients . So now is a linear combination of the first vectors in , which is a contradiction to is a linearly independent set. The property that a larger linearly independent set can provide some vector to a smaller independent set is called the independent set exchange property (aka. augmentation property).

A matroid is a combinatorial object that captures and generalizes the hereditary property and the independent set exchange property:

The axioms of matroids above are called the independent set axioms of matroids, and we will see there're many ways to define a matroid axiomatically and equivalently. Here, we define hereditary systems prior to matroids, since we want to reuse it in other axioms of matroids later.

In the case of linearly independent sets, it's okay to let empty set to be linearly independent. However, we will see letting is indispensible if we want the hereditary system to exhibit some natural behaviors, which makes our life easier.

In combinatorics, we are discussing about finite objects in most time, and that's why we require the ground set to be a finite set.

The linearly independent sets itself that motivates us obviously defines a matroid:

However, a matroid over a ground set of vectors with independent sets being linearly independent subsets need not be a vectorial matroid:

As linearly independent sets are the initial motivation of matroids, playing with them is not very motivating. So let's see an object from graph theory that also turns out to have abstract linear independence:

So the abstract linear independence occurs in a seemingly completely unrelated field, the graph theory. Interesting as it is, the purpose of defining matroids is still fuzzy, why would we want to unify the linearly independent sets and the spanning forests? To answer this question, we will have to reveal more properties of matroids.

Bases of Matroids

Again, let's do a quick review about the bases in linear algebra.

For a finite set of vectors , we may use it to span a vector space by the linear combination of vectors in . However, by the theory of linear algebra, some vectors in might be dispensable: let and vector , if is expressible by , then is dispensable and represents the same vector. In this way, the set might be reduced to a basis , a subset of linearly independent vectors, such that .

In the example above, given that , the way of eliminating linearly dependent vectors in is not unique, and we should expect more than one bases of obtainable from eliminations in in general.

For a finite set of vectors and the vector space it spans, a linearly independent set is a basis iff it's a maximal, that is, no proper superset of it is linearly independent. To show the necessity, for a basis and a proper linearly independent superset , there's an element that is not expressible by linear combination of vectors in , but is expected, which is a contradiction. To show the sufficiency, if is maximal linearly independent subset of but not span , there must be a vector that is not spanned by , and thus is linearly independent and larger than , which is contradiction to the maximality of .

And in the case of matroid:

So a basis of matroid captures the maximal property of a basis in linear algebra. However, we will show, it suffices to capture this property in order for a basis matroid to exhibit many behaviors similar to a basis in linear algebra.

We are familiar with the conclusion, that for the -dimensional vector space spanned by , every basis has vectors. And the bases of matroid also possess this property:

Simple as they are, if we put the proofs above alongside with the proof of every basis of -dimensional vector space has vectors, we will soon find the proofs above are just abstracted versions of the one in linear algebra.

The bases in linear algebra also have the basis exchange property, that is, for two distinct bases of the same vector space, , such that is also a basis. This property also holds for bases of matroids:

The matroid version of basis exchange property is called the weak basis exchange property, in comparision with the strong basis exchange property that . However, the latter one can't be proved by using rudimentary properties of matroids we've known (in this text) so far. We will revisit the proof of the strong basis exchange property once we have discussed sufficiently about properties of matroids to prove.

Matroids and Greedy Algorithms

The matroids are even famous among computer scientists due to their connection with the greedy algorithms, especially the fact that it's possible to generalize the classical Kruskal's MST algorithm over matroids.

The Kruskal's MST algorithm finds the minimum spanning tree of a connected graph, that is, with weights assigned to every edges in graph, the Kruskal's MST algorithm finds a spanning tree minimizing the total weights.

On the other hand, it won't be hard to see the bases of a cycle matroid are the spanning forests such that each component is a spanning tree of a connected component in the original graph . When there's only one component, the bases are the spanning trees of the graph. And when we assign weights to the edges, let , the MST problem can also be viewed as finding among the bases.

And in this section, we would like to show for a general matroid with weights assigned to each elements, a greedy algorithm suffices to solve the problem of finding .

For convenience, we would like to show the following process ends up with finding a basis of a matroid:

Please notice the order of iterating is arbitrary, and different order of iteration might end up with different basis constructed.

And the algorithm of finding with minimum weight is shown as below:

For those who are familiar with the non-matroid version of the proof of Kruskal's MST algorithm, they will quickly find how similar these two proofs are, and no wonder why the algorithm above is considered a generalization of Kruskal's MST algorithm to matroids.

For every matroid, the greedy algorithm above solves the minimum weighted basis problem for it sufficiently. However, it's a common misconception to think every greedy algorithm has necessarily an underlying matroid. The Prim's MST algorithm, which is the twin cousin compared to Kruskal's MST algorithm from time to time, has no underlying matroid inside in this case.

Base System Axioms of Matroids

For every matroid , we can find the bases, a set of maximally and equally-sized independent set via . However, is it possible to specify a set of equally-sized subsets of a ground set , and use it as the set of bases, defining a matroid?

From the previous sections, we know the bases of a matroid have the weak basis exchange property, so if a set of equally-sized subsets would like to define a matroid, they must fulfil this property in the first place. Thinking of extremality, it won't be hard to find the tuple defnies a matroid minimally, and its bases are , so the set of bases can never be empty. But is possessing these properties sufficient, let's give it a try:

Intuively speaking, in a matroid, every independent set must be a subset of a basis. This inspire us to define:

So that we may retrieve the independent sets from a base system through . The only thing left to check is whether the hereditary system also possesses the independent set exchange property, and how are they connected to the way we define the base system above:

In this way, to define a matroid, it suffice to come up with a base system . That is, it suffices to say there's a matroid such that , in order to define a matroid in the form of .

The theorem above also shows us an alternative way to define a matroid equivalently. In fact, there're other ways of defining matroid. Such a phenomenon of defining matroid equivalently in many seemingly unrelated way (that are later shown to be tightly connected) is sometimes referred as cryptomorphism of matroids by mathematicians. The terminology of cryptomorphism is also leveraged to describe different but equivalent sets of axioms of defining the same mathematical object.

Rank Function

We are familiar with the rank of a matrix, that is, the maximum number of linearly independent row or column vectors in a matrix. It won't be hard to find the order of rows and columns does not matter, and deduplication does not affect the rank, so we may assume the rank to be defined on a set of vectors, by evaluating the maximum number of linearly independent vectors in the set.

Analogously, for a given set which is a subset of the ground set of a matroid, we would also want to ask the maximum number of "independent" elements, this is equivalent to asking the maximum size of an independent subset of the given set. Noted that asking the rank of a matrix is equivalent to asking the maximum size of an independent subset in a vectorial matroid.

To fulfill this purpose, we first define the restriction of matroid to a set:

Obviously the maximum size of an independent subset of the given set is the size of a basis of the restriction of the matroid to the given set. And we may define:

By doing so, given that the size of bases of a matroid is unique, we obtain the well-formedness of the rank function of a matroid for free. Meantime, such a definition is compatible with the rank of a matrix, when viewing it as a vectorial matroid.

Absorption Rules

We can see metaphors play an important role in studying matroids. In a matrix, when extending it by a vector, its rank remains unchanged or increment by , depending whether the introduced row is independent or not. And in a matroid, the case is similar:

In a matrix , assume augmenting with vector does not , and so does , then augmenting with simultenously will not affect either. And when it comes to the case of a matroid , we also have:

Submodularity

First, we would like to introduce the concept of submodular function:

Then, we would like to show the rank function of a matroid is a submodular function:

The submodularity of rank function is a useful in proving properties of matroids, we will see later in this text.

Rank Function Axioms of Matroids

There's another cryptomorphism of matroids, that if a set is equipped with a rank function, then we are able to extract a hereditary system with independent set exchange property out of it, using it as the independent sets of a matroid and defining a matroid.

First, we would like to equip a set with a rank function:

A rank function on a finite set has the strong absorption rule, which can be directly implied from the weak absorption rule:

Intuitively speaking, in a matroid, all independent sets fulfills , and this inspires us to define:

And see whether defines a hereditary system on with independent set exchange property. We will begin with showing the hereditary property:

So it suffices for and the monotonicity property to ensure the hereditary property of . But to prove the independent set exchange property, we still need the absorption rules:

The submodularity of a rank function on ground set , that , follows immediately by viewing from the underlying matroid .

On the other hand, it's also possible to substitute the weak absorption rule with the submodularity in the axioms of rank function. Since if , then given that , we have , and by combining with the monotonicity we have .

Dependent Sets and Circuits

While the bases and rank function we've discussed about are related to independent sets, it's also possible to study matroids from the dependent sets. The most important kind of dependent sets might be the circuits:

The circuits rise from the cycle matroids:

But the definition above is applicable to all matroids, not just the cycle matroid. So what do circuits look like in the vectorial matroids?

The circuits draw special attention, since there's:

It's good to take care of the following common misconception:

Weak Elimination Rule

Consider two cycles in a cycle matroid and their union , if they intersect at a path , then after removing any edge in the path, will still contain a cycle:

Interestringly, it turns out that such a property is general and applicable to any matroid:

We name such a property of matroid the weak elimination rule. There's also a strong elimination rule, which states in every dependent set and for every element , there's a circuit such that . Intuitively, those corresponds to the edges marked purple in our cycle matroid example. We will prove this property later, as what we've learnt about matroids so far is insufficient for proving it.

Consider a spanning forest in a cycle matroid: If by adding one edge we introduce a cycle, then only one cycle can be introduced. Otherwise for two cycles introduced, they must both contain otherwise they are to find in the original graph. But edge set contains another cycle and can be found in the original spanning forest.

And by utilizing the weak elimination rule, such a phenomenon in cycle matroid can also be generalized to any matroid:

The process of proof is literally identical to what we've argued for the cycle matroid above. So no wonder graph theory also plays an important role in studying matroids.

Greedy Algorithm Axioms of Matroids

This section is not related to circuits directly, however it's essential to the later proof of showing that we may define matroids by circuits cryptomorphically.

It's said that there's not necessarily a matroid behind a greedy algorithm, however there's a specialty when the greedy algorithm is running over a hereditary system. If we go over the proof of the correctness of greedy algorithm to find the minimum weighted basis, we will notice that the independent set exchange property plays a major role in ensuring the correctness, regardless of what weight function is used as input. And the specialty is, if a greedy algorithm to run in a hereditary system is correct, regardless of the input weight function, then we may excavate the independent set exchange property from the hereditary system, showing it to have an underlying matroid.

The proof is based on the classical work of Rado and Gale. They first came up with the following greedy algorithm:

And then they asserted that:

Let's begin with the sufficiency part. When the hereditary system is a matroid, it won't be hard to find the algorithm above is almost identical to the greedy algorithm we've used for finding the minimum weighted basis, except for forcing the weight function to be non-negative, ordering the list in descending order, and not requiring to find a basis. However, if our previous greedy algorithm is correct, then this algorithm must also be correct:

So in the case of matroid, by requiring the weight function to be non-negative we have forced a maximum weighted independent set to be a basis, and then the greedy algorithm will find such a basis with maximum weight sufficiently.

Now let's focus on the necessity part. Please notice that a general hereditary system does not necessarily have the independent set exchange property. However, if such a property is dispensible, we can show the greedy algorithm will fail for a deliberately designed input weight function:

In this way, with a hereditary system , paired with the guarantee for the Greedy Algorithm for Maximum Weighted Independent Set to yield the correct answer for whichever non-negative weight function indefinitely, we may define a matroid cryptomorphically. We shall call it the greedy algorithm axioms of matroids.

Circuit System Axioms of Matroids

So let's see whether we can define a matroid cryptomorphically. Just like what we've done before, we begin with extracting properties of circuits in a matroid:

And since all dependent sets are those containing a circuit, it's expected that by defining:

We retrieve the "dependent sets" defined by a circuit system, and therefore the "independent sets" . And therefore for a subset , it suffices for to show is independent.

So if a matroid is hopefully defined in such a way, it should be in the form of . Let's begin with showing the hereditary property:

Then let's show some familiar properties in the circuit system:

Finally, we are ready to show a circuit system defines a matroid:

In this way, it turns out that we may define a matroid on by simply saying for a circuit system on .

Span Function

We are familiar with the vector space spanned by a set of vectors. When it comes to the case of vectorial matroid , the most direct way of defining the span of is to consider those vectors representable by the linear combination of vectors in .

However, being a matroid deliberately hides the underlying detail of "linear combination" from us, so we must only rely on the language and characterization of independent sets and dependent sets. However, is dependent does not necessarily imply that can be represented by the linear combination of : as long as itself is dependent, any superset of will also be dependent. This will ridiciously lead us to every element in is "representable" by the "linear combination" of .

But the previous section also provides us a solution, that is, for that would like to be expressible by the remaining vectors, there's a circuit iff for (by eliminating those with zero coefficients).

In this way, the closest characterization of span may rely on the language of circuits:

Does defining in such a way eliminate the problem of dependent sets' "spanning" every element in , let's give it a try: in a matroid on , there's a loop , while no singleton set of is loop. When we evaluate , it won't be hard to find none of the sets is circuit in for containing circuit . So does not span and . So there's no longer the problem of dependent sets' "spanning" every element by defining so.

Let's see what span function looks like in a cycle matroid:

The independent sets and dependent sets in a matroid can also be characterized by the span function:

The lemma above can be intuitively interpreted in a cycle matroid, it means for edge set , the spanning subgraph is a spanning forest iff every is a cut edge.

For any vector space, we know it suffices for a basis to span it. And this property also holds for a general matroids:

Span Function Defined by Rank Function

Let's see another seemingly "careless" way of defining span function. In a vectorial matroid , if we want to test whether vector is expressible by the linear combination of , we may put vectors of into a matrix (assume are column vectors) and evaluate , which equals . Then we augment with , resulting in , evaluate and see whether . If then can be eliminated by Gaussian elimination, which requires representing as the linear combination of .

And we would like to show it's as effective to express elements spanned by a set using rank function, as the one using circuits:

So is there any intuitive way to interpret why it works by doing so?

Well, by evaluating , it can be seen as reducing matrix of elements in into a maximal independent set. If , then the maximal independent set can represents , thus forms a circuit with elements from this maximal independent set, and thus . Conversely, if by forming a circuit with some elements in , that is, is representable by some elements in with non-zero coefficients, then move these elements to the first few rows and reduce the matrix to its maximal independent sets. The first few rows is independent and thus intact during elimination. Adding to the matrix will not increment the rank since it is sufficiently eliminated by the first few rows, and thus . So the rank function has intrinsic connection to the circuits.

Defining span using rank function can easily lead to:

Closure Operator Properties

Let's first introduce the definition of a closure operator:

And we would like to show:

In this way, it's said that defines a closure operator in a matroid.

These concepts are closely related to the closure operator aspect of matroids:

When combining with the property , one can easily see:

Steinitz Exchange Property and Closure Operator Axioms of Matroids

In linear algebra, the Steinitz exchange lemma states, that if there's a set of vectors plus a vector , that spans a vector space , then for any vectors , there's .

The proof is simple, when , there's and the proposition is trivially true. When , in any representation of , we must have . Thus for there must necessarily be a representation such that , otherwise there must be by there's no way to fix into . In this way, we must have , and thus .

This phenomenon can also be generalized to matroids:

It won't be hard to see the proof is just a rephrashing of the proof of Steinitz exchange lemma in linear algebra.

So the span function of a matroid are the kind of closure operators with Steinitz exchange property. Conversely, we would like to show it suffices for a closure operator with Steinitz exchange property to define a matroid cryptomorphically.

Recall that independent sets of a matroid can also be retrieved by , so we would like to show a hereditary system may be defined in such a way first:

Then we would like to show the Steinitz exchange property enables a closure operator to define a matroid. The role that Steinitz exchange property plays in the proof is indispensible and must be emphasized:

So closure operators with Steinitz exchange property are equivalent to matorids.

Strong Elimination Property

With the language of span function, we may now prove the strong elimination property we've mentioned when showing the weak elimination property of matroids.

Dual Matroids

By utilizing the properties of circuits in a matroid, we are ready to show the strong basis exchange property of a matroid:

Generally speaking, the choice of elements such that enables does not neccessarily guarantee , and vice versa.

However, by utilizing the properties of span function, we are able to prove, there does exist choice of elements such that enables simultaneously:

The even stronger version of strong basis exchange property is not required by the following text, but required by the later topic of the matroid intersection theorem.

The strong basis exchange property sheds light on some sort of duality in a matroid. That is, we may retrieve the dual base system from a base system of a matroid:

And then show it to be a base system, which defines the dual matroids:

By now, we can clearly see how is the strong exchange property of a matroid connected to its duality.

The dual matroid arises from the dual graph of a planar graph, and the topological arguments of planar graphs can also be generalized to matroids, offering an alternative characterization of planar graphs by matroids, the Whitney's Planarity Criterion. We have a later topic of matroid duality and topology, and we will be focusing on the non-topological part of dual matroids in this text.

Coindependent Sets and Corank Function

We begin with arguing a set is coindependent iff it's the complement of a spanning set:

This property can easily lead to the dual augmentation property:

In this way, we may always permute the elements of , so that for disjoint independent set and coindependent set , the following setup exists:

By the definition of dual matroid, one can easily see , but the relation between rank and corank for can't be easily seen. In fact, by the construction of matroid and subset , the values of can be arbitrary:

Therefore one must not expect there to be any direct connection between and . However, there's still connection between and :

Cocircuits

Just like the connection between coindependent sets and spanning sets, we have connection between cocircuits and hyperplanes. We state that a set is cocircuit iff it's the complement of a hyperplane:

In this way, we can see the independent sets and circuits are actually connected and interchangeable, due to the string the dual matroids pull for us.

In fact, due to the corollary, we are now able to interpret the dual matroid of a cycle matroid intuitively, for bonds, the minimal edge cuts:

We will discuss more about the topological aspect of the bond matroids in the later topic.

Finally, we want to characterize the circuits and cocircuits by their intersections:

Matroid Isomorphisms

It won't be hard to see, it's the independent sets and their set-inclusion relationship that really matters. So we may define isomorphism in such a way:

Just like graph isomorphisms, the matroid isomorphisms also categorize matroids into isomorphism classes. We will be going over some important isomorphism classes of matroids in the remaining text of this section.

On the other hand, since the ground set of a matroid is always finite, we may define matroids over letter set , and use them as the representatives of the isomorphism classes.

Uniform Matroids, Direct Sum and Partition Matroids

The simplest form of matroids may be the uniform matroids:

By putting some uniform matroids over disjoint ground sets together, with their direct sum, we obtain the parition matroids:

The problem of matching in bipartite graph is expressible in the language of the intersection of the independent sets, of two partition matroids:

While the connection above seems like nothing more than an uninteresting coincidence, mathematicians have grasped this clue, discovered and proved its "converse", which is truly mind-blowing: it turns out that finding the maximum (cardinality) common independent set of any two matroids over the same ground set, not limited to partition matroids, is reducible to multiple iterations of finding / augmenting matchings, in delicately constructed bipartite graphs per iteration.

Meantime, there's a min-max duality similar to König-Egerváry Theorem between the maximum cardinality of the common independent sets and the rank functions in each matroids, due to the way we find the maximum common independent set.

We will discuss these in detail in the later topic of matroid intersection theorem.

Linear Matroids and Graphic Matroids

Let's introduce the concept of column matroids first:

While vectorial matroid deduplicates vector as soon as the ground set is defined, defining column matroid allows us to identify elements by which column identity, rather than their underlying vectorial value. We will see why defining so is useful soon.

By now, we may unify matroids that can be represented by certain kind of vector spaces:

On the other hand, we may also unify matroids that can be represented by certain kind of cycle matroids:

Specially, we claim that:

To prove this statement, clearly it suffices to show every cycle matroid has some kinds of linear matroids corresponding to it.

Our construction is, for every cycle matroid , we orient graph arbitrarily into digraph , and take its incidence matrix . Here, we allow loops to be present, by requiring the corresponding column of that loop in to be zero vector. Here's an example of our proposal:

Clearly only can be the elements of , while for any field .

We want to show is the very linear matroid isomorphic to . This will require us to show an edge subset is dependent in iff its corresponding column vectors in are linearly dependent, regardless of which field the matrix is seen as over. Noted that for an oriented edge corresponding to column vector , if it were oriented into instead, the only difference is that its corresponding column vector in becomes now, which doesn't affect the linear independence of the column vectors of . So the way we orient doesn't matter.

Let's begin with showing the necessity:

And since the coefficients of the identity can only be or , such an identity should reveal linear dependence over any field .

Those familiar with Kirchoff's Matrix Tree Theorem should be very familiar with the construction above.

Now let's show the sufficiency, that given a set of linearly dependent column vectors corresponding to edges , a cycle is to be found, and therefore they are dependent in . Again we may assume no edges in is loop, otherwise it's just the trivial case.

Consider the identity revealing the linear dependence of . Without loss of generality, we assume , otherwise we eliminate those terms with zero coefficients. The subset of column vectors with non-zero coefficients is still linearly dependent, but for the corresponding edge subset, once we are able to show there's a cycle inside, any super set of it contains such a cycle.

Our argument of sufficiency is based on the following algorithm:

While every graphic matroid is linear, the converse is not true. The simplest example might be the uniform matroid :

So there's no way for uniform matroid , which is linear and ternary, to be isomorphic to a graphic matroid. Since a graphic matroid must be representable over any field, but is never representable over sufficiently.