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

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s