Hall exponents of matrices, tournaments and their line digraphs

Richard A. Brualdi; Kathleen P. Kiernan

Czechoslovak Mathematical Journal (2011)

  • Volume: 61, Issue: 2, page 461-481
  • ISSN: 0011-4642

Abstract

top
Let A be a square ( 0 , 1 ) -matrix. Then A is a Hall matrix provided it has a nonzero permanent. The Hall exponent of A is the smallest positive integer k , if such exists, such that A k is a Hall matrix. The Hall exponent has received considerable attention, and we both review and expand on some of its properties. Viewing A as the adjacency matrix of a digraph, we prove several properties of the Hall exponents of line digraphs with some emphasis on line digraphs of tournament (matrices).

How to cite

top

Brualdi, Richard A., and Kiernan, Kathleen P.. "Hall exponents of matrices, tournaments and their line digraphs." Czechoslovak Mathematical Journal 61.2 (2011): 461-481. <http://eudml.org/doc/196346>.

@article{Brualdi2011,
abstract = {Let $A$ be a square $(0,1)$-matrix. Then $A$ is a Hall matrix provided it has a nonzero permanent. The Hall exponent of $A$ is the smallest positive integer $k$, if such exists, such that $A^k$ is a Hall matrix. The Hall exponent has received considerable attention, and we both review and expand on some of its properties. Viewing $A$ as the adjacency matrix of a digraph, we prove several properties of the Hall exponents of line digraphs with some emphasis on line digraphs of tournament (matrices).},
author = {Brualdi, Richard A., Kiernan, Kathleen P.},
journal = {Czechoslovak Mathematical Journal},
keywords = {Hall matrix; Hall exponent; irreducible; primitive; tournament (matrix); line digraph; Hall matrix; Hall exponent; irreducible; primitive; tournament (matrix); line digraph; -matrix; permanent; adjacency matrix},
language = {eng},
number = {2},
pages = {461-481},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Hall exponents of matrices, tournaments and their line digraphs},
url = {http://eudml.org/doc/196346},
volume = {61},
year = {2011},
}

TY - JOUR
AU - Brualdi, Richard A.
AU - Kiernan, Kathleen P.
TI - Hall exponents of matrices, tournaments and their line digraphs
JO - Czechoslovak Mathematical Journal
PY - 2011
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 61
IS - 2
SP - 461
EP - 481
AB - Let $A$ be a square $(0,1)$-matrix. Then $A$ is a Hall matrix provided it has a nonzero permanent. The Hall exponent of $A$ is the smallest positive integer $k$, if such exists, such that $A^k$ is a Hall matrix. The Hall exponent has received considerable attention, and we both review and expand on some of its properties. Viewing $A$ as the adjacency matrix of a digraph, we prove several properties of the Hall exponents of line digraphs with some emphasis on line digraphs of tournament (matrices).
LA - eng
KW - Hall matrix; Hall exponent; irreducible; primitive; tournament (matrix); line digraph; Hall matrix; Hall exponent; irreducible; primitive; tournament (matrix); line digraph; -matrix; permanent; adjacency matrix
UR - http://eudml.org/doc/196346
ER -

References

top
  1. Aigner, M., 10.1007/BF01110285, Math. Z. 102 (1967), 56-61. (1967) MR0216981DOI10.1007/BF01110285
  2. Brualdi, R. A., Kiernan, K. P., Landau's and Rado's theorems and partial tournaments, Electron. J. Comb. 16 (2009). (2009) Zbl1159.05014MR2475542
  3. Brualdi, R. A., Li, Q., The interchange graph of tournaments with the same score vector, In: Progress in Graph Theory (Waterloo, Ont. 1982) Academic Press Toronto, ON (1984), 129-151. (1984) Zbl0553.05039MR0776798
  4. Brualdi, R. A., Liu, B., Hall exponents of Boolean matrices, Czechoslovak Math. J. 40(115) (1990), 659-670. (1990) Zbl0737.05028MR1084901
  5. Brualdi, R. A., Ryser, H. J., Combinatorial Matrix Theory, Cambridge Univ. Press Cambridge (1991). (1991) Zbl0746.05002MR1130611
  6. Hemminger, R. L., Beineke, L. W., Line graphs and line digraphs, Selected Topics in Graph Theory Academic Press, New York, 271-305 (1978). (1978) Zbl0434.05056
  7. Huang, Y., Liu, B., 10.1080/03081080902843554, Linear Multilinear Algebra 58 (2010), 699-710. (2010) Zbl1201.15014MR2722753DOI10.1080/03081080902843554
  8. Liu, B., Zhou, Bo, Estimates on strict Hall exponents, Australas. J. Comb. 19 (1999), 129-135. (1999) MR1695868
  9. Liu, B., Zhou, Bo, 10.1080/03081089908818611, Linear Multilinear Algebra 46 (1999), 165-175. (1999) MR1708586DOI10.1080/03081089908818611
  10. Moon, J. W., Pullman, N. J., 10.1016/S0021-9800(67)80009-7, J. Comb. Theory 3 (1967), 1-9. (1967) Zbl0166.00901MR0213264DOI10.1016/S0021-9800(67)80009-7
  11. Schwarz, Š., The semigroup of fully indecomposable relations and Hall relations, Czechoslovak Math. J. 23(98) (1973), 151-163. (1973) Zbl0261.20057MR0316612
  12. Tan, S., Liu, B., Zhang, D., Extreme tournaments with given primitive exponents, Australas. J. Comb. 28 (2003), 81-91. (2003) MR1998863

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.