Unique low rank completability of partially filled matrices

Bill Jackson, Tibor Jordán, Shin-ichi Tanigawa

Published in:
Journal of Combinatorial Theory, Series B, Volume 121, 2016, Pages 432-462. DOI link


We consider the problems of completing a low-rank positive semidefinite square matrix $M$ or a low-rank rectangular matrix $N$ from a given subset of their entries. We study the local and global uniqueness of such completions by analysing the structure of the graphs determined by the positions of the known entries of $M$ or $N$.
We show that the unique completability testing of rectangular matrices is a special case of the unique completability testing of positive semidefinite matrices. We prove that a generic partially filled matrix is globally uniquely completable if any principal minor of size $n-1$ is locally uniquely completable. These results are based on new geometric observations that extend similar results of the theory of rigid frameworks. We also give an example showing that global completability is not a generic property in $\mathbb{R}^2$.
We provide sufficient conditions for two-dimensional local and global unique completability of an $n\times n$ matrix by proving tight lower (resp. upper) bounds on the minimum number of known entries per row on the total number of unknown entries, resp.) as a function of $n$.

Bibtex entry:

AUTHOR = {Jackson, Bill and Jord{\'a}n, Tibor and Tanigawa, Shin-ichi},
TITLE = {Unique low rank completability of partially filled matrices},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2015},
NUMBER = {TR-2015-08}

Last modification: 26.5.2021. Please email your comments to Tamás Király!