Title: An Algebraic-Combinatorial Proof Technique for the GM-MDS Conjecture,
Abstract: This paper considers the problem of designing maximum distance separable
(MDS) codes over small fields with constraints on the support of their
generator matrices. For any given $m\times n$ binary matrix $M$, the GM-MDS
conjecture, due to Dau et al., states that if $M$ satisfies the so-called MDS
condition, then for any field $\mathbb{F}$ of size $q\geq n+m-1$, there exists
an $[n,m]_q$ MDS code whose generator matrix $G$, with entries in $\mathbb{F}$,
fits $M$ (i.e., $M$ is the support matrix of $G$). Despite all the attempts by
the coding theory community, this conjecture remains still open in general. It
was shown, independently by Yan et al. and Dau et al., that the GM-MDS
conjecture holds if the following conjecture, referred to as the TM-MDS
conjecture, holds: if $M$ satisfies the MDS condition, then the determinant of
a transformation matrix $T$, such that $TV$ fits $M$, is not identically zero,
where $V$ is a Vandermonde matrix with distinct parameters. In this work, we
generalize the TM-MDS conjecture, and present an algebraic-combinatorial
approach based on polynomial-degree reduction for proving this conjecture. Our
proof technique's strength is based primarily on reducing inherent
combinatorics in the proof. We demonstrate the strength of our technique by
proving the TM-MDS conjecture for the cases where the number of rows ($m$) of
$M$ is upper bounded by $5$. For this class of special cases of $M$ where the
only additional constraint is on $m$, only cases with $m\leq 4$ were previously
proven theoretically, and the previously used proof techniques are not
applicable to cases with $m > 4$.