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].

3 thoughts on “uniform matroids and MDS codes”

1. I’m surprised SAGE doesn’t have any matroid routines. I tried yours, but after loading it and running

A = matrix(GF(2), [[1,0,0,1,1,0],[0,1,0,1,0,1],[0,0,1,0,1,1]])
M = vector_matroid(A)
print M

I get
Traceback (click to the left of this block for traceback)

TypeError: ‘list’ object is not callable

Or

M.rank()

Traceback (click to the left of this block for traceback)

TypeError: ‘list’ object is not callable

This on sage 4.4.3

• wdjoyner says:

I get

sage: attach “/Users/davidjoyner/sagefiles/matroid_class.sage”
sage: A = matrix(GF(2), [[1,0,0,1,1,0],[0,1,0,1,0,1],[0,0,1,0,1,1]])
sage: M = vector_matroid(A)
sage: print M
Matroid on base set [0, 1, 2, 3, 4, 5] of rank 3
sage: M.rank()
3

This is using 4.5.1 and the matroid code at
http://boxen.math.washington.edu/home/wdj/sagefiles/matroid_class.sage

2. Thank you, I’ll wait a coupl of days to be at home and tryit, meanwhile I’m stuck with 4.4.3 on sagenb.com