The game-theoretic value and the spectral radius of a nonnegative matrix

Cohen, Joel E.; Friedland, Shmuel

doi:10.1090/S0002-9939-1985-0770520-0

The game-theoretic value and the spectral radius of a nonnegative matrix
HTML articles powered by AMS MathViewer

by Joel E. Cohen and Shmuel Friedland PDF

Proc. Amer. Math. Soc. 93 (1985), 205-211 Request permission

Abstract:

We relate some minimax functions of matrices to some spectral functions of matrices. If $A$ is a nonnegative $n \times n$ matrix, $\upsilon (A)$ is the game-theoretic value of $A$, and $\rho (A)$ is the spectral radius of $A$, then $\upsilon (A) \leq \rho (A)$. Necessary and sufficient conditions for $\upsilon (A) = \rho (A)$ are given. It follows that if $A$ is nonnegative and irreducible and $n > 1$, then $\upsilon (A) < \rho (A)$. Also, if, for a real matrix $A$ and a positive matrix $B$, $\upsilon (A,B) = {\sup _X}{\inf _Y}{X^T}AY/{X^T}BY$ over probability vectors $X$ and $Y$, then for nonnegative, nonsingular $A$ and positive $B$, $\rho (AB) = {[\upsilon ({A^{ - 1}},B)]^{ - 1}}$.

References

Garrett Birkhoff, Extensions of Jentzsch’s theorem, Trans. Amer. Math. Soc. 85 (1957), 219–227. MR 87058, DOI 10.1090/S0002-9947-1957-0087058-6
Garrett Birkhoff and Richard S. Varga, Reactor criticality and nonnegative matrices, J. Soc. Indust. Appl. Math. 6 (1958), 354–377. MR 100984
David Blackwell, Minimax and irreducible matrices, J. Math. Anal. Appl. 3 (1961), 37–39. MR 139495, DOI 10.1016/0022-247X(61)90005-1
Monroe D. Donsker and S. R. S. Varadhan, On a variational formula for the principal eigenvalue for operators with maximum principle, Proc. Nat. Acad. Sci. U.S.A. 72 (1975), 780–783. MR 361998, DOI 10.1073/pnas.72.3.780
Melvin Dresher, The mathematics of games of strategy, Dover Publications, Inc., New York, 1981. Theory and applications; Reprint of the 1961 original. MR 671740
Shmuel Friedland, Convex spectral functions, Linear and Multilinear Algebra 9 (1980/81), no. 4, 299–316. MR 611264, DOI 10.1080/03081088108817381

Theory of matrices

Lynn H. Loomis, On a theorem of von Neumann, Proc. Nat. Acad. Sci. U.S.A. 32 (1946), 213–215. MR 17258, DOI 10.1073/pnas.32.8.213
T. E. S. Raghavan, Completely mixed games and $M$-matrices, Linear Algebra Appl. 21 (1978), no. 1, 35–45. MR 484461, DOI 10.1016/0024-3795(87)90198-4
L. S. Shapley, Stochastic games, Proc. Nat. Acad. Sci. U.S.A. 39 (1953), 1095–1100. MR 61807, DOI 10.1073/pnas.39.10.1953
Maurice Sion, On general minimax theorems, Pacific J. Math. 8 (1958), 171–176. MR 97026
Richard S. Varga, Matrix iterative analysis, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1962. MR 0158502
J. v. Neumann, Zur Theorie der Gesellschaftsspiele, Math. Ann. 100 (1928), no. 1, 295–320 (German). MR 1512486, DOI 10.1007/BF01448847

Ueber ein oekonomisches Gleichungsystem und eine Verallgemeinerung des Brouwerschen Fixpunktsatzes

Helmut Wielandt, Unzerlegbare, nicht negative Matrizen, Math. Z. 52 (1950), 642–648 (German). MR 35265, DOI 10.1007/BF02230720
Richard Bellman, On an iterative procedure for obtaining the Perron root of a positive matrix, Proc. Amer. Math. Soc. 6 (1955), 719–725. MR 71863, DOI 10.1090/S0002-9939-1955-0071863-X
T. E. S. Raghavan, Some remarks on matrix games and nonnegative matrices, SIAM J. Appl. Math. 36 (1979), no. 1, 83–85. MR 519185, DOI 10.1137/0136008