This paper provides a link between matroid theory and locally repairable codes (LRCs) that are either linear or more generally almost affine. Using this link, new results on both LRCs and matroid theory are derived. The parameters @math of LRCs are generalized to matroids, and the matroid analogue of the generalized Singleton bound in [P. , "On the locality of codeword symbols," IEEE Trans. Inf. Theory] for linear LRCs is given for matroids. It is shown that the given bound is not tight for certain classes of parameters, implying a nonexistence result for the corresponding locally repairable almost affine codes, that are coined perfect in this paper. Constructions of classes of matroids with a large span of the parameters @math and the corresponding local repair sets are given. Using these matroid constructions, new LRCs are constructed with prescribed parameters. The existence results on linear LRCs and the nonexistence results on almost affine LRCs given in this paper strengthen the nonexistence and existence results on perfect linear LRCs given in [W. , "Optimal locally repairable codes," IEEE J. Sel. Areas Comm.].
In this paper, locally repairable codes with all-symbol locality are studied. Methods to modify already existing codes are presented. It is also shown that, with high probability, a random matrix with a few extra columns guaranteeing the locality property is a generator matrix for a locally repairable code with a good minimum distance. The proof of the result provides a constructive method to find locally repairable codes. Finally, constructions of three infinite classes of optimal vector-linear locally repairable codes over a small alphabet independent of the code size are given.