Previous |  Up |  Next

Article

Full entry | Fulltext not available (moving wall 24 months)      Feedback
Keywords:
Perron-Frobenius theory; Collatz-Wielandt quotient; completely positive operator; commodity pricing; wireless network; quantum information theory
Summary:
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.
References:
[1] Avin, C., Borokhovich, M., Haddad, Y., Kantor, E., Lotker, Z., Parter, M., Peleg, D.: 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] Avin, C., Borokhovich, M., Haddad, Y., Kantor, E., Lotker, Z., Parter, M., Peleg, D.: Generalized Perron-Frobenius theorem for nonsquare matrices. Available at https://arxiv.org/abs/1308.5915 (2013), 55 pages. MR 3186769
[3] Berman, A., Plemmons, R. J.: 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] Boutry, G., Elad, M., Golub, G. H., Milanfar, P.: 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] Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, New York (2004). DOI 10.1017/CBO9780511804441 | MR 2061575 | Zbl 1058.90049
[6] Choi, M.-D.: 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] Chu, D., Golub, G. H.: 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] Collatz, L.: Einschliessungssatz für die charakteristischen Zahlen von Matrizen. Math. Z. 48 (1942), 221-226 German. DOI 10.1007/BF01180013 | MR 0008590 | Zbl 0027.00604
[9] Erdelyi, I.: 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] Friedland, S.: 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] Friedland, S.: 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] Friedland, S.: Matrices: Algebra, Analysis and Applications. World Scientific, Hackensack (2016). DOI 10.1142/9567 | MR 3467205 | Zbl 1337.15002
[13] Friedland, S., Loewy, R.: 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] Frobenius, G. F.: Über Matrizen aus positiven Elementen. Berl. Ber. 1908 (1908), 471-476 German \99999JFM99999 39.0213.03.
[15] Frobenius, G. F.: Über Matrizen aus positiven Elementen II. Berl. Ber. 1909 (1909), 514-518 German \99999JFM99999 40.0202.02.
[16] Frobenius, G. F.: Über Matrizen aus nicht negativen Elementen. Berl. Ber. 1912 (1912), 456-477 German \99999JFM99999 43.0204.09.
[17] Gantmacher, F. R.: The Theory of Matrices. Vol. 1. Chelsea Publishing, New York (1959). MR 0107649 | Zbl 0927.15001
[18] Gantmacher, F. R.: The Theory of Matrices. Vol. 2. Chelsea Publishing, New York (1959). MR 0107649 | Zbl 0927.15002
[19] Golub, G. H., Loan, C. F. Van: Matrix Computations. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore (2013). MR 3024913 | Zbl 1268.65037
[20] Grötschel, M., Lovász, L., Schrijver, A.: 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] Hastings, M. B.: Superadditivity of communication capacity using entangled inputs. Nature Phys. 5 (2009), 255-257. DOI 10.1038/nphys1224
[22] Holevo, A. S.: 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] Holevo, A. S.: 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] Horn, R. A., Johnson, C. R.: Matrix Analysis. Cambridge University Press, Cambridge (2013). DOI 10.1017/9781139020411 | MR 2978290 | Zbl 1267.15001
[25] Karlin, S.: Positive operators. J. Math. Mech. 8 (1959), 905-937. DOI 10.1512/iumj.1959.8.58058 | MR 0114138 | Zbl 0087.11002
[26] Kreĭn, M. G., Rutman, M. A.: Linear operators leaving invariant cone in a Banach space. Usp. Mat. Nauk 3 (1948), 3-95 Russian. MR 0027128 | Zbl 0030.12902
[27] Lovász, L.: 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] Mangasarian, O. L.: 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] Mendl, C. B., Wolf, M. M.: 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] Meyer, C. D.: Matrix Analysis and Applied Linear Algebra. SIAM, Philadelphia (2000). DOI 10.1137/1.9780898719512 | MR 1777382 | Zbl 0962.15001
[31] Minc, H.: Nonnegative Matrices. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1988). MR 0932967 | Zbl 0638.15008
[32] Perron, O.: Zur Theorie der Matrices. Math. Ann. 64 (1907), 248-263 German \99999JFM99999 38.0202.01. DOI 10.1007/BF01449896 | MR 1511438
[33] Petz, D.: 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] Pillai, S. U., Suel, T., Cha, S.: The Perron-Frobenius theorem: Some of its applications. IEEE Signal Process. Magazine 22 (2005), 62-75. DOI 10.1109/MSP.2005.1406483
[35] Schaeffer, H. H.: 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] Seneta, E.: 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] Shirokov, M. E.: 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] Shor, P. W.: 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] Srikant, R.: 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] Wielandt, H.: Unzerlegbare, nicht-negative Matrizen. Math. Z. 52 (1950), 642-648 German. DOI 10.1007/BF02230720 | MR 0035265 | Zbl 0035.29101
Partner of
EuDML logo