×

Operator scaling: theory and applications. (English) Zbl 1432.68617

Summary: In this paper, we present a deterministic polynomial time algorithm for testing whether a symbolic matrix in non-commuting variables over \(\mathbb{Q}\) is invertible or not. The analogous question for commuting variables is the celebrated polynomial identity testing (PIT) for symbolic determinants. In contrast to the commutative case, which has an efficient probabilistic algorithm, the best previous algorithm for the non-commutative setting required exponential time [G. Ivanyos et al., Comput. Complexity 26, No. 3, 717–763 (2017; Zbl 1421.13002)] (whether or not randomization is allowed). The algorithm efficiently solves the “word problem” for the free skew field, and the identity testing problem for arithmetic formulae with division over non-commuting variables, two problems which had only exponential time algorithms prior to this work. The main contribution of this paper is a complexity analysis of an existing algorithm due to L. Gurvits [J. Comput. Syst. Sci. 69, No. 3, 448–484 (2004; Zbl 1093.81012)], who proved it was polynomial time for certain classes of inputs. We prove it always runs in polynomial time. The main component of our analysis is a simple (given the necessary known tools) lower bound on central notion of capacity of operators (introduced by Gurvits [loc. cit.]). We extend the algorithm to actually approximate capacity to any accuracy in polynomial time, and use this analysis to give quantitative bounds on the continuity of capacity (the latter is used in a subsequent paper on Brascamp-Lieb inequalities). We also extend the algorithm to compute not only singularity, but actually the (non-commutative) rank of a symbolic matrix, yielding a factor 2 approximation of the commutative rank. This naturally raises a relaxation of the commutative PIT problem to achieving better deterministic approximation of the commutative rank. Symbolic matrices in non-commuting variables, and the related structural and algorithmic questions, have a remarkable number of diverse origins and motivations. They arise independently in (commutative) invariant theory and representation theory, linear algebra, optimization, linear system theory, quantum information theory, approximation of the permanent and naturally in non-commutative algebra. We provide a detailed account of some of these sources and their interconnections. In particular, we explain how some of these sources played an important role in the development of Gurvits’ algorithm and in our analysis of it here.

MSC:

68W40 Analysis of algorithms
15A09 Theory of matrix inversion and generalized inverses
15A27 Commutativity of matrices
68Q25 Analysis of algorithms and problem complexity
68W20 Randomized algorithms
68W25 Approximation algorithms
68W30 Symbolic computation and algebraic computation
81P68 Quantum computation
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] B. Adsul, S. Nayak, and K. V. Subrahmanyam. A geometric approach to the Kronecker problem ii : rectangular shapes, invariants of n*n matrices, and a generalization of the Artin-Procesi theorem. Manuscript, available athttp://www.cmi.ac.in/ kv/ANS10.pdf, 2010.
[2] Alon, N., Combinatorial Nullstellensatz, Combinatorics, Probability and Computing, 8, 1-2, 7-29 (1999) · Zbl 0920.05026
[3] Amistur, SA; Levitzki, J., Minimal identities for algebras, Proceedings of the American Mathematical Society, 1, 449-463 (1950) · Zbl 0040.01101
[4] Amitsur, S., Rational identities and applications to algebra and geometry, Journal of Algebra, 3, 304-359 (1966) · Zbl 0203.04003
[5] M. D. Atkinson. Spaces of matrices with several zero eigenvalues. Bulletin of the London Mathematical Society, 12(89-95), 1980. · Zbl 0404.15004
[6] Atkinson, MD; Lloyd, S., Large spaces of matrices of bounded rank, Quarterly Journal of Math. Oxford, 31, 253-262 (1980) · Zbl 0411.15013
[7] L. B. Beasley. Nullspaces of spaces of matrices of bounded rank. Current trends in matrix theory, 1987.
[8] Berkowitz, SJ, On computing the determinant in small parallel time using a small number of processors, Information Processing Letters, 18, 3, 147-150 (1984) · Zbl 0541.68019
[9] M. Bläser, G. Jindal, and A. Pandey. Greedy strikes again: A deterministic PTAS for commutative rank of matrix spaces. In LIPIcs-Leibniz International Proceedings in Informatics, volume 79. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. · Zbl 1395.68333
[10] A. Bogdanov and H. Wee. More on noncommutative polynomial identity testing. Computational Complexity, pages 92-99, 2005.
[11] Bürgin, M.; Draisma, J., The hilbert null-cone on tuples of matrices and bilinear forms, Math Z, 254, 4, 785-809 (2006) · Zbl 1133.14044
[12] M. Choi. Completely positive linear maps on complex matrices. Linear Algebra and Its Applications, pages 285-290, 1975. · Zbl 0327.15018
[13] Cohn, PM, The embedding of firs in skew fields, Proceedings of the London Mathematical Society, 23, 193-213 (1971) · Zbl 0217.33601
[14] Cohn, PM, The word problem for free fields, The Journal of Symbolic Logic, 38, 2, 309-314 (1973) · Zbl 0273.02027
[15] Cohn, PM, The word problem for free fields: A correction and an addendum, Journal of Symbolic Logic, 40, 1, 69-74 (1975) · Zbl 0298.02044
[16] P. M. Cohn. Skew Fields, Theory of General Division Rings. Cambridge University Press, 1995. · Zbl 0840.16001
[17] Cohn, PM; Reutenauer, C., On the construction of the free field, International journal of Algebra and Computation, 9, 3, 307-323 (1999) · Zbl 1040.16015
[18] D. Cox, J. Little, and D. O’Shea. Ideals, Varieties, and Algorithms. Undergraduate Texts in Mathematics. Springer, New York, third edition edition, 2007. · Zbl 1118.13001
[19] Derksen, H., Polynomial bounds for rings of invariants, Proceedings of the American Mathematical Society, 129, 4, 955-964 (2001) · Zbl 0969.13003
[20] Derksen, H.; Kemper, G., Computational Invariant Theory (2002), Berlin: Springer-Verlag, Berlin · Zbl 1011.13003
[21] Derksen, H.; Makam, V., Polynomial degree bounds for matrix semi-invariants, Advances in Mathematics, 310, 44-63 (2017) · Zbl 1361.15033
[22] Derksen, H.; Weyman, J., Semi-invariants of quivers and saturation for Littlewood-Richardson coefficients, Journal of the American Mathematical Society, 13, 3, 467-479 (2000) · Zbl 0993.16011
[23] Dieudonné, J., Sur une généralisation du groupe orthogonal à quatre variables, Arch. Math., 1, 282-287 (1949) · Zbl 0032.10601
[24] Domokos, M.; Zubkov, AN, Semi-invariants of quivers as determinants, Transformation Groups, 6, 1, 9-24 (2001) · Zbl 0984.16023
[25] Z. Dvir and A. Shpilka. Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits. SIAM J. Comput, 2006. · Zbl 1192.94141
[26] J. Edmonds. Systems of distinct representatives and linear algebra. Journal of research of the National Bureau of Standards, 71(241-245), 1967. · Zbl 0178.03002
[27] J. Edmonds. Submodular functions, matroids, and certain polyhedra. Lectures, Calgary International Symposium on Combinatorial Structures, 1969. · Zbl 1024.90054
[28] Eisenbud, D.; Harris, J., Vector spaces of matrices of low rank, Advances in Math, 70, 135-155 (1988) · Zbl 0657.15013
[29] S. A. Fenner, R. Gurjar, and T. Thierauf. Bipartite perfect matching is in quasi-NC. STOC, 2016. · Zbl 1373.68267
[30] M. Forbes and A. Shpilka. Explicit noether normalization for simultaneous conjugation via polynomial identity testing. RANDOM, 2013. · Zbl 1407.68535
[31] M. Forbes and A. Shpilka. Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs. FOCS, pages 243-252, 2013.
[32] E. Formanek. Generating the ring of matrix invariants. Ring Theory, pages 73-82, 1986. · Zbl 0602.16017
[33] M. Fortin and C. Reutenauer. Commutative/noncommutative rank of linear matrices and subspaces of matrices of low rank. 2004. · Zbl 1069.15011
[34] Garg, A.; Gurvits, L.; Oliveira, R.; Wigderson, A., Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling, Geometric and Functional Analysis, 28, 1, 100-145 (2018) · Zbl 1387.68133
[35] Gelbord, B.; Meshulam, R., Spaces of singular matrices and matroid parity, European Journal of Combinatorics, 23, 4, 389-397 (2002) · Zbl 1007.05039
[36] I. Gelfand, S. Gelfand, V. Retakh, and R. Wilson. Quasideterminants. arXiv:math/0208146, 2002.
[37] Gurvits, L., Classical complexity and quantum entanglement, Journal of Computer and System Sciences, 69, 3, 448-484 (2004) · Zbl 1093.81012
[38] L. Gurvits. Hyperbolic polynomials approach to Van der Waerden/Schrijver-Valiant like conjectures: sharper bounds, simpler proofs and algorithmic applications. STOC, pages 417-426, 2006. · Zbl 1301.90071
[39] L. Gurvits and A. Samorodnitsky. A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume. STOC, 2000. · Zbl 1296.68068
[40] L. Gurvits and A. Samorodnitsky. A deterministic algorithm approximating the mixed discriminant and mixed volume, and a combinatorial corollary. Discrete Computational Geometry, 27(531-550), 2002. · Zbl 1008.68145
[41] L. Gurvits and P. N. Yianilos. The deflation-inflation method for certain semidefinite programming and maximum determinant completion problems. Technical Report, NECI, 1998.
[42] Haken, W., Theorie der Normalflächen, Acta Math, 105, 245-375 (1961) · Zbl 0100.19402
[43] G. Higman. Units in group rings. PhD thesis, Balliol College, 1940. · Zbl 0025.24302
[44] Hilbert, D., Uber die vollen Invariantensysteme, Math. Ann., 42, 313-370 (1893) · JFM 25.0173.01
[45] P. Hrubes and A. Wigderson. Non-commutative arithmetic circuits with division. ITCS, 2014. · Zbl 1364.68200
[46] P. Hrubes, A. Wigderson, and A. Yehudayoff. Relationless completeness and separations. In Computational Complexity (CCC), 2010 IEEE 25th Annual Conference on, pages 280-290. IEEE, 2010.
[47] Hrubes, P.; Wigderson, A.; Yehudayoff, A., Non-commutative circuits and the sum-of-squares problem, Journal of the American Mathematical Society, 24, 3, 871-898 (2011) · Zbl 1225.03049
[48] Hua, L-K, Some properties of a sfield, Proceedings of National Academy of Sciences USA, 35, 533-537 (1949) · Zbl 0035.02001
[49] Hyafil, L., On the parallel evaluation of multivariate polynomials, SIAM Journal on Computing, 8, 2, 120-123 (1979) · Zbl 0408.68041
[50] Ivanyos, G.; Karpinski, M.; Qiao, Y.; Santha, M., Generalized Wong sequences and their applications to Edmonds’ problems, Journal of Computer and System Sciences, 81, 7, 1373-1386 (2015) · Zbl 1320.68222
[51] Ivanyos, G.; Qiao, Y.; Subrahmanyam, K., Non-commutative Edmonds’ problem and matrix semi-invariants, Computational Complexity, 26, 3, 717-763 (2017) · Zbl 1421.13002
[52] Ivanyos, G.; Qiao, Y.; Subrahmanyam, KV, Constructive noncommutative rank computation in deterministic polynomial time over fields of arbitrary characteristics, Computational Complexity, 27, 4, 561-593 (2018) · Zbl 1402.68197
[53] Kabanets, V.; Impagliazzo, R., Derandomizing polynomial identity tests means proving circuit lower bounds, Computational Complexity, 13, 1-46 (2004) · Zbl 1089.68042
[54] Kaliuzhnyi-Verbovetskyi, DS; Vinnikov, V., Noncommutative rational functions, their difference-differential calculus and realizations, Multidimensional Systems and Signal Processing, 23, 1-2, 49-77 (2010) · Zbl 1255.93073
[55] N. Kayal and N. Saxena. Polynomial identity testing for depth 3 circuits. Computational Complexity, 2007. · Zbl 1173.94470
[56] King, AD, Moduli of representations of finite dimensional algebras, The Quarterly Journal of Mathematics, 45, 4, 515-530 (1994) · Zbl 0837.16005
[57] A. Klivans and D. Spielman. Randomness efficient identity testing of multivariate polynomials. In Proceedings of the 33rd Annual STOC, 2001. · Zbl 1323.68563
[58] H. Kraft and C. Procesi. Classical invariant theory, a primer. https://math.unibas.ch/uploads/x4epersdb/files/primernew.pdf, 1996.
[59] N. Limaye, G. Malod, and S. Srinivasan. Lower bounds for non-commutative skew circuits. In Electronic Colloquium on Computational Complexity (ECCC), volume 22, page 22, 2015. · Zbl 1393.68063
[60] N. Linial, A. Samorodnitsky, and A. Wigderson. A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents. STOC, pages 644-652, 1998. · Zbl 1027.68980
[61] L. Lovasz. On determinants, matchings, and random algorithms. Fundamentals of Computation Theory, pages 565-574, 1979. · Zbl 0446.68036
[62] L. Lovasz. Selecting independent lines from a family of lines in a space. Acta Sci. Math., 42(121-131), 1980. · Zbl 0449.51008
[63] Lovasz, L., Singular spaces of matrices and their application in combinatorics, Bulletin of the Brazilian Mathematical Society, 20, 87-99 (1989) · Zbl 0757.05035
[64] P. Malcolmson. A prime matrix ideal yields a skew field. Journal of the London Mathematical Society, 18(221-233), 1978. · Zbl 0406.16013
[65] K. Mulmuley. Geometric complexity theory V: Equivalence between blackbox derandomization of polynomial identity testing and derandomization of noether’s normalization lemma. FOCS, pages 629-638, 2012.
[66] N. Nisan. Lower bounds for non-commutative computation. In Proceedings of the twenty-third annual ACM symposium on Theory of computing, pages 410-418. ACM, 1991.
[67] Popov, VL, The constructive theory of invariants, Izvestiya: Mathematics, 19, 2, 359-376 (1982) · Zbl 0501.14006
[68] Procesi, C., The invariant theory of nn matrices, Advances in Mathematics, 19, 306-381 (1976) · Zbl 0331.15021
[69] M. O. Rabin. Recursive unsolvability of group theoretic problems. Annals of Mathematics, 67(172-194), 1958. · Zbl 0079.24802
[70] Rado, R., A theorem on independence relations, Quarterly Journal of Math. Oxford, 13, 83-89 (1942) · Zbl 0063.06369
[71] Raz, R.; Shpilka, A., Deterministic polynomial identity testing in non commutative models, Computational Complexity, 14, 1-19 (2005) · Zbl 1096.68070
[72] Razmyslov, JP, Trace identities of full matrix algebras over a field of characteristic zero, Mathematics of the USSR-Izvestiya, 8, 4, 727 (1974) · Zbl 0311.16016
[73] Reutenauer, C., Inversion height in free fields, Selecta Mathematica, 2, 1, 93-109 (1996) · Zbl 0857.16021
[74] Rowen, LH, Polynomial identities in ring theory (1980), New York: Academic Press, New York · Zbl 0461.16001
[75] S. Saraf and I. Volkovich. Black-box identity testing of depth 4 multilinear circuits. In Proceedings of the 43rd annual STOC, 2011. · Zbl 1288.68137
[76] Schofield, A.; den Bergh, MV, Semi-invariants of quivers for arbitrary dimension vectors, Indagationes Mathematicae, 12, 1, 125-138 (2001) · Zbl 1004.16012
[77] A. Shpilka and A. Yehudayoff. Arithmetic Circuits: A Survey of Recent Results and Open Questions, volume 5. NOW, Foundations and Trends in Theoretical Computer Science, 2010. · Zbl 1205.68175
[78] Sinkhorn, R., A relationship between arbitrary positive matrices and doubly stochastic matrices, The Annals of Mathematical Statistics, 35, 876-879 (1964) · Zbl 0134.25302
[79] Strassen, V., Vermeidung von Divisionen, Journal für Reine Angew. Math, 264, 182-202 (1973) · Zbl 0294.65021
[80] Valiant, L., The complexity of computing the permanent, Theoretical Computer Science, 8, 189-201 (1979) · Zbl 0415.68008
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.