1. Rank decomposition under zero pattern constraints and [formula omitted]-free directed graphs.
- Author
-
Bart, H., Ehrhardt, T., and Silbermann, B.
- Subjects
- *
DIRECTED graphs , *VECTOR spaces , *INTEGER programming , *GRAPH algorithms , *MATRICES (Mathematics) - Abstract
For a block upper triangular matrix, a necessary and sufficient condition has been given to let it be the sum of block upper rectangular matrices satisfying certain rank constraints; see [12]. The proof involves elements from Integer Programming (totally unimodular systems of equations playing a role in particular) and employs Farkas' Lemma. The linear space of block upper triangular matrices can be viewed as being determined by a special pattern of zeros. The present paper is concerned with the question whether the decomposition result can be extended to situations where other, less restrictive, zero patterns play a role. It is shown that such generalizations do indeed hold for certain directed graphs determining the pattern of zeros. The graphs in question are what will be called L -free. This notion is akin to other graph theoretical concepts available in the literature, among them the one of being N -free in the sense of [16]. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF