Abstract
An MDS matrix is a k x n matrix, such that any k columns in it are linearly independent. A standard construction of such matrices is a Vandermonde matrix, which is equivalent to the generating matrix of a Reed-Solomon code.
There was 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 large enough fields, of size > {n \choose k}.
Dau, Song and Yuen (ISIT 2014) conjectured that the same combinatorial condition suffices also over much smaller fields, of size n+k-1. The reason is that they gave an algebraic construction for such sparse MDS matrices, based on an algebraic conjecture. In this work, we prove this algebraic conjecture, and hence resolve the GM-MDS conjecture.
In the talk, I will describe the background, the combinatorial condition, the algebraic construction of Dau et al and their algebraic conjecture. If time permits, I will sketch the proof of the algebraic conjecture.