Rank decomposition in zero pattern matrix algebras

Harm Bart; Torsten Ehrhardt; Bernd Silbermann

Czechoslovak Mathematical Journal (2016)

  • Volume: 66, Issue: 3, page 987-1005
  • ISSN: 0011-4642

Abstract

top
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, A. P. M. Wagelmans (2000). The proof involves elements from integer programming and employs Farkas' lemma. The algebra of block upper triangular matrices can be viewed as a matrix algebra determined by a pattern of zeros. The present note is concerned with the question whether the decomposition result referred to above can be extended to other zero pattern matrix algebras. It is shown that such a generalization does indeed hold for certain digraphs determining the pattern of zeros. The digraphs in question can be characterized in terms of forests, i.e., disjoint unions of rooted trees.

How to cite

top

Bart, Harm, Ehrhardt, Torsten, and Silbermann, Bernd. "Rank decomposition in zero pattern matrix algebras." Czechoslovak Mathematical Journal 66.3 (2016): 987-1005. <http://eudml.org/doc/286807>.

@article{Bart2016,
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 H. Bart, A. P. M. Wagelmans (2000). The proof involves elements from integer programming and employs Farkas' lemma. The algebra of block upper triangular matrices can be viewed as a matrix algebra determined by a pattern of zeros. The present note is concerned with the question whether the decomposition result referred to above can be extended to other zero pattern matrix algebras. It is shown that such a generalization does indeed hold for certain digraphs determining the pattern of zeros. The digraphs in question can be characterized in terms of forests, i.e., disjoint unions of rooted trees.},
author = {Bart, Harm, Ehrhardt, Torsten, Silbermann, Bernd},
journal = {Czechoslovak Mathematical Journal},
keywords = {block upper triangularity; additive decomposition; rank constraints; zero pattern matrix algebra; preorder; partial order; Hasse diagram; rooted tree; out-tree; in-tree},
language = {eng},
number = {3},
pages = {987-1005},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Rank decomposition in zero pattern matrix algebras},
url = {http://eudml.org/doc/286807},
volume = {66},
year = {2016},
}

TY - JOUR
AU - Bart, Harm
AU - Ehrhardt, Torsten
AU - Silbermann, Bernd
TI - Rank decomposition in zero pattern matrix algebras
JO - Czechoslovak Mathematical Journal
PY - 2016
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 66
IS - 3
SP - 987
EP - 1005
AB - 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, A. P. M. Wagelmans (2000). The proof involves elements from integer programming and employs Farkas' lemma. The algebra of block upper triangular matrices can be viewed as a matrix algebra determined by a pattern of zeros. The present note is concerned with the question whether the decomposition result referred to above can be extended to other zero pattern matrix algebras. It is shown that such a generalization does indeed hold for certain digraphs determining the pattern of zeros. The digraphs in question can be characterized in terms of forests, i.e., disjoint unions of rooted trees.
LA - eng
KW - block upper triangularity; additive decomposition; rank constraints; zero pattern matrix algebra; preorder; partial order; Hasse diagram; rooted tree; out-tree; in-tree
UR - http://eudml.org/doc/286807
ER -

References

top
  1. Bart, H., Ehrhardt, T., Silbermann, B., Echelon type canonical forms in upper triangular matrix algebras, (to appear) in Oper. Theory, Adv. Appl. 
  2. Bart, H., Ehrhardt, T., Silbermann, B., Sums of idempotents and logarithmic residues in zero pattern matrix algebras, Linear Algebra Appl. 498 (2016), 262-316. (2016) Zbl1334.15039MR3478563
  3. Bart, H., Ehrhardt, T., Silbermann, B., Sums of idempotents and logarithmic residues in matrix algebras, Operator Theory and Analysis. The M. A. Kaashoek Anniversary Volume (Bart, H. et al. eds.), Oper. Theory, Adv. Appl. 122 (2001), 139-168. (2001) Zbl1047.46037MR1846056
  4. Bart, H., Ehrhardt, T., Silbermann, B., 10.1007/BF01206410, Integral Equations Oper. Theory 19 (1994), 135-152. (1994) Zbl0811.46043MR1274555DOI10.1007/BF01206410
  5. Bart, H., Wagelmans, A. P. M., An integer programming problem and rank decomposition of block upper triangular matrices, Linear Algebra Appl. 305 (2000), 107-129. (2000) Zbl0951.15013MR1733797
  6. Birkhoff, G., Lattice Theory, Colloquium Publications Vol. 25 American Mathematical Society, Providence (1967). (1967) Zbl0153.02501MR0227053
  7. Davis, R. L., 10.1016/S0021-9800(70)80064-3, J. Comb. Theory 9 (1970), 257-260. (1970) Zbl0211.06401MR0268208DOI10.1016/S0021-9800(70)80064-3
  8. Fang, S.-C., Puthenpura, S., Linear Optimization and Extensions: Theory and Algorithms, Prentice-Hall, Englewood Cliffs (1993). (1993) 
  9. Harary, F., Graph Theory, Addison-Wesley Series in Mathematics, Reading, Mass. Addison-Wesley Publishing Company (1969). (1969) Zbl0196.27202MR0256911
  10. Laffey, T. J., A structure theorem for some matrix algebras, Linear Algebra Appl. 162-164 (1992), 205-215. (1992) Zbl0758.16010MR1148400
  11. Papadimitriou, C. H., Steiglitz, K., Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Englewood Cliffs (1982). (1982) Zbl0503.90060MR0663728
  12. Schrijver, A., Theory of Linear and Integer Programming, Wiley-Interscience Series in Discrete Mathematics John Wiley & Sons, Chichester (1986). (1986) Zbl0665.90063MR0874114
  13. Szpilrajn, E., 10.4064/fm-16-1-386-389, Fundamenta Mathematicae 16 (1930), 386-389 French available at http://matwbn.icm.edu.pl/ksiazki/fm/fm16/fm16125.pdf. (1930) DOI10.4064/fm-16-1-386-389

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.