We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Proof of the GM-MDS conjecture

Formal Metadata

Title
Proof of the GM-MDS conjecture
Title of Series
Number of Parts
17
Author
License
CC Attribution - NonCommercial - NoDerivatives 4.0 International:
You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
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.