AN INTRODUCTION TO MATROID THEORY

KAISER TRAVIS CHAN

Abstract. In this paper, we explore matroids, which generalize properties of linear in-
dependence of vectors and cycles in graphs. We investigate properties and operations on
matroids, then we look at how we can represent matroids using matrices.

1. Introduction
Matroid theory has been used to find properties that generalize concepts in linear algebra
and graph theory. It has first been studied by mathematician Hassler Whitney in 1935, as
shown in his paper called On the abstract properties of linear independence [Whi35]. Whitney
started by giving a definition of a matroid using the concept of a rank function, then derived
properties of sets called independent sets, bases, and circuits from the rank function.
Here, we follow the more standard approach of first defining matroids using independent
sets as defined in 3.1, which from its name, follows from linearly independent sets of vectors
in linear algebra. These independent sets are some subsets of what we call the ground set
of the matroid. We build on this idea in Section 4 where we look at properties of bases and
circuits, which are pulled from linear algebra (basis sets) and graph theory (cycles of graphs),
respectively. After that, in Section 5, we use the rank function to characterize subsets of the
ground set, including conditions for being an independent set, base, or circuit. We derive
the properties of the rank function from our definition of matroids that uses independent
sets.
We also look at examples of matroids, as shown in Section 3, which showcase how our idea
of matroids applies to vectors and graphs, and for vectors we show that it works with both
linear and affine independence. In the other sections, we also look into properties of matroids
applied into these examples. Additionally, in Section 6, we look at how we can geometrically
visualize some matroids defined with affine independence, among other interesting matroids.
We also see what we can do with more than one matroid and what we can do to get another
matroid from one or two matroids. We do this in Section 7, and look at dual matroids (the
term is pulled from duals of graphs), minors of matroids, and the direct sum of matroids.
Lastly, in Section 8, we look at how matroids can be represented using matrices.

2. Background
We first start with prerequisites from some fields that motivate our study of matroids.

2.1. Linear algebra. We discuss the idea of linearly independent sets of vectors based
on [Axl25].

Date: June 24, 2026.

1
2 KAISER TRAVIS CHAN

Definition 2.1. A set S = {v1 , v2 , v3 , . . . , vn } of vectors over a field F is linearly independent

if, for a1 , a2 , a3 , . . . , an ∈ F, the equation
Xn
ai vi = 0
i=1
only has the trivial solution a1 = a2 = a3 = · · · = an = 0. In other words, no vector in S
can be expressed as a linear combination of other vectors in S.
Example. Note that by definition, the zero vector is linearly independent with all other
vectors.
We also define span and basis sets, both related to linear independence of vectors.
Definition 2.2. The span of a set S = {v1 , v2 , v3 , . . . , vn } of vectors over a field F is defined
as the set of vectors that can be obtained from a linear combination of the vectors in S:
( n )
X
span(v1 , v2 , v3 , . . . , vn ) = ai vi | a1 , a2 , a3 , . . . , an ∈ F .
i=1

Definition 2.3. A basis of a vector space V is a set of vectors in V that is linearly indepen-
dent and has span V .
Note that a basis of a vector space is also a linearly independent set of vectors with
maximal cardinality.
We also define affine dependence of vectors [KP09, Chapter 1], which is similar to linear
independence:
Definition 2.4. A multiset S = {v1 , v2 , v3 , . . . , vn } of vectors over a field F is affinely de-
pendent if there exist a1 , a2 , a3 , . . . , an ∈ F where
k
X k
X
ai vi = 0, ai = 0,
i=1 i=1
and all of a1 , a2 , a3 , . . . , ak are not equal to zero. The set S is affinely independent if it is not
affinely independent.
Lastly, we define the rank of a matrix as follows.
Definition 2.5. The rank of a matrix A is defined as the dimension of the span of the
column vectors of A.
2.2. Graph theory. We also look into some definitions from graph theory. [Hil]
Definition 2.6. In a graph G, a walk is a finite sequence of edges v0 v1 , v1 v2 , . . . , vn−1 vn ,
where v0 , v1 , . . . , vn are vertices of G. The walk is a trail if the edges in the sequence are
distinct, and it is a path if the vertices v0 , v1 , . . . , vn are distinct except the case where
v0 = vn . The path is a cycle if v0 = vn .
Definition 2.7. Let G be a graph with n vertices. Then, a spanning tree with n vertices is
a connected subgraph of G with n − 1 edges and n vertices.
Example. Some spanning trees of the complete graph K4 is shown in Figure 1.
One can also note that a spanning tree does not contain any cycles.
 AN INTRODUCTION TO MATROID THEORY 3

Figure 1. Some spanning trees of K4 .

3. Definition and examples of matroids

There are many ways we can define a matroid, all of which are related to independence,
so we start off with the following definition and build the other definitions from this.
Definition 3.1. A matroid is an ordered pair M = (E, I), where E is a finite set called
the ground set and I is the set of independent sets, which is composed of some subsets of E
such that:
I-1. The empty set is independent.
I-2. If A ∈ I, then a set B ⊆ A is also independent.
I-3. (independence augmentation property) If A, B ∈ I such that |B| > |A|, then there is
an element x ∈ B \ A where A ∪ {x} is also independent.
A subset of E that is not independent is called a dependent set.
Notation. We also denote the ground set of a matroid M with E(M).
We saw earlier that linear algebra and graph theory motivated the study of matroids. Let
us look into these two fields and see what can be classified as a matroid in each of these
fields.

3.1. Vector and affine matroids. Firstly, we construct matroids using linear independence
of vectors. We see that linear independence also satisfies the properties stated in Definition
3.1.
Theorem 3.2. Let A be a matrix over a field F, and let E be the set of column vectors of
A. Then, let I be the sets of subsets of E that are linearly independent over F. Then, (E, I)
is a matroid and is called a vector matroid, denoted by M [A].
Proof. We show that (E, I) is a matroid by checking if it satisfies the properties in Definition
3.1. Note that I satisfies I-1 and I-2. So, we verify as follows that I-3 is also satisfied, as
shown in [Oxl03].
Let A and B be linearly independent subsets of E where |B| = |A| + 1. Then, let V
be the vector space that is the span of A ∪ B. Then, dim V ≥ |B|. If A ∪ {x} is linearly
dependent for all x ∈ B \ A, then V is in the span of A, thus dim V ≤ |A|. This means that
|B| ≤ dim V ≤ |A|. However, |B| > |A|, so we have a contradiction. Therefore, there exists
an element x ∈ B \ A where A ∪ {x} is linearly independent.
We thus conclude that (E, I) is a matroid. ■

Let us look at an example of an independent set of a vector matroid.

4 KAISER TRAVIS CHAN

5 4
d
3
g f
c b
1 a 2

Figure 2. An example graph H, together with one of the independent sets

from M (H).

Example. Suppose we have  

1 0 1 1 0
A = 0 0 1 0 1 .
1 1 0 0 0
     
 1 0 0 
Then, one independent set of the vector matroid M [A] is X =  0 , 0 , 1 . Notice
   
 1 1 0 
that all its subsets are linearly independent, satisfying I-2.    
 0 1 
Another independent set of the vector matroid is Y =  0 , 0 . Since |X| > |Y |,
 
 1 0 
by I-3, there exists an element
  x ∈ X \ Y where Y∪ {x}  is independent.
  We can see
0  0 1 0 
that this element is x = 1, resulting in Y ∪ {x} = 0 , 0 , 1 , which is linearly
0  1 0 0 
independent.
We can also do a similar construction of matroids using affine independence [KP09, Chap-
ter 1]:
Theorem 3.3. Let A be a matrix over a field F, and let E be the set of column vectors of
A. Then, let I be the sets of subsets of E that are affinely independent over F. Then, (E, I)
is a matroid and is called an affine matroid.
3.2. Graphic matroids. We can also construct matroids from graphs, where the subgraphs
without cycles are independent [Oxl03]:
Theorem 3.4. Let G = (V, E) be a graph, and let I be the set of edges that have no cycles
in G. Then, (E, I) is a matroid and is called a cycle matroid, denoted by M (G).
Example. Consider graph H shown in Figure 2 with edges a, b, c, d, e, f, g. One of the in-
dependent sets of M (H) will be the set {d, e, f } as the corresponding subgraph does not
contain any cycles.
We can also note that some matroids are isomorphic to cycle matroids, and we call these
graphic matroids.
 AN INTRODUCTION TO MATROID THEORY 5

Definition 3.5. A graphic matroid is a matroid that is isomorphic to a cycle matroid of a

graph.
3.3. Other types of matroids. We also present other examples of matroids with their own
names.
Proposition 3.6. If E is a set with n elements and I is the set of all subsets A of E such
that |A| = r for some integer r where 0 ≤ r ≤ n, then Ur,n = (E, I) is a matroid and is
called a uniform matroid.
Proposition 3.7. Let A1 , A2 , A3 , . . . , An be disjoint sets, and let E = A1 ∪A2 ∪A3 ∪· · ·∪An .
Then, let I be the set of all subsets of E that contain zero or one element from each of
A1 , A2 , A3 , . . . , An . Then, (E, I) is a matroid and is called a transversal matroid.
4. Bases and circuits
We can also define matroids in terms of bases and circuits, which are both based on
independent sets. The proofs of the theorems are also found in [KP09, Chapter 1].
4.1. Bases. We first define bases of a matroid to match the definition of a basis of a vector
space.
Definition 4.1. A base of a matroid M is an independent set of M with maximal cardinality.
From this, we can prove the following result, motivated by the fact that basis vectors in a
vector space have the same cardinality.
Proposition 4.2. All bases of a matroid M have the same cardinality, called the rank of
M [Duk04], denoted by r(M).
Proof. Let B1 and B2 be bases where |B2 | > |B1 |. Then, by property I-3 in Definition 3.1,
there exists an element x ∈ B2 \ B1 where B2 ∪ {x} is independent. However, since B2 is
a base, it is an independent set with maximal cardinality, so adding x makes the resulting
set dependent, thus a contradiction. Therefore, it is impossible for one to choose two bases
from a matroid that have differing cardinalities. ■
We can also define a matroid in terms of its bases as shown below, and we can prove that
this definition is consistent with Definition 3.1.
Lemma 4.3. The set of bases B of a matroid with ground set E satisfies the following
properties:
B-1. The set B is not empty.
B-2. ( exchange property) If B1 , B2 ∈ B and x1 ∈ B1 \ B2 , there exists an element x2 ∈
B2 \ B1 such that B1 \ {x1 } ∪ {x2 } is also a base.
Proof. Since the set of independent sets, I, is not empty due to it containing the empty set
(according to property I-1), we know that B is not empty, satisfying property B-1.
Now we prove property B-2. Suppose we have two bases B1 and B2 with an element x1 ∈
B1 \B2 . Then, B1 \{x1 } is independent by property I-2. We also know that B2 is independent
since it is a base, and by Proposition 4.2, we have |B1 | = |B2 |, so |B2 | > |B1 \ {x1 }|. So, by
property I-3, there exists another element x2 ∈ B2 \ (B1 \ {x1 }) where B1 \ {x1 } ∪ {x2 } is
independent. Since x2 ∈ B2 \ B1 and |B1 \ {x1 } ∪ {x2 }| = |B1 |, we know that B1 \ {x1 } ∪ {x2 }
is also a base. ■
6 KAISER TRAVIS CHAN

5 4
d
3
g f
c b
1 a 2

Figure 3. An example graph H, together with one of the bases from M (H).

We also state the following, which claim that the properties we gave for bases fully char-
acterize a matroid. We leave the proof to [KP09, Chapter 1].
Theorem 4.4. Let E be a set and B be the set of subsets of E that satisfy the properties
in Lemma 4.3. Then, let I be the set of subsets of E that are subsets of an element of B.
Then, (E, I) is a matroid.
Corollary 4.5. A set of subsets of a ground set of a matroid is the set of bases if and only
if it satisfies the properties listed in Lemma 4.3.
Let us look at examples of bases in both vector and graphic matroids.
Example. In a vector matroid on a matrix A, the bases are the maximal linearly independent
sets of columns of A, which are the basis sets of A.
Let us once again investigate our matrix from earlier,
 
1 0 1 1 0
A = 0 0 1 0 1 .
1 1 0 0 0
     
 1 0 0 
Then, one base of the vector matroid M [A], or basis of A, is X = 0 , 0 , 1 , and
   
 1 1 0 
     
 1 1 0 
another is Y = 0 , 1 , 1 . We can exchange the second elements of each of the
   
1 0 0
 
bases, which results in X becoming Y and Y becoming X.
Example. In a graphic matroid M (G) where G has n vertices, the bases are the spanning
trees with n vertices that are subgraphs of G. For instance, in graph H shown in Figure 3
with edges a, b, c, d, e, f, g, one of the bases of the graphic matroid M (G) is {a, d, e, f } since
it is a spanning tree and a subgraph of H.

4.2. Circuits. We also look into circuits, which are defined as follows:
Definition 4.6. A circuit is a dependent set of a matroid with minimal cardinality.
Just like bases, circuits also have a list of properties that they satisfy, as shown in the
following lemma.
 AN INTRODUCTION TO MATROID THEORY 7

Lemma 4.7. The set of circuits C of a matroid with ground set E satisfies the following
properties:
C-1. The empty set is not a circuit.
C-2. If A ∈ C, then all proper subsets of A are not circuits.
C-3. ( circuit elimination property) If C1 , C2 ∈ C, where C1 ̸= C2 , and x ∈ C1 ∩ C2 , then
(C1 ∪ C2 ) \ {x} contains a circuit.
Proof. Firstly, by property I-1, we know that the empty set is independent, so it is not a
circuit, thus property C-1 is true. Also, since circuits have minimal cardinality, no subset of
a circuit is a circuit, satisfying property C-2.
Now, we prove C-3 as shown in [KP09, Chapter 1]. Assume for the sake of contradiction
that (C1 ∪ C2 ) \ {x} does not contain a circuit. Then, it is independent. By C-2, we know
that if an element e belongs to C2 \ C1 , then C2 \ {e} is independent since C2 is a circuit.
Let I be an independent subset of C1 ∪C2 that has maximum cardinality such that C2 \{e}.
Since C2 is a circuit, we know that e ∈ / I. Also, since I is not a subset of C1 , there exists
an element f ∈ C1 \ I. We stated earlier that e ∈ C2 \ C1 , so e and f are distinct elements.
Therefore,
|I| ≤ |(C1 ∪ C2 ) \ {e, f }| = |C1 ∪ C2 | − 2 < |(C1 ∪ C2 ) \ {x}|.
So, |I| < |(C1 ∪ C2 ) \ {x}|, which means we can apply property I-3 to get that there exists
an element g ∈ (C1 ∪ C2 \ {x}) \ I where I ∪ {g} is independent. However, I has maximal
cardinality, giving us a contradiction.
Therefore, (C1 ∪ C2 ) \ {x} contains a circuit. ■
Just like with bases, we also state the following, which claim that the properties we gave
for circuits fully characterize a matroid. We once again leave the proof to [KP09, Chapter
1].
Theorem 4.8. Let E be a set and C be the set of subsets of E that satisfy the properties
in Lemma 4.7. Then, let I be the set of subsets of E that do not contain an element of C.
Then, (E, I) is a matroid.
Corollary 4.9. A set of subsets of a ground set of a matroid is the set of circuits if and
only if it satisfies the properties listed in Lemma 4.7.
We also define the following [KP09, Chapter 1]:
Definition 4.10. A loop of a matroid with ground set E is an element x of E such that {x}
is a circuit.
We now explore circuits through examples in vector and graphic matroids.
Example. In a vector matroid of a matrix A, the circuits are the minimal linearly dependent
sets of column vectors of A. For instance, we can consider our matrix from earlier,
 
1 0 1 1 0
A = 0 0 1 0 1 .
1 1 0 0 0
           
 1 1 0   1 0 1 
Then, two of the circuits of M [A] are X = 1 , 0 , 1 and Y = 0 , 0 , 0 .
 0 0 0   1 1 0 
By C-3, there exists an element e ∈ X ∩ Y where (X ∪ Y ) \ {e} contains a circuit, and in
8 KAISER TRAVIS CHAN

5 4
d
3
g f
c b
1 a 2

Figure 4. An example graph H, together with one of the circuits from

M (H).
          
1  1 0 1 0 
this case, this element is e = 0 . We then have (X ∪ Y ) \ {e} =
  1 , 1 , 0 , 0 ,
     
0 0 0 1 1
 
which is itself a circuit.
Example. In a graphic matroid M (G), the circuits are the cycles in G with at least one edge.
We know that these are of minimal cardinality because if we remove an edge from the cycle,
then the resulting subgraph has no cycles. For example, in graph H shown in Figure 4 with
edges a, b, c, d, e, f, g, one of the circuits of M (H) is {a, b, d, f }.

5. The rank function

In Whitney’s paper, [Whi35], the first definition of matroids that was given used the rank
function; however, we use a different definition here that is consistent with the original one.
We will also see that this definition of matroids is consistent with Definition 3.1, which uses
independent sets.
Definition 5.1. The rank function rM : 2E → N ∪ {0} of a matroid M with ground set E
is defined such that, if A ⊆ E, then r(A) is the cardinality of the largest independent set
contained in A. If the matroid being referred to is clear, we usually shorten rM to r.
We now define matroids using the rank function as follows:
Lemma 5.2. The rank function r of a matroid with ground set E satisfies the following
properties:
R-1. For a subset A of E, we have 0 ≤ r(A) ≤ |A|.
R-2. If A ⊆ B ⊆ E, then r(A) ≤ r(B).
R-3. ( submodularity property) If A, B ⊆ E, we have r(A ∪ B) + r(A ∩ B) ≤ r(A) + r(B).
Proof. Note that R-1 is true because the size of the largest independent subset is always
nonnegative and cannot be greater than |A|. Also, R-2 is true because if r(A) > r(B),
then A contains an independent set with cardinality larger than the largest independent
subset of B, which cannot be the case since A ⊆ B. We now prove property R-3 as shown
in [KP09, Chapter 1].
Let X∩ and X∪ be inclusion-wise maximal independent subsets of A ∩ B and A ∪ B,
respectively, such that X∩ ⊆ X∪ . Then, by I-2, since X∪ ∩ A ⊆ X∪ , we know that X∪ ∩ A is
 AN INTRODUCTION TO MATROID THEORY 9

an independent subset of A. Thus, we have r(X∪ ∩ A) = |X∪ ∩ A|. Also, since X∪ ∩ A ⊆ A,

we have by R-2 that r(X∪ ∩ A) ≤ r(A), or |X∪ ∩ A| ≤ r(A). Similarly, |X∪ ∩ B| ≤ r(B).
Therefore, we have
r(A) + r(B) ≥ |X∪ ∩ A| + |X∪ ∩ B|
= |(X∪ ∩ A) ∪ (X∪ ∩ B)| + |(X∪ ∩ A) ∩ (X∪ ∩ B)|
= |X∪ ∩ (A ∪ B)| + |X∪ ∩ (A ∩ B)|
= |X∪ | + |X∩ |
= r(A ∪ B) + r(A ∩ B),
completing our proof of R-3. ■
5.1. Independent sets, bases, and circuits in terms of the rank function. Before
we characterize the independent sets of a matroid using the rank function, we first state and
prove the following lemma based on [KP09, Chapter 1].
Lemma 5.3. Let E be a finite set, and let r : 2E → N \ {0} satisfy the three properties in
Lemma 5.2. Then, let A, B ⊆ E where for every element x ∈ B \ A, we have r(A ∪ {x}) =
r(A). Then, we have r(A ∪ B) = r(A).
Proof. We prove the lemma by inducting on k = |B \ A|. Suppose B \ A = {x1 , x2 , . . . , xk }.
Note that if k = 1, then B \ A = {x1 }, and since we know from the condition that r(A ∪
{x1 }) = r(A), our claim is true and thus the base case is satisfied.
Now, assume the lemma is true for |B \ A| = k − 1 where k ≥ 2; that is, r(A) =
r(A ∪ {x1 , x2 , . . . , xk−1 }). We will prove that it is also true for |B \ A| = k. Note that
r(A) = r(A ∪ {xk }) by our condition. This means that
r(A) + r(A) = r(A ∪ {x1 , x2 , . . . , xk−1 }) + r(A ∪ {xk }).
Additionally, note that (A ∪ {x1 , x2 , . . . , xk−1 }) ∪ (A ∪ {xk }) = A ∪ {x1 , x2 , . . . , xk } and
(A ∪ {x1 , x2 , . . . , xk−1 }) ∩ (A ∪ {xk }) = A, so by R-3, we have
r(A ∪ {x1 , x2 , . . . , xk−1 }) + r(A ∪ {xk }) ≥ r(A ∪ {x1 , x2 , . . . , xk }) + r(A).
By R-2, since A ⊆ A ∪ {x1 , x2 , . . . , xk }, we have r(A ∪ {x1 , x2 , . . . , xk }) ≥ r(A), so
r(A ∪ {x1 , x2 , . . . , xk }) + r(A) ≥ r(A) + r(A).
We would then have:
r(A) + r(A) = r(A ∪ {x1 , x2 , . . . , xk−1 }) + r(A ∪ {xk })
≥ r(A ∪ {x1 , x2 , . . . , xk }) + r(A)
≥ r(A) + r(A).
However, r(A) + r(A) = r(A) + r(A), so the inequalities listed above are actually equalities.
Therefore, r(A) + r(A) = r(A ∪ {x1 , x2 , . . . , xk }) + r(A), or r(A) = r(A ∪ {x1 , x2 , . . . , xk }) =
r(A ∪ (B \ A)) = r(A ∪ B), thus completing the inductive step.
Therefore, the lemma is true for all such values of B \ A by the principle of mathematical
induction. ■
Now, we can use Lemma 5.3 to prove the following, which shows the condition for inde-
pendent sets based on the rank function. We once again base the proof on [KP09, Chapter
1].
10 KAISER TRAVIS CHAN

Theorem 5.4. Let E be a finite set, and let r : 2E → N \ {0} satisfy the three properties in
Lemma 5.2. Then, let I be the set of A ⊆ E where r(A) = |A|. Then, (E, I) is a matroid
with rank function r.
Proof. We prove that the given conditions satisfy the properties listed in Definition 3.1.
Firstly, r(∅) = 0 = |∅| by R-1, so ∅ is independent, satisfying property I-1.
We now prove that I-2 holds given our setup. Consider an element A of I, and let A′ be
a subset of A. Note that applying R-3 on sets A′ and A \ A′ gives
r(A) + r(∅) ≤ r(A′ ) + r(A \ A′ )
since A′ ∪ (A \ A′ ) = A and A′ ∩ (A \ A′ ) = ∅. Additionally, by R-1 we have r(A′ ) ≤ |A′ |
and r(A \ A′ ) ≤ |A \ A′ |, so we have
|A| = r(A) = r(A) + r(∅)
≤ r(A′ ) + r(A \ A′ )
≤ |A′ | + |A \ A′ | = |A|.
Since |A| = |A|, the inequalities listed are equalities, so r(A′ ) + r(A \ A′ ) = |A′ | + |A \ A′ |.
However, r(A′ ) ≤ |A′ | and r(A \ A′ ) ≤ |A \ A′ |, so r(A′ ) = |A′ |, therefore A′ ∈ I. Since
A′ ⊆ A, we have proved property I-2.
We now prove that I-3 also holds. Consider two elements A and B of I where |B| > |A|.
Also, suppose for the sake of contradiction that for all x ∈ B \ A, we have A ∪ {x} ∈ / I.
Then, since r(A ∪ {e}) ̸= |A ∪ {e}| = |A| + 1, we know by R-1 that |A| + 1 > r(A ∪ {e}).
Also, by R-2, we have r(A ∪ {e}) ≥ r(A) = |A|. Putting these together, we have
|A| + 1 > r(A ∪ {e}) ≥ r(A) = |A|,
so r(A ∪ {e}) = |A|. Thus, by Lemma 5.3, we have r(A) = r(A ∪ B). We also have by R-2
that r(A ∪ B) ≥ r(A), so
r(B) ≤ r(A ∪ B) = r(A) = |A| < |B|.
Therefore, r(B) < |B|, which means I2 ∈ / I, thus giving us a contradiction. Therefore,
I2 ∈ I, satisfying I-3.
We also need to prove that r is the rank function of M = (E, I). To do this, we consider
a subset A of E. Note that if A is independent in M, then r(A) = |A| = rM (A). If A is not
independent in M, then we let I be an independent subset of X with maximal cardinality.
Then, for every x ∈ X \I we have I ∪{x} ̸= I, so r(I ∪{x}) = r(I). Thus, by Lemma 5.3, we
have that r(X) = r(I) = rM (I). Therefore, for all subsets A of E, we have r(A) = rM (A),
so r is the rank function of the matroid M. ■
Corollary 5.5. Let E be a set. A function r with domain 2E is the rank function of a
matroid with ground set E if an only if r satisfies the properties listed in Lemma 5.2.
Given that we characterized independent sets in terms of the rank function in 5.4, we also
give conditions for the bases and circuits as follows [KP09, Chapter 2]:
Proposition 5.6. Let M be a matroid with r as its rank function. Then, for any subset A
of E(M), we have:
(1) A is a base if and only if |A| = r(A) = r(M).
(2) A is a circuit if and only if A ̸= ∅ and for all x ∈ A we have r(A \ {x}) = |A| − 1 =
r(A).
 AN INTRODUCTION TO MATROID THEORY 11

6
5
4
1 2 3

Figure 5. A visualization that does not give a matroid, as described

in [KP09, Chapter 1]

5.2. Examples of rank functions. Let us now look at how the rank function applies in
vector and graphic matroids.
Proposition 5.7. Let A be a matrix over a field F, and let E be the set of column vectors
of A. Then, the rank function of the vector matroid of A is given by the rank of the matrix
formed by each subset of E.
Proposition 5.8. Let G = (V, E) be a graph. Then, the rank function of M (G) is given by
the largest number of edges in each subgraph of G that has no cycles.

6. Geometric visualizations of matroids

We first explore a property of affine matroids by rank, as described in [KP09, Chapter 1],
starting with those with rank three.
Let E be a multiset of vectors in R2 , interpreted as points on the Cartesian plane. Then,
a subset A ⊆ E is affinely dependent if it contains two points at the same position, three
collinear points, or four or more coplanar points.
Similarly, in an affine matroid of rank four, the vectors, which we again interpret as points,
are in R3 . A subset in this case would be affinely dependent if it contains two points at the
same position, three collinear points, four coplanar points, or five or more points in space.
Using the idea from affine matroids, we can draw diagrams of matroids with rank at most
4 by assigning each element of the ground set to a point, and these points are positioned
so that circuits with two elements correspond to identical points, those with three elements
correspond to collinear points, and those with four elements correspond to coplanar points.
Not all visualizations can give matroids, as shown in the following example given in [KP09,
Chapter 1].
Example. The diagram shown in Figure 5 does not represent a matroid. To see this, consider
subsets A = {1, 2, 3, 4, 5} and B = {1, 2, 5, 6, 7} of the ground set E = {1, 2, 3, 4, 5, 6, 7}.
Then, r(A) = 3, r(B) = 3, r(A ∪ B) = 4, and r(A ∩ B) = 4, thus violating R-3 since
r(A ∪ B) + r(A ∩ B) > r(A) + r(B).
These constructions do not need to be in Rn . For instance, the Fano matroid has its
visualization on the projective plane over GF (2) instead of the Cartesian plane R2 [KP09,
Chapter 1]:
Proposition 6.1. Let E = {1, 2, 3, 4, 5, 6, 7} be the set of points in the Fano plane, which
is the projective plane over GF (2) = Z/2Z. Then, let I be the set of sets of points that are
12 KAISER TRAVIS CHAN

2 6
7

3 4 5

Figure 6. The Fano matroid F7 .

not collinear in the Fano plane. Then, (E, I) is a matroid and is called the Fano matroid
F7 , depicted in Figure 6. 1

7. Duals, minors, and the direct sum

Now that we investigated properties of matroids, we look at what we can do with matroids
to get other matroids. Specifically, we will explore dual matroids, minors of matroids, and
the direct sum or union of matroids.
7.1. Duals of graphs and matroids. To get some background, we define duals of graphs
as follows.
Definition 7.1. Let G be a graph. The dual of G, denoted by G∗ , is constructed by placing a
vertex representing every face or region of G, then drawing an edge between pairs of vertices
that represent adjacent faces.
Example. An example graph H together with its dual graph is shown in Figure 7. Note that
since an edge also connects two faces, each edge of H ∗ corresponds to an edge in H, and we
label them like so (e.g. a′ corresponds to a).
Take a spanning tree of H, for example {a, c, f, g}. Its complement is then {b, d, e}, which
corresponds to {b′ , d′ , e′ }. Note that {b′ , d′ , e′ } is also a spanning tree of H ∗ . We can observe
with other spanning trees that the spanning trees of H ∗ are complements of those of H.
Our observation that the spanning trees of G∗ are complements of the spanning trees of
G is true for every graph [Oxl03]. So, we generalize this definition to matroids.
Theorem 7.2. Let M = (E, I) be a matroid with B as the set of its bases. Then, let
B ∗ = {E \ x | x ∈ B} be the set of complements of the elements of B. Then, B ∗ is a set of
bases of another matroid with ground set E.
We thus define dual matroids based on Theorem 7.2:
Definition 7.3. The dual of a matroid M with B as the set of its bases, denoted as M∗ ,
is defined so that its set of bases, B ∗ = {E \ {x} | x ∈ B}, is the set of complements of the
elements of B. The bases of M∗ are called cobases and its circuits are called cocircuits. The
rank function of M∗ , denoted by r∗ , is called the corank function.
1Notethat despite the fact that {2, 4, 6} are connected by a circle in our diagram, they are still treated
as collinear.
 AN INTRODUCTION TO MATROID THEORY 13

e
8
d′
5 4
d
′
f
e′ 7 3
g f
g′ c′
c b
6

1 a 2

9 a′

b′

Figure 7. An example graph H with its dual H ∗ in blue.

Let us look at duals of uniform matroids as an example of this concept.

Example. In the uniform matroid Ur,n , the bases are the subsets of the ground set with r
∗
elements, so those of Ur,n are the subsets of the ground set with n − r elements, therefore
∗
Ur,n = Un−r,n . Thus, the dual of a uniform matroid is also a uniform matroid.
Note that we call M∗ the dual of M due to the following property.
Proposition 7.4. Let M be a matroid. Then, (M∗ )∗ = M.
We also discuss properties of the corank function of a matroid [KP09, Chapter 2].
Proposition 7.5. Let M be a matroid. Then, r(M) + r∗ (M∗ ) = |E(M)| = |E(M∗ )|.
In fact, the above property is a special case of the following proposition, which generalizes
this to any subset of the ground set of the matroid. This also gives us a formula for the
corank of a subset of the ground set.
Proposition 7.6. Let M be a matroid with ground set E, and A be a subset of E. Then,
r∗ (A) = |A| − r(M) + r(E \ A).
We also state the following, which gives some information about cocircuits of a matroid
according to [Oxl03].
14 KAISER TRAVIS CHAN

Theorem 7.7. Let M be a matroid. We then have the folowing:

(1) A set C ∗ is a cocircuit of M if and only if C ∗ has a non-empty intersection with
every base of M while having minimal cardinality.
(2) A set B is a base of M if and only if B has a non-empty intersection with every
cocircuit of M while having minimal cardinality.
We will also soon see that the duals of matroids when other operations are applied give
special properties.
7.2. Minors of matroids. We first define two operations on matroids, namely deletion and
contraction.
Definition 7.8. Let M be a matroid with ground set E. When a subset A is deleted from
E, the resulting matroid M\A (or M|(E \A)) has the ground set E \A and the independent
sets are the subsets of E \ A that are also independent in M.
Definition 7.9. Let M be a matroid with ground set E. When a subset A is contracted
from E, the resulting matroid M/A is the same as the matroid obtained from deleting A in
the dual matroid M∗ .
We are now ready to define minors of matroids in terms of these two operations.
Definition 7.10. A minor of a matroid M is a matroid that can be obtained from M by
a sequence of deletions and contractions.
We will see that any minor can be expressed as the original matroid with one deletion and
one contraction applied to it. We first prove the following:
Proposition 7.11. Let M be a matroid with ground set E. Let A ⊆ E and X ∈ E \ A.
Then, we have
(7.1) rM\A (X) = rM (X),
(7.2) rM/A (X) = rM (X ∪ A) − rM (A).
Proof. Since X does not contain any elements that are in A, the largest independent sets
contained in X in the matroids M and M \ A are the same, so their cardinalities are equal.
Therefore, rM\A (X) = rM (X), satisfying Equation 7.1.
Now, we prove Equation 7.2 as follows, based on the proof in [KP09, Chapter 2], using the
property of the corank function described in Proposition 7.6. Firstly, we have the following,
with the second equality coming from Equation 7.1:
rM/A (X) = |X| + rM∗ \A (E \ A \ X) − rM∗ \A (E \ A)
∗ ∗
= |X| + rM (E \ (A ∪ X)) − rM (E \ A).
Now, by Proposition 7.6, we have
∗
rM (E \ (A ∪ X)) = |E \ (A ∪ X)| + rM (A ∪ X) − rM (E),
∗
rM (E \ A) = |E \ A| + rM (A) − rM (E).
This means that our expression becomes
∗ ∗
rM/A (X) = |X| + rM (E \ (A ∪ X)) − rM (E \ A)
= |X| + (|E \ (A ∪ X)| + rM (A ∪ X) − rM (E)) − (|E \ A| + rM (A) − rM (E)).
■
 AN INTRODUCTION TO MATROID THEORY 15

Now we prove the following lemma, based on [KP09, Chapter 2], which indicates that
deletions and contractions are actually commutative, both with themselves and with each
other, and that we can combine deletions and contractions into their unions.
Lemma 7.12. Let M be a matroid with ground set E, and let A and B be disjoint subsets
of E. We then have
(7.3) (M \ A) \ B = M \ (A ∪ B) = (M \ B) \ A,
(7.4) (M/A)/B = M/(A ∪ B) = (M/B)/A,
(7.5) (M/A) \ B = (M \ B)/A.
Proof. Note that Equation 7.3 follows from the definition of deletion, because each sequence
of operations removes the same elements and the same independent sets. Equation 7.4 follows
from Equation 7.3 but instead considering the corresponding dual matroid.
We now prove Equation 7.5 by showing that (M/A) \ B and (M \ B)/A have the same
rank function. Consider a subset X of E \ (A ∪ B). Then, we have by Equation 7.1 that
r(M/A)\B (X) = rM/A (X), which by Equation 7.2 is equal to rM (X ∪ A) − rM (A). We then
apply Equation 7.1 to each term to get
rM (X ∪ A) − rM (A) = rM\B (X ∪ A) − rM\B (A),
which by Equation 7.2 is equal to r(M\B)/A (X). Putting this together, we have
r(M/A)\B (X) = rM/A (X)
= rM (X ∪ A) − rM (A)
= rM\B (X ∪ A) − rM\B (A)
= r(M\B)/A (X),
therefore (M/A) \ B and (M \ B)/A have the same rank function, thus completing our proof
for Equation 7.5. ■
Note that Lemma 7.12 shows that any sequence of deletions and contractions can be
written as just one deletion and one contraction by combining all deletions into one deletion
involving the union of the sets being deleted, and doing the same for the contractions.
We also state a property, according to [KP09, Chapter 2], of minors of matroids when it
comes to their duals. Note that this follows from the fact that for disjoint subsets A, B of
E(M), we have N = M \ A/B if and only if N ∗ = M∗ /X \ Y .
Proposition 7.13. Let M and N be two matroids. Then, N is a minor of M if and only
if N ∗ is a minor of M∗ .
7.3. Direct sum of matroids. We now define the union or direct sum of two matroids
using the union of disjoint ground sets:
Proposition 7.14. Let M1 = (E1 , I1 ) and M2 = (E2 , I2 ) be matroids, where E1 and E2
are disjoint. Then, define I to be the set of subsets A of E1 ∪ E2 where A ∩ E1 and A ∩ E2
are independent in M1 and M2 , respectively. Then, (E1 ∪ E2 , I) is a matroid and is called
the union or direct sum of M1 and M2 , denoted by M1 ⊕ M2 .
We also present some properties of direct sums, characterizing their circuits, bases, and
rank function.
16 KAISER TRAVIS CHAN

Proposition 7.15. Let M1 = (E1 , I1 ) and M2 = (E2 , I2 ) be matroids with disjoint ground
sets, and let B(M) and C(M) denote the sets of bases and circuits of a matroid M. Then,
we have:
(1) The set of bases of M1 ⊕ M2 is the set of B1 ∪ B2 for all possible B1 ∈ B(M1 ) and
B2 ∈ B(M2 ).
(2) The set of circuits of M1 ⊕ M2 is the same as C(M1 ) ∪ C(M2 ).
(3) For all subsets A of the ground set of M1 ⊕ M2 , we have
rM1 ⊕M2 = rM1 (A ∪ E1 ) + rM2 (A ∪ E2 ).
Additionally, we state the following proposition which specifies how we can get the dual
of the direct sum of two matroids. The proof is found in [KP09, Chapter 2].
Proposition 7.16. Let M1 and M2 be matroids with disjoint ground sets. Then,
(M1 ⊕ M2 )∗ = M∗1 ⊕ M∗2 .

8. Representability of matroids
Definition 8.1. A matroid with n elements is F-representable if each element of the ma-
troid can be mapped to a column vector in a matrix A with n columns over the field F so
that the column vectors corresponding to the elements in each independent set are linearly
independent. The matrix A is called the F-representation of the matroid. Additionally, a
matroid is representable if there exists a field F such that the matroid is F-representable.
Definition 8.2. A matroid is binary if it can be represented over the field GF (2) = Z/2Z
and ternary if it can be represented over the field GF (3) = Z/3Z.
Given this definition, consider the following example of the representability of a uniform
matroid. The proof is also in [Oxl03].
Proposition 8.3. The uniform matroid U2,4 is binary but not ternary.
Proof. We first prove that U2,4 is not binary. Suppose for the sake of contradiction that it is
representable over GF (2). Then, the representation A has four columns and would become
 
0 0 1 1
A= .
0 1 0 1
Notice that A does not have four nonzero columns, so there is a set of two vectors that is
linearly dependent (specifically, the zero vector and any of the other columns are linearly
dependent), giving us a contradiction since each column of A must be distinct. Thus, U2,4
cannot be represented over GF (2) and is thus not binary.  
1 0 1 1
Additionally, U2,4 is ternary because it can be represented by the matrix .
0 1 1 −1
■

8.1. Representability of graphic matroids. As usual, we also want to look into graphic
matroids. First, let us define the vertex-edge incidence matrix of a graph, which allows us
to connect graph theory and linear algebra.
 AN INTRODUCTION TO MATROID THEORY 17

Definition 8.4. Let G be a graph. The vertex-edge incidence matrix of G is the matrix that
has rows labeled with the vertices of G and the columns labeled with the edges of G. If an
edge e in G is a loop (that is, it connects a vertex to itself), then the column corresponding
to e is the zero vector. Otherwise, the entry corresponding to vertex v and edge e of G is 1
if v is an end-vertex of e and 0 if it is not [Oxl03].
For us to get an understanding of how this is constructed, let us once again look at our
graph H shown in Figure 2.
Example. Consider graph H shown in Figure 2. The vertex-edge incidence matrix would
then be as follows:
a b c d e f g
1 1 0 1 0 0 1 1
 
2 1 1 0 0 0 0 0
AH = 3 0 1 1 1 1 0 0.

4 0 0 0 1 0 1 0
5 0 0 0 0 1 0 1

The surprising fact about graphic matroids is that all of them are binary, and we can
use the vertex-edge incidence matrix as described in Definition 8.4 to represent such graphic
matroids. We show this is true based on [Oxl03].
Theorem 8.5. Let G be a graph with vertex-edge incidence matrix AG . Then, the vector
matroid M [AG ] viewed over GF (2) has all subsets of E that do not contain the edges of a
cycle in G as its independent sets. Then, M [AG ] = M (G), and M (G) is binary.
Proof. Note that by the definition of representability as described in Definition 8.1, we only
need to prove that a subset S of columns of AG is linearly dependent if and only if S contains
a set of edges of graph G that form a cycle.
Suppose that S contains the set of edges of a cycle C in graph G. If C is a loop, then the
column corresponding to the sole edge of C is the zero vector, thus S is linearly dependent.
Otherwise, each vertex in C is met by exactly two edges of C. This means that the sum of
the columns of C is the zero vector when taken modulo 2, leading to S also being linearly
dependent in this case. Therefore, if S contains the set of edges of a cycle C in G, then S is
linearly dependent.
Now we prove the converse; that is, if S is a linearly dependent set of columns of AG , then
it also contains the set of edges of a cycle in G. Suppose that S is linearly dependent. Then,
let D ⊆ S be a circuit of M [AG ] that does not contain the zero vector as a column. We then
have that the sum of the columns of D taken modulo 2 is the zero vector, so every vertex
that is an end-vertex of an edge of D is an end-vertex of at least two edges in D.
Let d1 be an edge of D with end-vertices v0 and v1 . Then, v1 is also an end-vertex of
another edge d2 ∈ D, which has v2 as is other end-vertex. We can use this idea to make a
sequence d1 , d2 , d3 , . . . of edges of D and another sequence v0 , v1 , v2 , . . . of vertices that are
met by these edges. Since we know that G is finite, we will eventually get a vertex v in the
sequence that will repeat, and once this happens we get a cycle in D starting at v. This
means that D contains the edges of a cycle in G, completing our proof. ■
8.2. The Vámos matroid. However, not all matroids are representable by a field. Consider
the following example, as described in [FHJK23, KP09].
18 KAISER TRAVIS CHAN

1 2

4 3

Figure 8. The Vámos matroid V8 .

Definition 8.6. Let E = {1, 2, 3, 4, 5, 6, 7, 8} and

A = {{1, 2, 3, 4}, {1, 4, 5, 6}, {1, 4, 7, 8}, {2, 3, 5, 6}, {2, 3, 7, 8}}.
Then, there exists a matroid M where all subsets of E with at most three elements are
independent, and the five elements of A are the only circuits. This is called the Vámos
matroid, depicted by Figure 8, and is denoted by V8 .
A surprising fact about this matroid is it is not representable over any field; we leave the
proof to [KP09, Chapter 6].
Proposition 8.7. The Vámos matroid V8 is not representable over any field.

9. Acknowledgements
I would like to thank Dr. Simon Rubinstein-Salzedo for the opportunity for me to write
this paper via the 2025 Euler Circle Independent Research and Paper Writing class, and
Ethan Martirosyan for guiding me throughout this process by giving helpful insights and
resources and clarifying confusions.

References
[Axl25] Sheldon Axler. Linear algebra done right. Fourth edition, 06 2025. [Link]
[Link].
[Duk04] W. M. B. Dukes. The number of matroids on a finite set, 2004. [Link]
0411557.
[FHJK23] Ragnar Freij-Hollanti, Relinde Jurrius, and Olga Kuznetsova. Combinatorial derived matroids.
Electronic Journal of Combinatorics, 30(2):2–8, 2023. [Link]
[Link]/eljc/article/view/v30i2p8/pdf.
[Hil] Hayley Hillman. Matroid theory. [Link]
Mathematics/[Link].
[KP09] Daniel Král’ and Ondřej Pangrác. Introduction to matroid theory (lecture notes). Matfyzpress,
2009. [Link]
[Oxl03] James Oxley. What is a matroid? Cubo, 5(179):780, 2003. [Link]
[Link].
 AN INTRODUCTION TO MATROID THEORY 19

[Whi35] Hassler Whitney. On the abstract properties of linear dependence. American Journal of Mathe-
matics, 57(3):509–533, 1935. [Link]

Philippine Science High School - Main Campus in Diliman, Quezon City, Senator Miriam
P. Defensor-Santiago Avenue, Diliman, Quezon City, Philippines
Email address: ktachan314@[Link]