uniform matroids and MDS codes

It is known that uniform (resp. paving) matroids correspond to MDS (resp. “almost MDS” codes). This post explains this connection.

An MDS code is an [n,k,d] linear error correcting block code C which meets the Singleton bound, d+k=n+1. A uniform matroid is a matroid for which all circuits are of size \geq r(M)+1, where r(M) is the rank of M. Recall, a circuit in a matroid M=(E,J) is a minimal dependent subset of E — that is, a dependent set whose proper subsets are all independent (i.e., all in J).

Consider a linear code C whose check matrix is an (n-k)\times n matrix H=(\vec{h}_1,\dots , \vec{h}_n). The vector matroid M=M[H] is a matroid for which the smallest sized dependency relation among the columns of H is determined by the check relations c_1\vec{h}_1 + \dots + c_n \vec{h}_n = H\vec{c}=\vec{0}, where \vec{c}=(c_1,\dots,c_n) is a codeword (in C which has minimum dimension d). Such a minimum dependency relation of H corresponds to a circuit of M=M[H].