An integer programming problem and rank decomposition of block upper triangular matrices

Authors
Bart, H Wagelmans, APM
Citation
H. Bart et Apm. Wagelmans, An integer programming problem and rank decomposition of block upper triangular matrices, LIN ALG APP, 305(1-3), 2000, pp. 107-129
Citations number
11
Categorie Soggetti
Mathematics
Journal title
LINEAR ALGEBRA AND ITS APPLICATIONS
ISSN journal
00243795 → ACNP
Volume
305
Issue
1-3
Year of publication
2000
Pages
107 - 129
Database
ISI
SICI code
0024-3795(20000115)305:1-3<107:AIPPAR>2.0.ZU;2-I
Abstract
A necessary and sufficient condition is given for a block upper triangular matrix A to be the sum of block upper rectangular matrices satisfying certa in rank constraints. The condition is formulated in terms of the ranks of c ertain submatrices of A. The proof goes by reduction to an integer programm ing problem. This integer programming problem has a totally unimodular cons traint matrix which makes it possible to utilize Farkas' Lemma. (C) 2000 El sevier Science Inc. All rights reserved.