Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

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


Authors: Joel E. Cohen and Shmuel Friedland
Journal: Proc. Amer. Math. Soc. 93 (1985), 205-211
MSC: Primary 15A42; Secondary 15A48, 90D05
DOI: https://doi.org/10.1090/S0002-9939-1985-0770520-0
MathSciNet review: 770520
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [G] Birkhoff [1957], Extensions of Jentzsch's theorem, Trans. Amer. Math. Soc. 85, 219-227. MR 0087058 (19:296a)
  • [G] Birkhoff and R. S. Varga [1958], Reactor criticality and nonnegative matrices, J. Soc. Indust. Appl. Math. 6, 354-377. MR 0100984 (20:7407)
  • [D] Blackwell [1961], Minimax and irreducible matrices, J. Math. Anal. Appl. 8, 37-39. MR 0139495 (25:2927)
  • [M] D. Donsker and S. R. S. Varadhan [1975], On a variational formula for the principal eigenvalue for operators with maximum principle, Proc. Nat. Acad. Sci. U.S.A. 72, 780-783. MR 0361998 (50:14440)
  • [M] Dresher [1961], Games of strategy: theory and applications, Prentice-Hall, Englewood Cliffs, N.J.; reprinted as The mathematics of games of strategy: theory and applications, Dover, New York, 1981. MR 671740 (83m:90093)
  • [S] Friedland [1981], Convex spectral functions, Linear and Multilinear Algebra 9, 299-316. MR 611264 (82d:15014)
  • [F] R. Gantmacher [1960], Theory of matrices, Chelsea, New York.
  • [L] H. Loomis [1946], On a theorem of von Neumann, Proc. Nat. Acad. Sci. U.S.A. 32, 213-215. MR 0017258 (8:128d)
  • [T] E. S. Raghavan [1978], Completely mixed games and $ M$-matrices, Linear Algebra Appl. 21, 35-45. MR 0484461 (58:4370)
  • [L] S. Shapley [1953], Stochastic games, Proc. Nat. Acad. Sci. U.S.A. 39, 1095-1100. MR 0061807 (15:887g)
  • [M] Sion [1958], On general minimax theorem, Pacific J. Math. 8, 171-176. MR 0097026 (20:3506)
  • [R] S. Varga [1962], Matrix iterative analysis, Prentice-Hall, Englewood Cliffs, N.J. MR 0158502 (28:1725)
  • [J] von Neumann [1928], Zur Theorie der Gesellschaftsspiele, Math. Ann. 100, 295-320; English transl., translated by Sonya Bargmann, On the theory of games of strategy, Contributions to the Theory of Games (A. W. Tucker and R. D. Luce, eds.), Vol. 4, Princeton Univ. Press, Princeton, N.J., 1959, pp. 13-42. MR 1512486
  • 1. -, [1937], Ueber ein oekonomisches Gleichungsystem und eine Verallgemeinerung des Brouwerschen Fixpunktsatzes, Ergebnisse Math. Kolloq., Vol. 8, pp. 73-83.
  • [H] Wielandt [1950], Unzerlegbare, nicht negative Matrizen, Math. Z. 52, 642-648. MR 0035265 (11:710g)
  • [R] Bellman [1955], On an iterative procedure for obtaining the Perron root of a positive matrix, Proc. Amer. Math. Soc. 6, 719-725. MR 0071863 (17:194l)
  • [T] E. S. Raghavan [1979], Some remarks on matrix games and nonnegative matrices, SIAM J. Appl. Math. 36, 83-85. MR 519185 (80d:90096)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 15A42, 15A48, 90D05

Retrieve articles in all journals with MSC: 15A42, 15A48, 90D05


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1985-0770520-0
Keywords: Eigenvalue inequality, Perron-Frobenius root, minimax, inverse nonnegative matrix, essentially nonnegative matrix, zero-sum two-person game, Jentzsch's theorem
Article copyright: © Copyright 1985 American Mathematical Society

American Mathematical Society