×

Wielandt-type bounds for primitive mappings of partially ordered sets. (English. Russian original) Zbl 0736.05011

Math. Notes 45, No. 6, 450-454 (1989); translation from Mat. Zametki 45, No. 6, 30-35 (1989).
From the introduction: In [Math. Z. 52, No. 5, 642–648 (1950; Zbl 0035.29101)], H. Wielandt has given without proof the following result:
\[ t(\varphi)\le n^2-2n+2 \tag{1} \]
for any primitive additive mapping \(\varphi\). The above presented situation is generalized in M. A. Perles [Proc. Colloq. Convexity, Copenhagen 1965, 221–228 (1967; Zbl 0148.37001)], where for \(X\) one considers an arbitrary lattice, while the corresponding class consists of the mappings that preserve sup. (Thus, in the case \(X=2^N\) this class is the class of additive mappings.) Generalizing in an appropriate manner the concept of a primitive mapping, the author obtains a bound that is similar to (1).
We consider an even more general situation: for \(X\) we take an arbitrary partially ordered set, while the corresponding class consists of the monotone mappings of \(X\) into itself. This class is significantly larger than the class of additive mappings (in the case \(X=2^ N\)). Introducing an appropriate definition of a primitive mapping, we obtain bounds similar to (1) and we prove their sharpness. This gives us the possibility to extend the results, known for nonnegative matrices, to polynomial operators of an arbitrary degree with nonnegative coefficients.

MSC:

05A99 Enumerative combinatorics
06A06 Partial orders, general
15A99 Basic linear algebra
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] D. Rosenblatt, ?On the graphs and asymptotic forms of finite Boolean relation matrices and stochastic matrices,? Naval Res. Logist. Quart.,4, No. 2, 151-167 (1957).
[2] V. Pták, ?On a certain combinatorial theorem and its applications to nonnegative matrices,? Czechoslovak Math. J.,8, (83), No. 4, 487-495 (1958). · Zbl 0082.24402
[3] J. Sedlacek, ?On incidence matrices of directed graphs,? Casopis Pest. Mat.,84, No. 3, 303-316 (1959).
[4] Yu. I. Lyubich, ?Estimates for the optimal determination of indeterminate autonomous automata,? Sib. Mat. Zh.,5, No. 2, 337-355 (1964). · Zbl 0192.08104
[5] E. A. Bender and T. W. Tucker, ?The exponents of strongly connected graphs,? Can. J. Math.,21., No. 4, 769-782 (1969). · Zbl 0179.52702
[6] S. Schwarz, ?On a sharp estimation in the theory of binary relations on a finite set,? Czechoslovak Math. J.,20 (95), No. 4, 703-714 (1970). · Zbl 0226.20061
[7] S. Schwarz, ?On the semigroup of binary relations on a finite set,? Czechoslovak Math. J.,20, (95), No. 4, 632-679 (1970). · Zbl 0228.20034
[8] H. Wielandt, ?Unzerlegbare, nicht negative Matrizen,? Math. Z.,52, No. 5, 642-648 (1950). · Zbl 0035.29101
[9] J. C. Holladay and R. S. Varga, ?On powers of nonnegative matrices,? Proc. Am. Math. Soc.,9, No. 4, 631-634 (1958). · Zbl 0096.00805
[10] M. A. Perles, ?Critical exponents of convex sets,? in: Proceedings of the Colloquium on Convexity (Copenhagen, 1965), Københavns Univ. Mat. Inst., Copenhagen (1967), pp. 221-228.
[11] S. Schwarz, ?A new approach to some problems in the theory of nonnegative matrices,? Can. J. Math.,16, (91), No. 2, 274-284 (1966). · Zbl 0232.20140
[12] J. Ma?ík and V. Pták, ?Norms, spectra and combinatorial properties of matrices,? Czechoslovak Math. J.,10, (85), No. 2, 181-196 (1960). · Zbl 0093.24205
[13] Yu. I. Lyubich and M. I. Tabachnikov, ?On a theorem of Marik and Ptak,? Sib. Mat. Zh.,10, No. 2, 470-473 (1969).
[14] Yu. I. Lyubich and M. I. Tabachnikov, ?Subharmonic functions on a directed graph,? Sib. Mat. Zh.,10, No. 3, 600-613 (1969). · Zbl 0194.13702
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.