Abstract
We study the (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)-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.
| Original language | English |
|---|---|
| Pages (from-to) | 171-185 |
| Number of pages | 15 |
| Journal | Linear Algebra and Its Applications |
| Volume | 510 |
| Early online date | 26 Aug 2016 |
| DOIs | |
| Publication status | Published - 1 Dec 2016 |
| Externally published | Yes |
Bibliographical note
The authors also wish to thank Prof. Kameshwar Poolla of University of California at Berkeley, Prof. Matias N. Pincetic of Pontificia Universidad Catolica de Chile, Dr. He Hao of Pacific Northwest National Laboratory, Prof. Karl Johansson of The Royal Institute of Technology (KTH), and Prof. Tryphon Georgiou, Dr. Seizhen Khong, and Dr. Yongxin Chen of University of Minnesota for valuable discussions.Publisher Copyright:
© 2016 Elsevier Inc.
Funding
The work in this paper was partially supported by National Science Foundation , United States, under Grant 1331692 , Research Grants Council of Hong Kong Special Administrative Region, China, under the Theme-Based Research Scheme T23-701/14-N and Hong Kong PhD Fellowship.
Keywords
- Constrained (0,1)-matrix completion
- Fixed zeros
- Structure tensor
- Young diagram
