Rank decomposition under zero pattern constraints and \(\mathsf{L}\)-free directed graphs. (English) Zbl 1464.15002
Summary: 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 [H. Bart and A. P. M. Wagelmans, Linear Algebra Appl. 305, No. 1–3, 107–129 (2000; Zbl 0951.15013)]. 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 \(\mathsf{L}\)-free. This notion is akin to other graph theoretical concepts available in the literature, among them the one of being \(\mathsf{N}\)-free in the sense of [M. Habib and R. Jegou, Discrete Appl. Math. 12, 279–291 (1985; Zbl 0635.06002)].
MSC:
| 15A03 | Vector spaces, linear dependence, rank, lineability |
| 15A21 | Canonical forms, reductions, classification |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C20 | Directed graphs (digraphs), tournaments |
| 06A06 | Partial orders, general |
| 90C10 | Integer programming |
Keywords:
block (upper triangular) matrices; additive decomposition; rank constraints; integer programming; zero pattern constraints; directed (bipartite) graph; \(\mathsf{L}\)-free graphReferences:
| [1] | Bart, H.; Ehrhardt, T.; Silbermann, B., Logarithmic residues in Banach algebras, Integral Equ. Oper. Theory, 19, 135-152 (1994) · Zbl 0811.46043 |
| [2] | Bart, H.; Ehrhardt, T.; Silbermann, B., Logarithmic residues, generalized idempotents and sums of idempotents in Banach algebras, Integral Equ. Oper. Theory, 29, 155-186 (1997) · Zbl 0894.46038 |
| [3] | Bart, H.; Ehrhardt, T.; Silbermann, B., Sums of Idempotents and Logarithmic Residues in Matrix Algebras, Operator Theory: Advances and Applications, OT, vol. 122, 139-168 (2001), Birkhäuser Verlag: Birkhäuser Verlag Basel · Zbl 1047.46037 |
| [4] | Bart, H.; Ehrhardt, T.; Silbermann, B., Logarithmic Residues of Fredholm Operator Valued Functions and Sums of Finite Rank Projections, Operator Theory: Advances and Applications, OT, vol. 130, 83-106 (2001), Birkhäuser Verlag: Birkhäuser Verlag Basel · Zbl 1051.30046 |
| [5] | Bart, H.; Ehrhardt, T.; Silbermann, B., Logarithmic residues, Rouché’s theorem, spectral regularity, and zero sums of idempotents: the \(C^\ast \)-algebra case, Indag. Math., 23, 816-847 (2012) · Zbl 1279.47028 |
| [6] | Bart, H.; Ehrhardt, T.; Silbermann, B., Sums of idempotents and logarithmic residues in zero pattern matrix algebras, Linear Algebra Appl., 498, 262-316 (2016) · Zbl 1334.15039 |
| [7] | Bart, H.; Ehrhardt, T.; Silbermann, B., Rank decomposition in zero pattern matrix algebras, Czechoslov. Math. J., 66, 987-1005 (2016) · Zbl 1413.15010 |
| [8] | Bart, H.; Ehrhardt, T.; Silbermann, B., Echelon Type Canonical Forms in Upper Triangular Matrix Algebras, Operator Theory: Advances and Applications, vol. 259, 79-124 (2017), Birkhäuser Verlag, Springer Basel AG · Zbl 1365.15014 |
| [9] | Bart, H.; Ehrhardt, T.; Silbermann, B., \( \mathsf{L} \)-Free Directed Bipartite Graphs and Echelon-Type Canonical Forms, Operator Theory: Advances and Applications, vol. 271, 75-117 (2018), Birkhäuser/Springer: Birkhäuser/Springer Cham · Zbl 1427.15016 |
| [10] | Bart, H.; Ehrhardt, T.; Silbermann, B., Unions of rank/trace complete preorders, Linear Algebra Appl., 570, 181-224 (2019) · Zbl 1417.15019 |
| [11] | Bart, H.; Ehrhardt, T.; Silbermann, B., How small can a sum of idempotents be?, Integral Equ. Oper. Theory, 92, 1, Article 10 pp. (2020) · Zbl 1504.47063 |
| [12] | Bart, H.; Wagelmans, A. P.M., An integer programming problem and rank decomposition of block upper triangular matrices, Linear Algebra Appl., 305, 107-129 (2000) · Zbl 0951.15013 |
| [13] | Birkhoff, G., Lattice Theory, American Mathematical Society Colloquium Publications, vol. XXV (1967), American Mathematical Society: American Mathematical Society Providence, R.I. · Zbl 0126.03801 |
| [14] | Davis, R. L., Algebras defined by patterns of zeros, J. Comb. Theory, 9, 257-260 (1970) · Zbl 0211.06401 |
| [15] | Fang, S.-C.; Puthenpura, S., Linear Optimization and Extensions: Theory and Algorithms (1993), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0799.90080 |
| [16] | Habib, M.; Jegou, R., \( \mathsf{N} \)-free posets as generalizations of series-parallel posets, Discrete Appl. Math., 12, 3, 279-291 (1985) · Zbl 0635.06002 |
| [17] | Hartwig, R. E.; Putcha, M. S., When is a matrix a sum of idempotents?, Linear Multilinear Algebra, 26, 279-286 (1990) · Zbl 0696.15011 |
| [18] | Laffey, T. J., A structure theorem for some matrix algebras, Linear Algebra Appl., 162-164, 205-215 (1992) · Zbl 0758.16010 |
| [19] | Papadimitriou, C. H.; Steiglitz, K., Combinatorial Optimization, Algorithms and Complexity (1982), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0503.90060 |
| [20] | Shitov, Y., A partial order that is not rank/trace complete, Linear Algebra Appl., 582, 99-102 (2019) · Zbl 1425.15033 |
| [21] | Stanley, R. P., Enumerative Combinatorics, Vol. 1 (1997), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0889.05001 |
| [22] | Wu, P. Y., Sums of idempotent matrices, Linear Algebra Appl., 142, 43-54 (1990) · Zbl 0724.15012 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
