Linear operators that strongly preserve graphical properties of matrices. (English) Zbl 0776.05068

Summary: An operator on the set \({\mathcal M}\) of \(n\times n\) matrices strongly preseveres a subset \({\mathcal F}\) if it maps \({\mathcal F}\) into \({\mathcal F}\) and \({\mathcal M}\backslash{\mathcal F}\) into \({\mathcal M\backslash F}\). The operator semigroup of \({\mathcal F}\) is the semigroup of linear operators strongly preserving \({\mathcal F}\). We show that all the \(n\times n\) matrix-families which are determined by the directed graphs of their members and satisfy a short list of conditions, have the same operator semigroup \(\Sigma\), and we determine the generators of \(\Sigma\). Among those matrix-families are: the irreducible matrices; the matrices whose directed graphs have maximum cycle length \(l\geq k\) for fixed \(k\geq 4\); and the matrices whose directed graphs have a path of length at least \(l\geq k\) for fixed \(k\geq 3\). Similar results are obtained for matrix-families determined by the undirected graphs of their members.


05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15A04 Linear transformations, semilinear transformations
05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.)
05C38 Paths and cycles
15B33 Matrices over special rings (quaternions, finite fields, etc.)
Full Text: DOI


[1] Beasley, L. B.; Pullman, N. J., Boolean rank preserving operators and Boolean rank-1 spaces, Linear Algebra Appl., 65, 55-77 (1984) · Zbl 0536.20044
[2] Beasley, L. B.; Pullman, N. J., Linear operators that strongly preserve primitivity, Linear and Multilinear Algebra, 25, 206-213 (1989) · Zbl 0685.15005
[3] Beasley, L. B.; Pullman, N. J., Linear operators preserving properties of graphs, Congr. Numer., 70, 105-112 (1990)
[4] Beasley, L. B.; Pullman, N. J., Linear operators strongly preserving diagraphs whose maximum cycle length is small, Linear and Multilinear Algebra, 28, 111-117 (1990) · Zbl 0731.05023
[5] Brualdi, R. A.; Harary, F.; Miller, Z., Bigraphs versus digraphs via matrices, J. Graph Theory, 4, 51-73 (1980) · Zbl 0401.05059
[6] Gregory, D. A.; Pullman, N. J., Semiring rank: Boolean rank and nonnegative factorizations, J. Combin. Inform. System Sci., 8, 223-233 (1983) · Zbl 0622.15007
[7] Hershkowitz, D., Linear mappings which preserve acyclicity properties of graphs and digraphs and applications to matrices, Discrete Math., 64, 157-190 (1987) · Zbl 0634.05055
[8] Kim, K. H., Boolean Matrix Theory and Applications, (Pure Appl. Math., Vol.70 (1982), Marcel Dekker: Marcel Dekker New York)
[9] Pullman, N. J., Linear operators that preserve clique covering numbers, Ars Combin., 19A, 27-36 (1985) · Zbl 0562.05029
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.