Sparse MDS Matrices: Proof of the GM-MDS Conjecture
summary
States and proves the GM‑MDS conjecture: any K×N zero pattern that satisfies the combinatorial MDS condition can be completed to an MDS matrix over any field of size at least n + k - 1. Proof rewrites rows as degree ≤K−1 polynomials with prescribed roots, shows the Vandermonde‑style determinant polynomial is not identically zero via individual‑degree counting, and closes the argument by a combinatorial induction that allows multiplicities. Produces explicit T/polynomial construction that works.
AI-written summary · about