An Integer Programming Problem and Rank Decomposition of Block Upper Triangular Matrices
A necessary and sufficient condition is given for a block upper triangular matrix A to be the sum of block upper rectangular matrices satisfying certain rank constraints. The condition is formulated in terms of the ranks of certain submatrices of A. The proof goes by reduction to an integer programming problem. This integer programming problem has a totally unimodular constraint matrix which makes it possible to utilize Farkas' Lemma.
|Keywords||Additive decomposition, Block upper triangular matrices, Farkas' Lemma, Integer programming, Rank constraints|
|Persistent URL||dx.doi.org/10.1016/S0024-3795(99)00219-0, hdl.handle.net/1765/2320|
Bart, H., & Wagelmans, A.P.M.. (2000). An Integer Programming Problem and Rank Decomposition of Block Upper Triangular Matrices. Linear Algebra and Its Applications, 107–219. doi:10.1016/S0024-3795(99)00219-0