zbMATH — the first resource for mathematics

Totally expanding multiplicative systems. (English) Zbl 1078.15017
A single-matrix multiplicative system is given by the entries of the sequence \(\{Q^{n}x(0)\}_{n=0,1,\dots}\), where \(Q\) is an \(N \times N\) non-negative transition matrix and \(x(0)\) is an \(N \times 1\) semi-positive input vector. A single-matrix multiplicative system is said to be totally expanding if each coordinate of the sequence \((x(1), x(2), \dots)\) is unbounded.
Here, multiple-matrix multiplicative systems are studied. They are obtained when the single matrix \(Q\) is replaced by a set \(\{Q^{\delta}: \delta \in D\}\) of \(N \times N\) non-negative matrices, where \(D\) has a “product form” structure \(D= D_1 \times \dots \times D_N\), where for each \(i\), \(D_i\) is a finite non-empty set of non-negative \(1 \times N\) vectors. Each element \(\delta\) of \(D\) is called a policy. Such a system is said to be totally expanding if, for each policy \(\delta\), each coordinate of the sequence \((x^{\delta}(1), x^{\delta}(2), \dots)\) is unbounded.
It is shown that the multiple-matrix multiplicative system is totally expanding if and only if there are no “degenerate” coordinates, the growth rate \(\rho^{\delta}_{i} > 1\) for each \(\delta\) and each \(i\) and there exists an \(N \times 1\) vector \(u\) satisfying certain linear inequalities. These linear inequalities can give also the estimate of the smallest coordinate-dependent growth rate of the system.

15B48 Positive matrices and their generalizations; cones of matrices
15A18 Eigenvalues, singular values, and eigenvectors
90B50 Management decision making, including multiple objectives
Full Text: DOI
[1] Bellman, R., Dynamic programming, (1957.), Princeton University Press Princeton, NJ
[2] Berman, A.; Plemmons, R.J., ()
[3] Cain, B.; Hershkowitz, D.; Schneider, H., Theorems of the alternative for cones and Lyapunov regularity, Czech math. J., 47, 467-499, (1997) · Zbl 0902.15011
[4] Denardo, E.V.; Rothblum, U.G., Optimal stopping, exponential utility, and linear programming, Math. programm., 16, 228-244, (1979)
[5] E.V. Denardo, U.G. Rothblum, A turnpike theorem for a risk-sensitive Markov decision process with stopping, submitted for publication. · Zbl 1151.90571
[6] Fox, B.L.; Landi, D.M., An algorithm for identifying the ergodic subchains and transient states of a stochastic matrix, Commun. assoc. comput. Mach., 11, 619-621, (1968) · Zbl 0177.45701
[7] Frobenius, G., Über matrizen aus positiven elementen, Sitzungsber. kgl. preussischen akad. wiss. Berlin, 471-476, (1908) · JFM 39.0213.03
[8] Frobenius, G., Über matrizen aus positiven elementen II, Sitzungsber. kgl. preussischen akad. wiss. Berlin, 514-518, (1909) · JFM 40.0202.02
[9] Frobenius, G., Über matrizen aus nicht negativen elementen III, Sitzungsber. kgl. preussischen akad. wiss. Berlin, 456-477, (1912) · JFM 43.0204.09
[10] Friedland, S.; Schneider, H., The growth of powers of a nonnegative matrix, SIAM J. algebra. discrete methods, 1, 185-200, (1980) · Zbl 0498.65018
[11] Hartfiel, D.J., Nonhomogeneous matrix products, (2002.), World Scientific New Jersey
[12] Hershkowitz, D.; Schneider, H., Solutions of Z-matrix equations, Linear algebra appl., 106, 25-38, (1988) · Zbl 0652.15016
[13] Howard, R.A.; Matheson, J.E., Risk sensitive Markov decision processes, Manage. sci., 8, 356-369, (1972) · Zbl 0238.90007
[14] Lindquist, B.H., Asymptotic properties of powers of nonnegative powers, with applications, Linear algebra appl., 114, 555-588, (1989) · Zbl 0668.15012
[15] Perron, O., Zur theorie der matrizen, Math. ann., 64, 248-263, (1908) · JFM 38.0202.01
[16] U.G. Rothblum, Multiplicative Markov decision chains, Ph.D. thesis, Department of Operations Research, Stanford University, Stanford, CA, 1974. · Zbl 0535.90097
[17] Rothblum, U.G., Sensitive growth analysis of multiplicative systems I: the stationary approach, SIAM J. algebra. discrete methods, 2, 25-34, (1981) · Zbl 0498.60047
[18] Rothblum, U.G., Multiplicative Markov decision chains, Math. oper. res., 9, 6-24, (1984) · Zbl 0535.90097
[19] Rothblum, U.G.; Whittle, P., Growth decision processes, Math. oper. res., 7, 582-601, (1982) · Zbl 0498.90082
[20] Seneta, E., Non-negative matrices and Markov chains, (1981.), Springer-Verlag New York
[21] Schneider, H., The role of the marked reduced graph of a nonnegative matrix on the Jordan form and on related properties: a survey, Linear algebra appl., 84, 161-189, (1986) · Zbl 0613.15017
[22] Schrijver, A., Theory of linear and integer programming, (1986.), John Wiley and Sons New York
[23] Tam, B.S.; Wu, S.F., On the Collatz-Wielandt sets associated with a cone-preserving map, Linear algebra appl., 125, 23-28, (1990)
[24] A.F. Veinott, Jr., Personal communication to U.G. Rothblum, 1973.
[25] Zijm, W.H.M., Generalized eigenvectors and sets of non-negative matrices, Linear algebra appl., 59, 91-113, (1984) · Zbl 0548.15015
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.