Geometry Seminar

Date: February 19, 2016

Time: 4:00PM - 5:00PM

Location: BLOC 113

Speaker: Igor Zelenko, TAMU

Title: On Reed-Solomon Type Matrix Completion for Constrained Maximal Distance Separable Codes

Abstract: I will discuss the following matrix completion problem taking its origin in coding theory: we want to construct a linear code of dimension $k$ and length $n$ over a sufficiently large field such that in the generator matrix $G$ of this code in some basis each row has zeros in $k-1$ prescribed positions, all maximal minors of the matrix $G$ are not equal to zero (or, equivalently, the minimal Hamming distance of the code is maximal possible), and the code is of the Reed -Solomon type, i.e. each code-word is obtained by the evaluation of some polynomial at the fixed $n$ distinct elements of the field. Our conjecture is that this completion is possible if and only if the prescribed zeros in the generator matrix do not occupy a submatrix of a size $r\times s$ with $r+s=k+1$ (which is an obvious necessary condition for the completion). I will discuss some reformulations of this conjecture in algebra-geometric and graph-theoretic terms and also a surprising determinantal identity for the matrix involving elementary symmetric functions that I obtained in an attempt to prove this conjecture. This project is in collaboration with Alex Sprintson, Muxi Yan (TAMU, Electrical and Computer Engineering), and Hoang Dao (Urbana-Champaign).