On Binary Matroid Minors and Applications to
Data Storage over Small Fields
Matthias Grezet, Ragnar Freij-Hollanti, Thomas Westerbäck, and Camilla
Hollanti

arXiv:1707.00421v2 [cs.IT] 19 Feb 2018

Department of Mathematics and Systems Analysis, Aalto University, Finland
firstname.lastname@aalto.fi

Abstract. Locally repairable codes for distributed storage systems have
gained a lot of interest recently, and various constructions can be found in
the literature. However, most of the constructions result in either large
field sizes and hence too high computational complexity for practical
implementation, or in low rates translating into waste of the available
storage space.
In this paper we address this issue by developing theory towards code
existence and design over a given field. This is done via exploiting recently established connections between linear locally repairable codes
and matroids, and using matroid-theoretic characterisations of linearity
over small fields. In particular, nonexistence can be shown by finding
certain forbidden uniform minors within the lattice of cyclic flats. It is
shown that the lattice of cyclic flats of binary matroids have additional
structure that significantly restricts the possible locality properties of
F2 -linear storage codes. Moreover, a collection of criteria for detecting
uniform minors from the lattice of cyclic flats of a given matroid is given,
which is interesting in its own right.
Keywords: Binary matroids; Distributed Storage Systems; Lattice of
cyclic flats; Locally repairable codes; Uniform minors

1

Introduction

The need for large-scale data storage is continuously increasing. Within
the past few years, distributed storage systems (DSSs) have revolutionised
our traditional ways of storing, securing, and accessing data. Storage
node failure is a frequent obstacle, making repair efficiency an important
objective. Network coding techniques for DSSs were considered in [6],
characterising a storage space–repair bandwidth tradeoff.
A bottle-neck for repair efficiency, measured by the notion of locality
[13], is the number of contacted nodes needed for repair. To this end,
our motivation in this paper comes from locally repairable codes (LRCs),
which are, informally speaking, storage systems where a small number
of failing nodes can be recovered by boundedly many other (close-by)
nodes. Repair-efficient LRCs are already implemented on HDFS-Xorbas
used by Facebook [14] and Windows Azure storage [11]. Here, the field
size is not yet a huge concern, as the coding is done over a small number

(< 20) of nodes. Nevertheless, if we wish for more flexibility in terms
of the code parameters, the field size quickly becomes a critical issue.
Hence, a question arises as to how and when can we maintain a small
field size, regardless of the number of the storage nodes. Some explicit
constructions of LRCs over small fields can be found in the literature,
e.g., [4,12,8,16,17].
Let us denote by (n, k, d, r, δ), respectively, the code length, dimension,
global minimum distance, locality, and local minimum distance. In terms
of a storage system employing an (n, k, d, r, δ)-LRC, this means that we
encode k information symbols into n code symbols that are then stored
on n storage nodes, and can globally tolerate d − 1 node failures while
still being able to repair by contacting k nodes. Locally, if we lose at
most δ − 1 nodes (δ ≤ d), we can repair those by contacting at most
r < k close-by nodes.
It was shown in [18] that the (r, δ = 2)-locality of a linear LRC is a
matroid invariant. The connection between matroid theory and linear
LRCs was examined in more detail in [20]. In addition, the parameters
(n, k, d, r, δ) for linear LRCs were generalised to matroids, and new results for both matroids and linear LRCs were given therein.
In this paper, we develop theory towards matroids that are representable
over the binary field or some other fixed-sized field. We show that wellknown matroid-theoretic criteria on binary linear codes give conditions
on the lattice of cyclic flats, which govern the locality properties of the
associated storage codes. As a consequence, we get stronger structural
constraints on binary LRCs compared to those previously known for
general LRCs. Moreover, a collection of criteria for detecting uniform
minors from the lattice of cyclic flats of a given matroid is given, which
is interesting in its own right.

2

Preliminaries on LRCs and Matroids

To study LRCs in more detail, we consider punctured codes C|Y , where
Y ⊆ E is a set of coordinates of the code C. For a fixed code C, we denote
by dY the minimum Hamming distance of the punctured code C|Y . As
is common practice, we say that C is an (n, k, d)-code if it has length n,
dimension k and minimum Hamming distance d. A linear (n, k, d)-code
C over a field is a non-degenerate storage code if d ≥ 2 and there is no
zero column in a generator matrix of C.
Definition 1. Here, a linear (n, k, d, r, δ)-LRC over a finite field F is a
non-degenerate linear (n, k, d)-code C over FE such that any coordinate
x ∈ E of C has locality (r, δ), meaning that there is a subset R of E,
called repair set of x, such that x ∈ R, |R| ≤ r + δ − 1 and dR ≥ δ.
The parameters (n, k, d, r, δ) can immediately be defined and studied for
matroids in general, as in [18,20].

2.1

Matroid fundamentals

Matroids were first introduced by Whitney in 1935, to capture and generalise the notion of linear dependence in purely combinatorial terms.

Indeed, the combinatorial setting is general enough to also capture many
other notions of dependence occurring in mathematics, such as cycles or
incidences in a graph, non-transversality of algebraic varieties, or algebraic dependence of field extensions. Of special interest for linear LRCs
is the connection between linear algebra and matroids.
Matroids have many equivalent definitions in the literature. Here, we
choose to present matroids via their rank functions. Much of the contents
in this section can be found in more detail in [9].
Definition 2 (Matroid). A (finite) matroid M = (ρ, E) is a finite set
E together with a rank function ρ : 2E → Z such that for all subsets
X, Y ⊆ E
(R.1) 0 ≤ ρ(X) ≤ |X|,
(R.2) X ⊆ Y
⇒ ρ(X) ≤ ρ(Y ),
(R.3) ρ(X) + ρ(Y ) ≥ ρ(X ∪ Y ) + ρ(X ∩ Y ).
A subset X ⊆ E is called independent if ρ(X) = |X|. If X is independent
and ρ(X) = ρ(E), then X is called a basis. Strongly related to the rank
function is the nullity function η : 2E → Z, defined by η(X) = |X|−ρ(X)
for X ⊆ E.
Any matrix G over a field F generates a matroid MG = (ρ, E), where E
is the set of columns of G, and ρ(X) is the rank of G(X) over F, where
G(X) denotes the submatrix of G formed by the columns indexed by
X. As elementary row operations preserve the row space of G(X) for
all X ⊆ E, it follows that row-equivalent matrices generate the same
matroid.
Thus, there is a straightforward connection between linear codes and
matroids. Let C be a linear code over a field F. Then any two different
generator matrices of C will have the same row space by definition, so
they will generate the same matroid. Therefore, without any inconsistency, we can denote the matroid associated to these generator matrices
by MC = (ρC , E). The rank function ρC can be defined directly from the
code without referring to a generator matrix, via ρC (X) = dim(C|X) for
X ⊆ E.
Example 1. Let C be the linear code generated by the following matrix
G over F2 :
1
1
G=
0
0

2
0
1
0

3
1
1
0

4
0
0
1

5
1
1
1

6
1
1
1

Then, for the matroid MC = (ρC , {1, 2, 3, 4, 5, 6}),
ρC (∅) = 0, ρC ({1, 2, 3}) = ρC ({3, 4, 5}) = 2, ρC ({1, 2, 3, 4, 5, 6}) = 3.
Two matroids M1 = (ρ1 , E1 ) and M2 = (ρ2 , E2 ) are isomorphic if there
exists a bijection ψ : E1 → E2 such that ρ2 (ψ(X)) = ρ1 (X) for all
subsets X ⊆ E1 .

Definition 3. A matroid that is isomorphic to MG for some matrix G
over F is said to be representable over F. We also say that such a matroid
is F-representable. A binary matroid is a matroid that is F2 -representable.
Definition 4. The uniform matroid Unk = (ρ, [n]) is a matroid with a
ground set [n] = {1, 2, . . . , n} and a rank function ρ(X) = min{|X|, k}
for X ⊆ [n].
The following straightforward observation gives a characterisation of
maximum distance separable (MDS) codes and also shows that uniform
matroids constitute a subclass of representable matroids.
Proposition 1. A linear code C is an (n, k, n − k + 1)-MDS code if and
only if MC is the uniform matroid Unk .
There are several elementary operations that are useful for explicit constructions of matroids, as well as for analysing their structure. The operations that we will need for this paper are dualisation, contraction, and
deletion.
Definition 5. Let M = (ρ, E) be a matroid and X, Y ⊆ E, and denote
by X̄ = E − X for any X ⊆ E. Then
(i) The restriction of M to Y is the matroid M |Y = (ρ|Y , Y ), where
ρ|Y (A) = ρ(A) for A ⊆ Y .
(ii) The contraction of M by X is the matroid M/X = (ρ/X , X̄), where
ρ/X (A) = ρ(A ∪ X) − ρ(X) for A ⊆ X̄.
(iii) A minor of M is the matroid M |Y /X = (ρ|Y /X , Y − X) obtained
from M by restriction to Y and contraction by X. Observe that this
does not depend on the order in which the restriction and contraction
are performed.
(iv) The dual of M is the matroid M ∗ = (ρ∗ , E), where ρ∗ (A) = |A| +
ρ(Ā) − ρ(E) for A ⊆ E.
The restriction operation to Y is also referred to as deletion of the set
E−Y.
Let M = MC be a representable matroid. Then, restriction, contraction, and dualisation of M correspond to puncturing, shortening, and
orthogonal complement of the code C, respectively.
Example 2. Let C be the code generated by the matrix G in Example 1.
Then for the matroid MC = (ρ = ρC , [6]), X = {1}, and Y = {2, 3, 4, 5},
ρ/X ({2, 3, 4}) = 2, ρ|Y ({2, 3, 4}) = 3, and ρ∗ ({2, 3, 4}) = 2.
The minors of uniform matroids are very easily described:
Lemma 1. Let Unk = (ρ, [n]) be a uniform matroid, and let X ⊆ Y ⊆ E.
′
Then the minor Unk |Y /X is isomorphic to Unk′ , where k′ = max{0, k −
|X|} and n′ = |Y | − |X|. In particular, M is a minor of Unk if and only
′
if M ∼
= Unk′ , for some 0 ≤ k′ ≤ k and 0 ≤ n′ − k′ ≤ n − k.
In general there is no simple criterion to determine if a matroid is representable. However, there is a simple criterion for when a matroid is
binary.

Theorem 1 ([19]). Let M = (ρ, E) be a matroid. The following two
conditions are equivalent.
1. M is linearly representable over F2 .
2. There are no sets X ⊆ Y ⊆ E such that M |Y /X is isomorphic to
the uniform matroid U42 .
In essence, this means that the only obstruction that needs to be overcome in order to be representable over the binary alphabet, is that no
more than three nonzero points can fit in the same plane. Clearly, if M is
representable over F, then so are all its minors. The following result, Theorem 2, is a far-going extension of Theorem 1, that was first conjectured
by Gian-Carlo Rota in 1970. A proof of this conjecture was announced
by Geelen, Gerards, and Whittle in 2014, but the details of the proof
still remain to written up [10].
Theorem 2 ([10]). For any finite field F, there is a finite set L(F)
of matroids such that any matroid M is representable if and only if it
contains no element from L(F) as a minor.
Since the 1970’s, it has been known that a matroid is representable over
F3 if and only if it avoids the uniform matroids U52 , U53 , the Fano plane
P2 (F2 ), and its dual P2 (F2 )∗ as minors. The list L(F4 ) has seven elements,
and was given explicitly in 2000. For larger fields, the explicit list is not
known, and there is little hope to even find useful bounds on its size.
By the Critical Theorem [5], the matroid MC determines the supports
of a linear code C. Consequently, since binary codes are determined
uniquely by the support of the codewords, binary matroids are in oneto-one correspondence with binary codes. This is in sharp contrast to
linear codes over larger fields, where many interesting properties are not
determined by the associated matroid. An important example of such a
property is the covering radius [3].

2.2

Fundamentals on cyclic flats

The main tool from matroid theory in this paper are the cyclic flats. We
will define them using the closure and cyclic operator.
Let M = (ρ, E) be a matroid. The closure operator cl : 2E → 2E and
cyclic operator cyc : 2E → 2E are defined by
(i) cl(X) = X ∪ {e ∈ E − X : ρ(X ∪ e) = ρ(X)},
(ii) cyc(X) = {e ∈ X : ρ(X − e) = ρ(X)}.
A subset X ⊆ E is a flat if cl(X) = X and a cyclic set if cyc(X) = X.
Therefore, X is a cyclic flat if
ρ(X ∪ y) > ρ(X)

and

ρ(X − x) = ρ(X)

for all y ∈ E − X and x ∈ X. The collection of flats, cyclic sets, and
cyclic flats of M are denoted by F(M ), U(M ), and Z(M ), respectively.

It is easy to verify, as in [2], that the closure operator induces flatness
and preserves cyclicity, and that the cyclic operator induces cyclicity and
preserves flatness. Thus we can write
(
(
2E → U(M )
2E → F(M )
and cyc :
cl :
F(M ) → Z(M ).
U(M ) → Z(M ),
In particular, for any set X ⊆ E, we have cyc(cl(X)) ∈ Z(M ) and
cl(cyc(X)) ∈ Z(M ). Some more fundamental properties of flats, cyclic
sets, and cyclic flats are given in [2].
The cyclic flats of a linear code C of FE can be described as sets X ⊆ E
such that
C|(X ∪ y) ) C|X and C|(X − x) = C|X
for all y ∈ E − X and x ∈ X. Thus, we have the following immediate
proposition.
Proposition 2. Let M = (ρ, E) be a matroid. The following are equivalent:
(i) M is the uniform matroid Unk
(ii) Z = Z(M ) is the two element lattice with bottom element 0Z = ∅,
top element 1Z = E and ρ(1Z ) = k
Non-degeneracy of a truncated code can be observed immediately from
the lattice of cyclic flats of the associated matroid, as follows.
Proposition 3. Let C be a linear code over FE and X ⊆ E. Then C|X
is non-degenerate if and only if 1Z(MC |X) = X and 0Z(MC |X) = ∅.
The minimum distances and the ranks of punctured codes can be computed from the lattice of cyclic flats via the following theorem. In [20],
this was used to construct matroids and linear LRCs with prescribed
parameters (n, k, d, r, δ).
Theorem 3 ([20]). Let C be a linear code over FE and X ⊆ E. Then,
if C|X is non-degenerate, it has dimension kX = ρ(1Z(MC |X) ) and minimum distance dX = η(X)+1−max{η(Y ) : Y ∈ Z(MC |X) and Y 6= X}.
Example 3. Let MC = (ρC , E = [6]) be the matroid associated to the
linear code C generated by the matrix G given in Example 1. The lattice
of cyclic flats (Z, ⊆) of MC is given in Fig. 1, where the cyclic flat is
given inside the node and its rank is labelled outside the node on the
right.
From the lattice of cyclic flats given above, we can conclude that C is a
(6, 3, 2)-code.

3

Sufficient Conditions for Uniformity

Our main goal is to study criteria for when M |Y /X is uniform, for X ⊆
Y ⊆ E(M ). As a preparation, observe that for a uniform matroid M ∼
=
Unk , the only cyclic flats are ∅ and E(M ), with |E(M )| = n and ρ(E) = k.
Our first interest is in the case when X and Y are themselves cyclic
flats. Then we have a straightforward characterisation of cyclic flats in
M |Y /X, via the following two lemmas:

Lemma 2. Let M be a matroid, and let X ⊆ Y ⊆ E(M ) be two sets
with Y ∈ F(M ). Then F(M |Y /X) = {F ⊆ Y − X, F ∪ X ∈ F(M )}.
Proof. A set S is flat in M |Y /X precisely if ρ(S ∪ X ∪ i) > ρ(S ∪ X) for
all i ∈ (Y − X) − S. Since Y is flat, the inequality ρ(S ∪ X ∪ i) > ρ(S ∪ X)
will hold for all i ∈ Ȳ regardless of S. Thus, S is flat in M |Y /X if and
only if S ∪ X is flat in M .
Lemma 3. Let M be a matroid, and let X ⊆ Y ⊆ E(M ) be two sets
with X ∈ U(M ). Then U(M |Y /X) = {U ⊆ Y − X, U ∪ X ∈ U(M )}.
This is the dual statement, and thus an immediate consequence, of
Lemma 2. We write out the proof explicitly only for illustration.
Proof. A set S is cyclic in M |Y /X precisely if ρ((S ∪ X) − i) = ρ(S ∪ X)
for all i ∈ S. For i ∈ X, this will hold regardless of S, since X is cyclic.
Thus, S is cyclic in M |Y /X if and only if S ∪ X is cyclic in M .
The previous lemmas give the following immediate corollary:
Corollary 1. Let M = (E, ρ) be a matroid, and let X ⊆ Y ⊆ E(M ) be
two sets with X ∈ U(M ) and Y ∈ F(M ). Then Z(M |Y /X) = {Z ⊆ Y −
X, Z ∪ X ∈ Z(M )}, with the rank function ρ|Y /X (Z) = ρ(Z ∪ X) − ρ(X).
As a consequence, we get a sufficient condition for uniformity of minors,
that only depends on the Hasse diagram of Z(M ). Recall that v is said
to cover u in a poset P if u < v and there is no w with u < w < v. If
this is the case, then we write u ⋖P v. This is equivalent to (u, v) being
an upwards directed edge in the Hasse diagram of P .
Theorem 4. Let X and Y be two cyclic flats in M with X ⋖Z(M ) Y .
Let n = |Y | − |X| and k = ρ(Y ) − ρ(X). Then M |Y /X ∼
= Unk .
Proof. By Corrolary 1, we have Z(M |Y /X) = {∅, Y −X} as there are no
cyclic flats with X ⊂ Z ⊂ Y . Again by Corrolary 1, we have ρ(Y − X) =
ρ(Y )−ρ(X) = k. Thus, by Proposition 2, M |Y /X is the uniform matroid
Unk .
Corollary 2. Let M be a matroid that contains no Unk minors. Then,
for every edge X ⋖Z(M ) Y in the Hasse diagram of Z(M ), we have ρ(Y )−
ρ(X) < k or η(Y ) − η(X) < n − k.

E

3

123 2

3456 2

56 1

∅

0

Fig. 1. Lattice of cyclic flats of MC .

Proof. Assume for a contradiction that X ⋖Z(M ) Y has ρ(Y ) − ρ(X) =
k′ ≥ k or η(Y ) − η(X) = n′ − k′ ≥ n − k. Then by Theorem 4, M |Y /X ∼
=
′
Unk′ , and so contains Unk as a minor by Lemma 1.
Now, we are going to need formulas for how to compute the lattice operators in Z(M |Y /X) in terms of the corresponding operators in Z(M ).
These can be derived from corresponding formulas for the closure and
cyclic operator. To derive these, we will need to generalise Corollary 1
to the setting where the restriction and contraction are not necessarily
performed at cyclic flats.
Theorem 5. For X ⊆ Y ⊆ E, we have
1. Z(M |Y ) = {cyc(Z ∩ Y ) : Z ∈ Z(M )}
2. Z(M/X) = {cl(X
n ∪ Z) − X : Z ∈ Z(M
 )}
o

3. Z(M |Y /X) = cl X ∪ cyc Z ∩ Y
∩ Y − X : Z ∈ Z(M )
n 

o

= cyc cl X ∪ Z ∩ Y − X : Z ∈ Z(M )

Proof. 1. First, observe that the cyclic operator in M |Y is the same as
that in M , and that the flats in M |Y are {F ∩ Y : F ∈ F(M )}. Thus
we have
Z(M |Y ) = {cyc(F ∩ Y ) : F ∈ F(M )} ⊇ {cyc(Z ∩ Y ) : Z ∈ Z(M )}.
On the other hand, let A ∈ Z(M |Y ), so cyc(A) = A and cl(A) ∩ Y =
A. But the closure operator preserves cyclicity, so cl(A) ∈ Z(M ). We
then observe that
A = cyc(cl(A) ∩ Y ) ∈ {cyc(Z ∩ Y ) : Z ∈ Z(M )}.
This proves the reverse inclusion
Z(M |Y ) = {cyc(F ∩ Y ) : F ∈ F(M )} ⊆ {cyc(Z ∩ Y ) : Z ∈ Z(M )}.
2. This is the dual statement of 1., and so follows immediately by applying 1. to the matroid M ∗ |X̄/Ȳ .
3. We first apply 2. and then 1. to the restricted matroid M |Y , and get
Z(M |Y /X) = {cl|Y (X ∪ cyc(Z ∩ Y )) − X : Z ∈ Z(M )}.
But if T ⊆ Y , then cl|Y (T ) = cl(T ) ∩ Y . Then,
Z(M |Y /X) = {cl(X ∪ cyc(Z ∩ Y )) ∩ (Y − X) : Z ∈ Z(M )}
For the second equality of 3. we need to study the operator cyc/X .
Suppose T ⊆ E − X. Using duality and the formula for cl|X̄ , we find
that
cyc/X (T ) = cyc(X ∪ T ) − X.
Now we are ready to prove the last equality. Applying first 1. and
then 2. to the contracted matroid M/X, we get
Z(M |Y /X) = {cyc/X ((cl(X ∪ Z) − X) ∩ Y ) : Z ∈ Z(M )}
Applying the formula for cyc/X , we obtain
Z(M |Y /X) = {cyc((cl(X ∪ Z) ∩ Y − X) ∪ X) − X : Z ∈ Z(M )}
= {cyc(cl(X ∪ Z) ∩ Y ) − X : Z ∈ Z(M )},
where the last equality follows as X ⊆ cl(X ∪ Z). This concludes the
proof.

4

Criteria for Uniformity via Cyclic Flats

We can use Theorem 5 to find conditions for a minor to be isomorphic to
a uniform matroid. The idea is to detect when Z(M |Y /X) as calculated
in Theorem 5 is precisely {∅, Y − X}. Using this, we will be able to find
some conditions on the sets X and Y , as well as on the matroid itself.

4.1

Minors Given by Restriction or Contraction Only

We will begin by considering a simpler case when the minor is the result
of a restriction only, i.e., when the minor is given by M |Y . So, let M =
(E, ρ) be a matroid and Y an arbitrary subset of E. We can use Corollary
1 to restrict the amount of information we need to consider. Indeed, by
properties of minors, we have
M |Y = M |cl(Y ) \ (cl(Y ) − Y ).

(1)

Then, Theorem 5 states that the cyclic flats of M |Y depend only on
the cyclic flats of M |cl(Y ). Furthermore, according to Corollary 1 the
cyclic flats of M |cl(Y ) are exactly the cyclic flats of M contained in
cl(Y ). Hence, we can restrict the study to the case when M = (E, ρ) is
a matroid and Y is a subset of full rank. Define k := ρ(Y ) and n := |Y |.
With this setup, we obtain the following theorem.
Theorem 6. Let M = (E, ρ) be a matroid and Y a subset of full rank.
M |Y is isomorphic to the uniform matroid Unk if and only if either Y is
a basis of M or the following two conditions are satisfied:
1. Y is a cyclic set of M .
2. For all Z ∈ Z(M ) with ρ(Z) < k, we have that Z ∩ Y is independent
in M .
Before stating the proof, we will need one useful lemma about the properties of the closure and cyclic operator.
Lemma 4. Let M = (E, ρ) be a matroid and Y ⊆ E. Then
1. cl(cyc(Y )) ∩ Y = cyc(Y ).
2. cyc(cl(Y )) ∪ Y = cl(Y ).
The proof of Lemma 4 is straightfrorward from the definition of the
operators together with the submodularity of the rank function. Details
of the proof can be found in [2]. We now present the proof of Theorem
6.
Proof. We know that M |Y ∼
= Unk if and only if Z(M |Y ) = {∅, Y }. On
the other hand, we know by Theorem 5, that Z(M |Y ) = {cyc(Z ∩ Y ) :
Z ∈ Z(M )}. Then we have
k
M |Y ∼
= Un if and only if cyc(Z ∩ Y ) ∈ {∅, Y } for all Z ∈ Z(M ).

Now consider the cyclic flat ZY := cl(cyc(Y )). Using Lemma 4, we have
cyc(ZY ∩ Y ) = cyc(Y ). Two cases can occur. If cyc(Y ) = ∅ then Y
was a basis of M and we end up with a minor isomorphic to Ukk . If

not, then cyc(Y ) must be equal to Y . So, we have that Y ∈ Z(M |Y ) if
and only if Y is a cyclic set and we obtain the first condition. Since Y
already has full rank, there is only one cyclic flat that contains Y , namely
cl(cyc(Y )) = E. Therefore, for every other cyclic flat Z, i.e., for all Z
with ρ(Z) < k, we have cyc(Z ∩ Y ) ⊆ Z ∩ Y 6= Y . But, by Theorem 5,
cyc(Z ∩Y ) is a cyclic flat of M |Y . Thus, for all Z ∈ Z(M ) with ρ(Z) < k,
we have cyc(Z ∩ Y ) = ∅, or equivalently, Z ∩ Y is independent. Notice
that, combined with the first condition, this implies immediately that
Z(M |Y ) = {∅, Y }. This concludes the proof.
Corollary 3. Under the above assumptions, if M |Y is isomorphic to
Unk then the ground set E must be a cyclic flat, i.e., E ∈ Z(M ).
Example 4. We will look at the matroid MC arising from the binary matrix in Example 1. Since it is a binary matroid, we cannot find a minor
isomorphic to U42 . Using the lattice of cyclic flats of Fig. 1, we can find a
minor isomorphic to U32 if we look at, e.g., MC |{1, 2, 3}. We can also find
a minor isomorphic to U43 . To this end, we look at MC |{1, 2, 4, 5}. The
set {1, 2, 4, 5} is indeed a cyclic set because cyc({1, 2, 4, 5}) = {1, 2, 4, 5}.
Furthermore, there is no cyclic flat properly contained in {1, 2, 4, 5}, and
every intersection of a cyclic flat different from E with the set {1, 2, 4, 5}
gives us an independent set. Thus, the conditions from the previous theorem are met and we get a minor isomorphic to U43 .
Now we can do the same for M/X and use duality to get back to the
restriction case. By minor properties, we have
M/X = M/cyc(X)/(X − cyc(X)).

(2)

Then, Corollary 1 states that the cyclic flats of M/cyc(X) are the cyclic
flats of M that contain cyc(X). Thus, we will consider a matroid M =
(E, ρ) and X an independent subset of E. Define k := ρ(E) − ρ(X) and
n := |E − X|. Then, we have the following dual statement of Theorem 6.
Theorem 7. Let M = (E, ρ) be a matroid and X an independent subset
of E. M/X is isomorphic to the uniform matroid Unk if and only if either
X is a basis of M or the following two conditions are satisfied:
1. X is a flat of M .
2. For all Z ∈ Z(M ) with ρ(Z) > 0, we have cl(X ∪ Z) = E.
Corollary 4. Under the above assumptions, if M/X is isomorphic to
Unk then the empty set must be a cyclic flat, i.e., ∅ ∈ Z(M ).

4.2

Minors Given by Both Restriction and Contraction

This part combines the two previous situations into a more general statement. We will see that, when we allow both a restriction and a contraction to occur, we lose some conditions on the matroid that are then
replaced by conditions on the sets used in the minor.
Let M = (E, ρ) be a matroid and X ⊂ Y ⊆ E two sets. Combining minor
properties (1) and (2) and Corollary 1, it is sufficient to only consider

the cyclic flats between cyc(X) and cl(Y ). In addition, we want to avoid
some known cases, namely when Y is a basis (we will obtain Ukk ) and
when X has full rank (we will obtain U00 ). Define k := ρ(E) − ρ(X) and
n := |Y − X|. We get the following theorem.
Theorem 8. Let M = (E, ρ) be a matroid and X ⊂ Y ⊆ E two sets
such that Y is a dependent full-rank set and X is an independent set with
ρ(X) < ρ(E). The minor M |Y /X is isomorphic to a uniform matroid
Unk if and only if
1. cl(X) ∩ Y = X,
2. Y − X ⊆ cyc(Y ),
3. for all Z ∈ Z(M ) either Z ∩ Y is independent or
cl(X ∪ cyc(Z ∩ Y )) = E.
Proof. Using Theorem 5, we have that M |Y /X ∼
= Unk if and only if
cl(X ∪ cyc(Z ∩ Y )) ∩ (Y − X) ∈ {∅, Y − X} for all Z ∈ Z(M ).
In particular, it holds for Z = 0Z . Let Z0′ := cl(X ∪ cyc(0Z ∩ Y )). Using
the properties of the closure, we have
cl(X) ⊆ Z0′ ⊆ cl(X ∪ 0Z ) = cl(X).
Thus, we have a chain of equalities and, in particular, ρ(Z0′ ) < ρ(E).
This means that Z0′ = ∅ in order to have ∅ ∈ Z(M |Y /X). But, since
Z0′ = cl(X) then Z0′ = ∅ is equivalent to cl(X) ∩ Y = X and Condition 1
is proved.
Now, consider the cyclic flat ZY := cl(cyc(Y )). First, using again Lemma
4, we have cyc(ZY ∩ Y ) = cyc(Y ). Since Y is a dependent subset,
cyc(Y ) 6= ∅ and thus X ( X ∪ cyc(Y ). Then, the closure cannot be
contained in X and we must have
cl(X ∪ cyc(Y )) ∩ (Y − X) = Y − X.
Define ZY′ := cl(X ∪ cyc(Y )). The above equality means that Y − X ⊆
ZY′ . On the other hand, we have that X ⊆ ZY′ . Then, Y ⊆ ZY′ and
ZY′ = E. In particular, we must have Y − X ⊆ cyc(Y ). Indeed, assume
by contradiction that there exists a ∈ Y − X and a ∈
/ cyc(Y ). Then, by
definition of the cyclic operator, ρ(Y − a) < ρ(Y ). But since a ∈
/ cyc(Y )
and a ∈
/ X then X ∪ cyc(Y ) ⊆ Y − a. This implies that ρ(X ∪ cyc(Y )) ≤
ρ(Y −a) < ρ(Y ) which is a contradiction. The condition Y −X ⊆ cyc(Y )
is also sufficient to guarantee that Y − X ∈ Z(M |Y /X). This proves
Condition 2.
Finally, for every other cyclic flat of M , cl(X ∪cyc(Z ∩Y ))∩(Y −X) = ∅ if
and only if cyc(Z ∩Y ) ⊆ X. But since X is independent, this is equivalent
to Z ∩ Y being independent. On the other hand, cl(X ∪ cyc(Z ∩ Y )) ∩
(Y − X) = Y − X if and only if cl(X ∪ cyc(Z ∩ Y )) = E. This concludes
the proof.

5

Stuctural Properties of Binary LRCs

From a practical viewpoint, storage systems over alphabets of bounded
size are of special interest. The field size is important both because it
governs the complexity of the computations involved in repair and retrieval, and because it restricts the size of the data items stored. We are
therefore interested in understanding the matroidal structure of LRCs
that are linearly representable over the finite field Fq , where q is small.
Assuming the MDS conjecture [15], a matroid M that is linearly reprek
sentable over Fq must avoid Uq+2
as a minor, for k = 2, 4 ≤ k ≤ q − 2,
q−1
3
and k = q. If q is odd, M must also avoid Uq+2
and Uq+2
minors. The
MDS conjecture is widely believed to be true, and is proven when q is
prime [1].
By Corollary 2, matroids avoiding Unk minors have a rather special structure in their lattice of cyclic flats. In particular, it tells us that whenever X ⋖Z Y , we cannot simultaneously have ρ(Y ) − ρ(X) > k and
η(Y ) − η(X) > n − k. This observation can be exploited to bound locality parameters of an LRC in terms of the field size.
Of special interest are binary storage codes that are linear over F2 . It is
known that a matroid is representable over F2 if and only if it avoids U42 as
a minor. In this case, Corollary 2 tells us that we cannot simultaneously
have ρ(Y ) − ρ(X) > 1 and η(Y ) − η(X) > 1. On the other hand, we
know by Theorem 3.2 in [2] or by direct calculation, that we always have
ρ(Y ) − ρ(X) ≥ 1 and η(Y ) − η(X) ≥ 1. Thus, if M is representable
over F2 , then every edge X ⋖Z Y in the Hasse diagram of Z(M ) satisfies
exactly one of the following:
(i) ρ(Y ) − ρ(X) = l > 1. We call such an edge a rank edge, and label it
l
minor in M .
ρ = l. Such an edge corresponds to a Ul+1
(ii) η(Y ) − η(X) = l > 1. We call such an edge a nullity edge, and label
1
it η = l. Such an edge corresponds to a Ul+1
minor in M .
(iii) ρ(Y ) − ρ(X) = 1 and η(Y ) − η(X) = 1. We call such an edge an
elementary edge. Such an edge corresponds to a U21 minor in M .
As an example, the matroid from Examples 1 and 2 gets an edge labelling
as illustrated in Figure 2:

E
η=2
123

3456

56

ρ=2

∅

Fig. 2. Lattice of cyclic flats of MC .

It is clear that this representation is enough to reconstruct the so-called
configuration of the matroid, i.e., the isomorphism type of the lattice
of cyclic flats, together with the cardinality and rank of the cyclic flats.
However, this data does not uniquely determine the matroid, as is shown
in [7].
As is proven in [20], the configuration of a representable matroid determines the minimum distance of the corresponding code, via the formula
dC = η(E) + 1 −

max

Z∈Z(M )−{E}

η(Z).

In particular, for a binary code C with dC > 2, all edges Z ⋖ E on the
“top level” of Z(MC ) must be nullity edges. Moreover, the minimum
distance is then one higher than the smallest label of a top level edge in
Z(MC ).
Recall that an (n, k, d)-storage code is said to have locality (r, δ) if every
storage node i ∈ [n] is contained in a set X with |X| ≤ r + δ − 1
and dX ≥ δ. This is equivalent to that every node i ∈ [n] is contained
in a set X with sX := |X| − dX + 1 ≤ r and dX ≥ δ. Now, notice
that sX = ρ(X) + maxZ<Z X η(Z), and so sX does not increase when
replacing X by its closure, which is a cyclic flat as X is cyclic. This gives
a lattice-theoretic description of Z(MC ), when C is a binary code with
(r, δ)-locality.
Surprisingly, the descriptions are qualitatively different depending on
whether δ = 2 or δ > 2, i.e., whether one or more erasures can be
corrected locally. This is in sharp contrast to the case when the field
size is ignored, as in [20]. We conclude this paper by formulating the
locality criteria for binary storage codes in terms of lattices of cyclic
flats. Exploiting this description to obtain quantitative bounds on the
parameters (n, k, d, r, δ) is left for future research. Such bounds are also
likely to suggest explicit constructions of extremal LCFs satisfying the
conditions of Theorem 9.
Theorem 9. Let d > 2 and let C be a linear (n, k, d, r, δ)-LRC over F2 .
Then Z = Z(MC ) satisfies the following:
1. ∅ and [n] are cyclic flats.
2. Every covering relation Z ⋖Z [n] is a nullity edge labeled with a number ≥ d − 1.
3. If δ = 2, then for every i ∈ [n], there is X ∈ Z with i ∈ X such that
ρ(X) ≤ r.
4. If δ > 2, then for every i ∈ [n], there is X ∈ Z with i ∈ X such that
(i) Every covering relation Y ⋖Z X is a nullity edge labeled with a
number ≥ δ − 1.
(ii) Every cyclic flat Y ⋖Z X has rank ≤ r − 2

6

Conclusions and Future Work

We have studied the lattice of cyclic flats of matroids, with a special
emphasis on identifying uniform minors, and with applications to locally repairable codes over small fields. Necessary and sufficient criteria for a specified minor M |Y /X to be uniform are derived in general,

and in the special case of U42 -minors, necessary global criteria for U42 avoidance are given. Finally, it is shown how these criteria dictate the
structure of binary storage codes with prescribed locality parameters.
Future work include translating these structural results to quantitative
parameter bounds. Similar arguments are likely to be applicable when
studying storage codes over other small fields, although new methods
would then be needed to identify other minors than uniform ones.
Acknowledgment. The authors gratefully acknowledge the financial
support from the Academy of Finland (grants #276031 and #303819).

References
1. Ball, S.: On sets of vectors of a finite vector space in which every
subset of basis size is a basis. Journal of the European Mathematical
Society 14, 733–748 (2012)
2. Bonin, J.E., de Mier, A.: The lattice of cyclic flats of a matroid.
Annals of combinatorics 12, 155–170 (2008)
3. Britz, T., Rutherford, C.G.: Covering radii are not matroid invariants. Discrete Mathematics 296, 117–120 (2005)
4. Cadambe, V., Mazumdar, A.: An upper bound on the size of locally
recoverable codes. In: International Symposium on Network Coding.
pp. 1–5 (2013)
5. Crapo, H., Rota, G.C.: On the Foundations of Combinatorial Theory: Combinatorial Geometries,. MIT Press, Cambridge, MA, London,, preliminary edition edn. (1970)
6. Dimakis, A., Godfrey, P.B., Wu, Y., Wainwright, M.J., Ramchandran, K.: Network coding for distributed storage systems. IEEE
Transactions on Information Theory 56(9), 4539–4551 (2010)
7. Eberhardt, J.: Computing the tutte polynomial of a matroid from its
lattice of cyclic flats. Electronic Journal of Combinatorics 21, 12pp.
(2014)
8. Ernvall, T., Westerbäck, T., Freij-Hollanti, R., Hollanti, C.: Constructions and properties of linear locally repairable codes. IEEE
Transactions on Information Theory 62, 5296–5315 (2016)
9. Freij-Hollanti, R., Hollanti, C., Westerbäck, T.: Matroid theory and
storage codes: bounds and constructions (2017), arXiv: 1704.0400
10. Geelen, J., Gerards, B., Whittle, G.: Solving Rota’s conjecture. Notices of the American Mathematical Society 61(736–743) (2014)
11. Huang, C., Simitci, H., Xu, Y., Ogus, A., Calder, B., Gopalan, P.,
Li, J., Yekhanin, S.: Erasure coding in Windows Azure storage. In:
Proc. USENIX Annual Technical Conference. pp. 15–26 (2012)
12. Huang, P., Yaakobi, E., Uchikawa, H., Siegel, P.H.: Binary linear
locally repairable codes. IEEE Transactions on Information Theory
62, 5296–5315 (2016)
13. Papailiopoulos, D., Dimakis, A.: Locally repairable codes. In: International Symposium on Information Theory. pp. 2771–2775. IEEE
(2012)

14. Sathiamoorthy, M., Asteris, M., Papailiopoulos, D., Dimakis, A.G.,
Vadali, R., Chen, S., Borthakur, D.: Xoring elephants: Novel erasure
codes for big data. In: Proc. VLDB. vol. 6, pp. 325–336 (2013)
15. Segre, B.: Curve razionali normali e k-archi negli spazi finiti. Annali
di Matematica Pura ed Applicata 39, 357–359 (1955)
16. Silberstein, N., Zeh, A.: Optimal binary locally repairable codes via
anticodes (2015), arXiv: 1501.07114v1
17. Tamo, I., Barg, A., Frolov, A.: Bounds on the parameters of locally
recoverable codes. IEEE Transactions on Information Theory 62(6),
3070–3083 (2016)
18. Tamo, I., Papailiopoulos, D., Dimakis, A.: Optimal locally repairable
codes and connections to matroid theory. IEEE Transactions on Information Theory 62, 6661–6671 (2016)
19. Tutte, W.: A homotopy theorem for matroids, I, II. Transactions of
the Amarican Mathematical Society 88, 148–178 (1958)
20. Westerbäck, T., Freij-Hollanti, R., Ernvall, T., Hollanti, C.: On the
combinatorics of locally repairable codes via matroid theory. IEEE
Transactions on Information Theory 62, 5296–5315 (2016)

