Applications of Mathematics, Vol. 65, No. 5, pp. 557-597, 2020


The Collatz-Wielandt quotient for pairs of nonnegative operators

Shmuel Friedland

Received October 10, 2019.   Published online June 30, 2020.

Abstract:  In this paper we consider two versions of the Collatz-Wielandt quotient for a pair of nonnegative operators $A,B$ that map a given pointed generating cone in the first space into a given pointed generating cone in the second space. If the two spaces and two cones are identical, and $B$ is the identity operator, then one version of this quotient is the spectral radius of $A$. In some applications, as commodity pricing, power control in wireless networks and quantum information theory, one needs to deal with the Collatz-Wielandt quotient for two nonnegative operators. In this paper we treat the two important cases: a pair of rectangular nonnegative matrices and a pair of completely positive operators. We give a characterization of minimal optimal solutions and polynomially computable bounds on the Collatz-Wielandt quotient.
Keywords:  Perron-Frobenius theory; Collatz-Wielandt quotient; completely positive operator; commodity pricing; wireless network; quantum information theory
Classification MSC:  15A22, 15A45, 15B48, 15B57, 94A40


References:
[1] C. Avin, M. Borokhovich, Y. Haddad, E. Kantor, Z. Lotker, M. Parter, D. Peleg: Generalized Perron-Frobenius theorem for multiple choice matrices, and applications. Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013. SIAM, Philadelphia, 2013, 478-497. DOI 10.1137/1.9781611973105.35 | MR 3186769 | Zbl 1422.90013
[2] C. Avin, M. Borokhovich, Y. Haddad, E. Kantor, Z. Lotker, M. Parter, D. Peleg: Generalized Perron-Frobenius theorem for nonsquare matrices. Available at https://arxiv.org/abs/1308.5915 (2013), 55 pages.
[3] A. Berman, R. J. Plemmons: Nonnegative Matrices in Mathematical Sciences. Computer Science and Applied Mathematics. Academic Press, New York (1979). DOI 10.1137/1.9781611971262 | MR 0544666 | Zbl 0484.15016
[4] G. Boutry, M. Elad, G. H. Golub, P. Milanfar: The generalized eigenvalue problem for nonsquare pencils using a minimal perturbation approach. SIAM J. Matrix Anal. Appl. 27 (2005), 582-601. DOI 10.1137/S0895479803428795 | MR 2179690 | Zbl 1100.65035
[5] S. Boyd, L. Vandenberghe: Convex Optimization. Cambridge University Press, New York (2004). DOI 10.1017/CBO9780511804441 | MR 2061575 | Zbl 1058.90049
[6] M.-D. Choi: Completely positive linear maps on complex matrices. Linear Algebra Appl. 10 (1975), 285-290. DOI 10.1016/0024-3795(75)90075-0 | MR 0376726 | Zbl 0327.15018
[7] D. Chu, G. H. Golub: On a generalized eigenvalue problem for nonsquare pencils. SIAM J. Matrix Anal. Appl. 28 (2006), 770-787. DOI 10.1137/050628258 | MR 2262980 | Zbl 1128.15004
[8] L. Collatz: Einschliessungssatz für die charakteristischen Zahlen von Matrizen. Math. Z. 48 (1942), 221-226. (In German.) DOI 10.1007/BF01180013 | MR 0008590 | Zbl 0027.00604
[9] I. Erdelyi: On the matrix equation $Ax=\lambda Bx$. J. Math. Anal. Appl. 17 (1967), 119-132. DOI 10.1016/0022-247X(67)90169-2 | MR 0202734 | Zbl 0153.04902
[10] S. Friedland: Characterizations of the spectral radius of positive operators. Linear Algebra Appl. 134 (1990), 93-105. DOI 10.1016/0024-3795(90)90008-Z | MR 1060012 | Zbl 0707.15005
[11] S. Friedland: Characterizations of spectral radius of positive operators on $C^*$ algebras. J. Funct. Anal. 97 (1991), 64-70. DOI 10.1016/0022-1236(91)90016-X | MR 1105655 | Zbl 0745.47024
[12] S. Friedland: Matrices: Algebra, Analysis and Applications. World Scientific, Hackensack (2016). DOI 10.1142/9567 | MR 3467205 | Zbl 1337.15002
[13] S. Friedland, R. Loewy: On the extreme points of quantum channels. Linear Algebra Appl. 498 (2016), 553-573. DOI 10.1016/j.laa.2016.02.001 | MR 3478578 | Zbl 1334.15086
[14] G. F. Frobenius: Über Matrizen aus positiven Elementen. Berl. Ber. 1908 (1908), 471-476. (In German.) JFM 39.0213.03
[15] G. F. Frobenius: Über Matrizen aus positiven Elementen II. Berl. Ber. 1909 (1909), 514-518. (In German.) JFM 40.0202.02
[16] G. F. Frobenius: Über Matrizen aus nicht negativen Elementen. Berl. Ber. 1912 (1912), 456-477. (In German.) JFM 43.0204.09
[17] F. R. Gantmacher: The Theory of Matrices. Vol. 1. Chelsea Publishing, New York (1959). MR 0107649 | Zbl 0927.15001
[18] F. R. Gantmacher: The Theory of Matrices. Vol. 2. Chelsea Publishing, New York (1959). MR 0107649 | Zbl 0927.15002
[19] G. H. Golub, C. F. Van Loan: Matrix Computations. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore (2013). MR 3024913 | Zbl 1268.65037
[20] M. Grötschel, L. Lovász, A. Schrijver: Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics 2. Springer, Berlin (1988). DOI 10.1007/978-3-642-97881-4 | MR 0936633 | Zbl 0634.05001
[21] M. B. Hastings: Superadditivity of communication capacity using entangled inputs. Nature Phys. 5 (2009), 255-257. DOI 10.1038/nphys1224
[22] A. S. Holevo: The additivity problem in quantum information theory. Proceedings of the International Congress of Mathematicians (ICM). Vol. III. European Mathematical Society, Zürich, 2006, 999-1018. DOI 10.4171/022-3/49 | MR 2275716 | Zbl 1100.94007
[23] A. S. Holevo: Quantum Systems, Channels, Information: A Mathematical Introduction. De Gruyter Studies in Mathematical Physics 16. De Gruyter, Berlin (2012). DOI 10.1515/9783110273403 | MR 2986302 | Zbl 1332.81003
[24] R. A. Horn, C. R. Johnson: Matrix Analysis. Cambridge University Press, Cambridge (2013). DOI 10.1017/9781139020411 | MR 2978290 | Zbl 1267.15001
[25] S. Karlin: Positive operators. J. Math. Mech. 8 (1959), 905-937. DOI 10.1512/iumj.1959.8.58058 | MR 0114138 | Zbl 0087.11002
[26] M. G. Kreĭn, M. A. Rutman: Linear operators leaving invariant cone in a Banach space. Usp. Mat. Nauk 3 (1948), 3-95. (In Russian.) MR 0027128 | Zbl 0030.12902
[27] L. Lovász: An Algorithmic Theory of Numbers, Graphs and Convexity. CBMS-NSF Regional Conference Series in Applied Mathematics 50. SIAM, Philadelphia (1986). DOI 10.1137/1.9781611970203 | MR 0861822 | Zbl 0606.68039
[28] O. L. Mangasarian: Perron-Frobenius properties of $Ax-\lambda Bx$. J. Math. Anal. Appl. 36 (1971), 86-102. DOI 10.1016/0022-247X(71)90020-5 | MR 0285555 | Zbl 0224.15010
[29] C. B. Mendl, M. M. Wolf: Unital quantum channels - convex structure and revivals of Birkhoff’s theorem. Commun. Math. Phys. 289 (2009), 1057-1086. DOI 10.1007/s00220-009-0824-2 | MR 2511660 | Zbl 1167.81011
[30] C. D. Meyer: Matrix Analysis and Applied Linear Algebra. SIAM, Philadelphia (2000). DOI 10.1137/1.9780898719512 | MR 1777382 | Zbl 0962.15001
[31] H. Minc: Nonnegative Matrices. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1988). MR 0932967 | Zbl 0638.15008
[32] O. Perron: Zur Theorie der Matrices. Math. Ann. 64 (1907), 248-263. (In German.) DOI 10.1007/BF01449896 | MR 1511438 | JFM 38.0202.01
[33] D. Petz: Quantum Information Theory and Quantum Statistics. Theoretical and Mathematical Physics. Springer, Berlin (2008). DOI 10.1007/978-3-540-74636-2 | MR 2363070 | Zbl 1145.81002
[34] S. U. Pillai, T. Suel, S. Cha: The Perron-Frobenius theorem: Some of its applications. IEEE Signal Process. Magazine 22 (2005), 62-75. DOI 10.1109/MSP.2005.1406483
[35] H. H. Schaeffer: Banach Lattices and Positive Operators. Die Grundlehren der mathematischen Wissenschaften 215. Springer, Berlin (1974). DOI 10.1007/978-3-642-65970-6 | MR 0423039 | Zbl 0296.47023
[36] E. Seneta: Non-Negative Matrices and Markov Chains. Springer Series in Statistics. Springer, New York (1981). DOI 10.1007/0-387-32792-4 | MR 0719544 | Zbl 0471.60001
[37] M. E. Shirokov: On the structure of optimal sets for a quantum channel. Probl. Inf. Transm. 42 (2006), 282-297 Translation from Probl. Peredachi Inf. 42 (2006), 23-40. DOI 10.1134/S0032946006040028 | MR 2278809 | Zbl 1237.94039
[38] P. W. Shor: Additivity of the classical capacity of entanglement-breaking quantum channels. J. Math. Phys. 43 (2002), 4334-4340. DOI 10.1063/1.1498000 | MR 1924442 | Zbl 1060.94004
[39] R. Srikant: The Mathematics of Internet Congestion Control. Systems and Control: Foundations and Applications. Birkhäuser, Boston (2004). DOI 10.1007/978-0-8176-8216-3 | MR 2018967 | Zbl 1086.68018
[40] H. Wielandt: Unzerlegbare, nicht-negative Matrizen. Math. Z. 52 (1950), 642-648. (In German.) DOI 10.1007/BF02230720 | MR 0035265 | Zbl 0035.29101

Affiliations:   Shmuel Friedland, Department of Mathematics, Statistics and Computer Science, University of Illinois, 851 S. Morgan Street, Chicago, IL, 60607-7045, U.S.A., e-mail: friedlan@uic.edu


 
PDF available at: