## 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

Publisher Copyright:© 2016 Elsevier Inc.

## Keywords

- Constrained (0,1)-matrix completion
- Fixed zeros
- Structure tensor
- Young diagram