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.