uniform matroids and MDS codes

Posted on by

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

    Reply

Leave a Reply

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

Gravatar
WordPress.com Logo

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

Facebook photo

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

Cancel

Connecting to %s