Computer Science/Discrete Mathematics Seminar II

A $k \times n$ matrix $(k<n)$ is an MDS matrix if any k columns in it are linearly independent. There are standard constructions of MDS matrices, such as Vandermonde matrices, which used for error correcting codes (they generate Reed-Solomon codes). There is interest in the coding community in *sparse* MDS matrices, with specific coordinates set to zero based on the underlying code topology. A natural question arises: when do these exist? It turns out that there is a simple combinatorial condition which is both necessary and sufficient over exponentially large fields. The GM-MDS conjecture of Dau, Song and Yuen (ISIT 2014) is that the same combinatorial conditions suffice over much smaller fields (of size linear in $k,n$ instead of exponential). In this work, we resolve this conjecture.