Why the only binary MDS codes are trivial ones?

Question

Why the only binary MDS codes are trivial ones?

I have been thinking how to draw a contradiction by assuming the MDS code is not trivial.

Thank you very much!

Answer 1

This is Proposition 9.2 on p. 212 of Elements of Algebraic Coding Theory by L. R. Vermani.

Definiton 9.2

We have shown that linear $[n, 1, n]$, $[n, n- 1, 2]$ and $[n, n, 1]$ codes exist over any finite field $F$ and these are MDS codes. These are called trivial MDS codes.

Proposition 9.2

The only binary MDS codes are the trivial codes.

Proof

Let $C$ be a binary $[n, k, d]$ MDS code. If $k = 1$, then $C$ is a trivial MDS code and so we may suppose that $k > 1$. Let $G$ be a generator matrix of $C$ with the first $k$ columns of $G$ forming the identity matrix. If $n > k + 1$, then $C$ has a column, say $j$th, of weight less than $k$ and greater than $1$. Suppose that the $i$th entry of this column is $0$. Then the first $k$ columns of $G$ except the $i$th together with the $j$th column are linearly dependent. This proves that $C$ cannot be an MDS code. Hence

$$k \le n \le k + 1$$

and $C$ is a trivial MDS code.

Answer 2

The only binary codes that are MDS are the trivial (n, n, 1) universe codes, the (n, n − 1, 2) single-parity-check (SPC) codes, and the (n, 1, n) repetition codes. http://web.stanford.edu/class/ee392d/Chap8.pdf

Answer 3

Let $G$ be the generator matrix of the code in standard form $[I_k|A]$ where $A$ is a $k \times (n - k)$ matrix. Since the minimum weight of the code is $d = n - k + 1$, all entries of $A$ are non-zero, and hence $A$ is the all one matrix. If $A$ has only one row, then $k = 1$ and the parameters of the code are $[n, 1, n]$. So, say that $A$ has at least two rows. The sum of first two rows is a vector of weight $2$ which is a codeword. Therefore, $d = n - k + 1 \leq 2$, which shows that $n = k$ or $n = k + 1$. For both cases we have a trivial code, of parameters $[n, n, 1]$ and $[n, n-1, 2]$, respectively.