Constrained (0,1)-matrix completion with a staircase of fixed zeros

详细信息    查看全文

• 作者：Wei Chen^a ; ^{wchenust@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Yanfang Mo^a ; ^{ymoaa@connect.ust.hk" class="auth_mail" title="E-mail the corresponding author} ; Li Qiu^a ; ^{eeqiu@ust.hk" class="auth_mail" title="E-mail the corresponding author} ; Pravin Varaiya^b ; ^{varaiya@berkeley.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：05C90 ; 15A83
• 刊名：Linear Algebra and its Applications
• 出版年：2016
• 出版时间：1 December 2016
• 年：2016
• 卷：510
• 期：Complete
• 页码：171-185
• 全文大小：421 K

文摘

We study the (0,1)$(0,1)$-matrix completion with prescribed row and column sums wherein the ones are permitted in a set of positions that form a Young diagram. We characterize the solvability of such (0,1)$(0,1)$-matrix completion problems via the nonnegativity of a structure tensor which is defined in terms of the problem parameters: the row sums, column sums, and the positions of fixed zeros. This reduces the exponential number of inequalities in a direct characterization yielded by the max-flow min-cut theorem to a polynomial number of inequalities. The result is applied to two engineering problems arising in smart grid and real-time systems, respectively.