MDS Matrices over Small Fields: A Proof of the GM-MDS Conjecture
MDS Matrices over Small Fields: A Proof of the GM-MDS Conjecture
复制标题
小域上的 MDS 矩阵：GM-MDS 猜想的证明
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Shachar Lovett
中科院分区：
文献类型：
--
作者：
Shachar Lovett
MDS矩阵是其子矩阵都具有满秩的矩阵。编码理论中的一个问题是，MDS矩阵可以有什么零模式。有一个自然的组合必要条件（称为MDS条件），它在任何域上都是必要的，并且通过概率论证在非常大的域上是充分的。Dau et al.（ISIT 2014）证明MDS条件在小域上也是充分的，并给出了一个暗示这一点的代数猜想。在这项工作中，我们证明了这个猜想。
An MDS matrix is a matrix whose minors all have full rank. A question arising in coding theory is, what zero patterns can MDS matrices have. There is a natural combinatorial necessary condition (called the MDS condition) which is necessary over any field, and sufficient over very large fields by a probabilistic argument. Dau et al. (ISIT 2014) conjectured that the MDS condition is sufficient over small fields as well, and gave an algebraic conjecture which would imply this. In this work, we prove this conjecture.