MDS codes containing a fixed subcode over finite field extensions

Source abstract

Let $2\le k\le n$ and let $U\le\mathbb{F}_q^n$ be a fixed $(k-1)$-dimensional linear code. We study the $[n,k]$ maximum distance separable (MDS) codes over finite extensions of $\mathbb{F}_q$ that contain the scalar extension of $U$. Our approach constructs an auxiliary linear code from $U$. Its full-weight words characterize the desired MDS completions. We prove that $U$ admits an $[n,k]$ MDS completion over some finite extension of $\mathbb{F}_q$ if and only if $d(U)\ge n-k+1$. When this condition holds, the number of these MDS codes over $\mathbb{F}_{q^m}$ is $$\#\left\{W\le\mathbb{F}_{q^m}^n:U\otimes_{\mathbb{F}_q}\mathbb{F}_{q^m}\subseteq W,\ \dim_{\mathbb{F}_{q^m}} W=k,\ W\text{ is MDS}\right\}=\frac{χ_{δ_GM(G)}(q^m)}{q^m-1},$$ where $G$ is a generator matrix of $U$, $δ_GM(G)$ is its represented derived matroid, and $χ_{δ_GM(G)}$ is its characteristic polynomial. In particular, the formula determines existence over each extension field and the least extension degree for which such an MDS code exists. Examples show that these counts may distinguish different representations of the same column matroid, while monomially inequivalent codes may have identical counts over every finite extension.