Open Collections

Proof of the GM-MDS conjecture

Banff International Research Station for Mathematical Innovation and Discovery

A k x n matrix is an MDS matrix if any k columns are linearly independent. Such matrices span MDS (Maximum Distance Separable) codes. A standard construction of such matrices is by Vandermonde matrices, which generate the Reed-Solomon codes. The following question arose in several applications in coding theory: what zero patterns can MDS matrices have it turns out that there is a simple combinatorial characterization that is both necessary and sufficient over large enough fields (concretely, of size {n \choose k}). It was conjectured by Dau et al in 2014 that the same combinatorial characterization is also sufficient over much smaller fields, of size n+k-1. This conjecture is called the GM-MDS conjecture. Dau et al proposed an algebraic conjecture on the structure of polynomials which would imply the GM-MDS conjecture. It speculates that the GM-MDS conjecture can be resolved by an "algebraic" construction. We prove this algebraic conjecture, and as a corollary also the GM-MDS conjecture. https://arxiv.org/abs/1803.02523

Mathematics; Computer science; Fourier analysis; Theoretical computer science

video/mp4

Author affiliation: University of California, San Diego

2019-03-28

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/69322

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/