Non-commutative Edmonds’ problem and matrix semi-invariants. (English) Zbl 1421.13002
The non-commutative rank of an \(n\times n\) matrix \(T\) of linear forms (in \(m\) indeterminates) over a field \(\mathbb{F}\) is the rank of \(T\) over the free skew-field (generated by the \(m\) indeterminates). The non-commutative Edmonds’ problem asks for computing the non-commutative rank of \(T\). Note that \(T\) is given by an \(m\)-tuple of \(n\times n\) matrices over \(\mathbb{F}\). The non-commutative Edmonds’ problem is closely related to the study of the ring of matrix semi-invariants (i.e. the ring of invariants of \(\mathrm{SL}(n,\mathbb{F})\times\mathrm{SL}(n,\mathbb{F})\) acting via left and right multiplication) on \(m\)-tuples of \(n\times n\) matrices over \(\mathbb{F}\). Denote by \(\sigma\) the minimal positive integer such that the nullcone for the above action is cut out by semi-invariants of degree at most \(\sigma\). The main results of the present paper are the following:
(1) For \(\mathbb{F}=\mathbb{Q}\) there exists a deterministic algorithm to decide wether the non-commutative rank is smaller than \(n\) in time polynomial in the input size and \(\sigma\).
(2) For \(\mathbb{F}\) large enough an algorithm is devised for the non-commutative Edmonds’ problem which runs in time polynomial in \((n+1)!\).
(3) Improving upon a result of M. Fortin and C. Reutenauer [Sémin. Lothar. Comb. 52, B52f, 12 p. (2004; Zbl 1069.15011)], the authors show a randomized efficient algorithm to compute the non-commutative rank of \(T\) under the assumption that its difference from the commutative rank is bounded by a constant.
(4) For \(\mathbb{F}\) large enough the inequality \(\sigma\leq (n+1)!\) is proved.
Along the way the authors discover a fact of independent interest as follows. For a subspace \(\mathcal{B}\) of the space \(M(n,\mathbb{F})\) of \(n\times n\) matrices and a positive integer \(d\), the \(d^{\mathrm{th}}\) tensor blow-up of \(\mathcal{B}\) is defined as \(\mathcal{B}^{(d)}=M(d,\mathbb{F})\otimes \mathcal{B}\), viewed as a subspace of \(M(dn,\mathbb{F})\). It is shown that the maximal possible rank of an element in \(\mathcal{B}^{(d)}\) is divisible by \(d\). The proof uses basic results on division rings.
We mention finally that the paper gives a thorough description of various formulations of the non-commutative Edmonds’ problem and the related literature.
(1) For \(\mathbb{F}=\mathbb{Q}\) there exists a deterministic algorithm to decide wether the non-commutative rank is smaller than \(n\) in time polynomial in the input size and \(\sigma\).
(2) For \(\mathbb{F}\) large enough an algorithm is devised for the non-commutative Edmonds’ problem which runs in time polynomial in \((n+1)!\).
(3) Improving upon a result of M. Fortin and C. Reutenauer [Sémin. Lothar. Comb. 52, B52f, 12 p. (2004; Zbl 1069.15011)], the authors show a randomized efficient algorithm to compute the non-commutative rank of \(T\) under the assumption that its difference from the commutative rank is bounded by a constant.
(4) For \(\mathbb{F}\) large enough the inequality \(\sigma\leq (n+1)!\) is proved.
Along the way the authors discover a fact of independent interest as follows. For a subspace \(\mathcal{B}\) of the space \(M(n,\mathbb{F})\) of \(n\times n\) matrices and a positive integer \(d\), the \(d^{\mathrm{th}}\) tensor blow-up of \(\mathcal{B}\) is defined as \(\mathcal{B}^{(d)}=M(d,\mathbb{F})\otimes \mathcal{B}\), viewed as a subspace of \(M(dn,\mathbb{F})\). It is shown that the maximal possible rank of an element in \(\mathcal{B}^{(d)}\) is divisible by \(d\). The proof uses basic results on division rings.
We mention finally that the paper gives a thorough description of various formulations of the non-commutative Edmonds’ problem and the related literature.
Reviewer: Matyas Domokos (Budapest)
MSC:
| 13A50 | Actions of groups on commutative rings; invariant theory |
| 68W30 | Symbolic computation and algebraic computation |
| 15A27 | Commutativity of matrices |
| 15A72 | Vector and tensor algebra, theory of invariants |
| 16K20 | Finite-dimensional division rings |
Keywords:
Edmonds’ problem; symbolic determinant identity test; semi-invariants of quivers; non-commutative rank; cyclic division algebras; Wong sequencesCitations:
Zbl 1069.15011References:
| [1] | B. Adsul, S. Nayak & K. V. Subrahmanyam (2007). A geometric approach to the Kronecker problem II: rectangular shapes, invariants of matrices and the Artin-Procesi theorem. Preprint. · Zbl 0883.17001 |
| [2] | Adsul Bharat, Subrahmanyam K.V. (2008) A geometric approach to the Kronecker problem I: the two row case. Proceedings Mathematical Sciences 118(2): 213-226 · Zbl 1147.20010 · doi:10.1007/s12044-008-0014-8 |
| [3] | S.A Amitsur (1966). Rational identities and applications to algebra and geometry. Journal of Algebra3(3), 304 - 359. ISSN 0021-8693. URL http://www.sciencedirect.com/science/article/pii/0021869366900044. · Zbl 0203.04003 |
| [4] | MD Atkinson & S Lloyd (1981). Primitive spaces of matrices of bounded rank. Journal of the Australian Mathematical Society (Series A)30(04), 473-482. · Zbl 0473.15007 |
| [5] | George W. Bergman (1969-1970). Skew fields of noncommutative rational functions (preliminary version). Séminaire Schützenberger1, 1-18. URL http://eudml.org/doc/112813. |
| [6] | Peter A. Brooksbank, Eugene M. Luks (2008) Testing isomorphism of modules. Journal of Algebra 320(11): 4020-4029 · Zbl 1172.16022 · doi:10.1016/j.jalgebra.2008.07.014 |
| [7] | Bürgin M., Draisma J. (2006) The Hilbert null-cone on tuples of matrices and bilinear forms. Mathematische Zeitschrift 254(4): 785-809 · Zbl 1133.14044 · doi:10.1007/s00209-006-0008-0 |
| [8] | Peter Bürgisser, J. M. Landsberg, Laurent Manivel & Jerzy Weyman (2011). An Overview of Mathematical Issues Arising in the Geometric Complexity Theory Approach to \[{VP \neq VNP}\] VP≠VNP. SIAM J. Comput.40(4), 1179-1209. doi:10.1137/090765328. · Zbl 1252.68134 |
| [9] | Buss Jonathan F., Frandsen Gudmund S., Shallit Jeffrey O. (1999) The computational complexity of some problems of linear algebra. J. Comput. Syst. Sci. 58(3): 572-596 · Zbl 0941.68059 · doi:10.1006/jcss.1998.1608 |
| [10] | Marco Carmosino, Russell Impagliazzo, Valentine Kabanets & Antonina Kolokolova (2015). Tighter Connections between Derandomization and Circuit Lower Bounds. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2015, August 24-26, 2015, Princeton, NJ, USA, 645-658. doi:10.4230/LIPIcs.APPROX-RANDOM.2015.645. · Zbl 1375.68209 |
| [11] | Alexander L. Chistov, Gábor Ivanyos & Marek Karpinski (1997). Polynomial Time Algorithms for Modules over Finite Dimensional Algebras. In Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, ISSAC ’97, Maui, Hawaii, USA, July 21-23, 1997, 68-74. · Zbl 0918.16001 |
| [12] | Ajeh M Cohen, Gábor Ivanyos & David B Wales (1997). Finding the radical of an algebra of linear transformations. Journal of Pure and Applied Algebra117, 177-193. · Zbl 0876.16009 |
| [13] | P. M. Cohn (1973). The Word Problem for Free Fields. J. Symbolic Logic38(2), 309-314. URL http://projecteuclid.org/euclid.jsl/1183738636. · Zbl 0273.02027 |
| [14] | P. M. Cohn (1975). The Word Problem for Free Fields: A Correction and an Addendum. J. Symbolic Logic40(1), 69-74. URL http://projecteuclid.org/euclid.jsl/1183739310. · Zbl 0298.02044 |
| [15] | P. M. Cohn (1985). Free Rings and Their Relations. L.M.S. Monographs. Acad. Press. ISBN 9780121791506. URL http://books.google.com.au/books?id=R3KmAAAAIAAJ. First edition 1971. · Zbl 0232.16003 |
| [16] | P. M. Cohn (1995). Skew Fields: Theory of General Division Rings. Encyclopedia of Mathematics and its Applications. Cambridge University Press. ISBN 9780521432177. URL http://books.google.com.au/books?id=u-4ADgUgpSMC. · Zbl 1147.20010 |
| [17] | Cohn P.M., Reutenauer C. (1999) On the construction of the free field. International Journal of Algebra and Computation 9(3-4): 307-323 · Zbl 1040.16015 · doi:10.1142/S0218196799000205 |
| [18] | Harm Derksen (2001) Polynomial bounds for rings of invariants. Proceedings of the American Mathematical Society 129(4): 955-964 · Zbl 0969.13003 · doi:10.1090/S0002-9939-00-05698-7 |
| [19] | Harm Derksen & Visu Makam (2015). Polynomial degree bounds for matrix semi-invariants. Preprint arXiv:1512.03393. · Zbl 1361.15033 |
| [20] | Derksen Harm, Weyman Jerzy (2000) Semi-invariants of quivers and saturation for Littlewood-Richardson coefficients. Journal of the American Mathematical Society 13(3): 467-479 · Zbl 0993.16011 · doi:10.1090/S0894-0347-00-00331-3 |
| [21] | M. Domokos, (2000a). Poincaré series of semi-invariants of \[2{\times}\]× 2 matrices. Linear Algebra and its Applications310(1), 183-194. · Zbl 0984.16022 |
| [22] | M. Domokos (2000b). Relative invariants of 3 × 3 matrix triples. Linear and Multilinear Algebra47(2), 175-190. · Zbl 0967.13005 |
| [23] | Domokos M. (2002) Finite generating system of matrix invariants. Math. Pannon 13(2): 175-181 · Zbl 1007.16017 |
| [24] | Domokos M., Drensky V. (2012) Defining relation for semi-invariants of three by three matrix triples. Journal of Pure and Applied Algebra 216(10): 2098-2105 · Zbl 1260.13010 · doi:10.1016/j.jpaa.2012.01.017 |
| [25] | Domokos M., Kuzmin S.G., Zubkov A.N. (2002) Rings of matrix invariants in positive characteristic. Journal of Pure and Applied Algebra 176(1): 61-80 · Zbl 1024.16014 · doi:10.1016/S0022-4049(02)00117-2 |
| [26] | Domokos M., Zubkov A.N. (2001) Semi-invariants of quivers as determinants. Transformation groups 6(1): 9-24 · Zbl 0984.16023 · doi:10.1007/BF01236060 |
| [27] | Donkin Stephen (1992) Invariants of several matrices. Inventiones mathematicae 110(1): 389-401 · Zbl 0826.20036 · doi:10.1007/BF01231338 |
| [28] | Stephen Donkin (1993). Invariant functions on matrices. Mathematical Proceedings of the Cambridge Philosophical Society113, 23-43. ISSN 1469-8064. URL http://journals.cambridge.org/article_S0305004100075757. · Zbl 0826.20015 |
| [29] | Edmonds Jack (1967) Systems of distinct representatives and linear algebra. J. Res. Nat. Bur. Standards Sect. B 71: 241-245 · Zbl 0178.03002 · doi:10.6028/jres.071B.033 |
| [30] | David Eisenbud & Joe Harris (1988). Vector spaces of matrices of low rank. Advances in Mathematics70(2), 135 - 155. ISSN 0001-8708. URL http://www.sciencedirect.com/science/article/pii/0001870888900540. · Zbl 0657.15013 |
| [31] | Edward Formanek (1986). Generating the ring of matrix invariants. In Ring Theory, Freddy M. J. van Oystaeyen, editor, volume 1197 of Lecture Notes in Mathematics, 73-82. Springer Berlin Heidelberg. ISBN 978-3-540-16496-8. doi:10.1007/BFb0076314. · Zbl 0602.16017 |
| [32] | M. Fortin & C. Reutenauer (2004). Commutative/Noncommutative Rank of Linear Matrices and Subspaces of Matrices of Low Rank. Séminaire Lotharingien de Combinatoire52, B52f. · Zbl 1069.15011 |
| [33] | Ankit Garg, Leonid Gurvits, Rafael Oliveira & Avi Wigderson (2015). A deterministic polynomial time algorithm for non-commutative rational identity testing. Preprint arXiv:1511.03730. |
| [34] | Geelen James, Satoru Iwata (2005) Matroid matching via mixed skew-symmetric matrices. Combinatorica 25(2): 187-215 · Zbl 1102.05048 · doi:10.1007/s00493-005-0013-7 |
| [35] | Geelen James F. (1999) Maximum rank matrix completion. Linear Algebra and its Applications 288: 211-217 · Zbl 0933.15026 · doi:10.1016/S0024-3795(98)10210-0 |
| [36] | James F Geelen (2000). An algebraic matching algorithm. Combinatorica20(1), 61-70 · Zbl 0949.05062 |
| [37] | Geelen James F., Iwata Satoru, Murota Kazuo (2003) The linear delta-matroid parity problem. Journal of Combinatorial Theory, Series B 88(2): 377-398 · Zbl 1021.05019 · doi:10.1016/S0095-8956(03)00039-X |
| [38] | de Graaf Willem A., Ivanyos Gábor, Rónyai Lajos (1996) Computing Cartan subalgebras of Lie algebras. Applicable Algebra in Engineering, Communication and Computing 7(5): 339-349 · Zbl 0883.17001 · doi:10.1007/BF01293593 |
| [39] | Gurvits Leonid (2004) Classical complexity and quantum entanglement. J. Comput. Syst. Sci. 69(3): 448-484 · Zbl 1093.81012 · doi:10.1016/j.jcss.2004.06.003 |
| [40] | Leonid Gurvits & Peter N. Yianilos (1998). The Deflation-Inflation Method for Certain Semidefinite Programming and Maximum Determinant Completion Problems (Extended Abstract). Technical report, NECI. · Zbl 1021.05019 |
| [41] | Nicholas J. A. Harvey, David R. Karger & Kazuo Murota (2005). Deterministic network coding by matrix completion. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005, 489-498. URL http://dl.acm.org/citation.cfm?id=1070432.1070499. · Zbl 1297.68022 |
| [42] | D. Hilbert (1893). Uber die vollen Invariantensysteme. Math. Ann. (42), 313-370 · JFM 25.0173.01 |
| [43] | Pavel Hrubeš & Avi Wigderson (2015). Non-Commutative Arithmetic Circuits with Division. Theory of Computing11, 357-393. doi:10.4086/toc.2015.v011a014. · Zbl 1403.94130 |
| [44] | Gábor Ivanyos, Marek Karpinski, Youming Qiao & Miklos Santha (2015a). Generalized Wong sequences and their applications to Edmonds’ problems. J. Comput. Syst. Sci. 81(7), 1373-1386. doi:10.1016/j.jcss.2015.04.006. · Zbl 1320.68222 |
| [45] | Ivanyos Gábor, Karpinski Marek, Saxena Nitin (2010) Deterministic Polynomial Time Algorithms for Matrix Completion Problems. SIAM J. Comput. 39(8): 3736-3751 · Zbl 1209.68269 · doi:10.1137/090781231 |
| [46] | Gábor Ivanyos, Youming Qiao & K. V. Subrahmanyam (2015b). Constructive noncommutative rank computation in deterministic polynomial time over fields of arbitrary characteristics. CoRRabs/1512.03531. · Zbl 1402.68198 |
| [47] | Gábor Ivanyos, Youming Qiao & K. V. Subrahmanyam (2015c). On generating the ring of matrix semi-invariants. CoRRabs/1508.01554 . · Zbl 1421.13002 |
| [48] | Kabanets Valentine, Impagliazzo Russell. (2004) Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds. Computational Complexity 13(1-2): 1-46 · Zbl 1089.68042 · doi:10.1007/s00037-004-0182-6 |
| [49] | Erich Kaltofen (1992). On Computing Determinants of Matrices without Divisions. In Proceedings of the 1992 International Symposium on Symbolic and Algebraic Computation, ISSAC ’92, Berkeley, CA, USA, July 27-29, 1992, 342-349. doi:10.1145/143242.143350. · Zbl 0978.65502 |
| [50] | T.Y. Lam (1991). A First Course in Noncommutative Rings. Graduate Texts in Mathematics. Springer. · Zbl 0728.16001 |
| [51] | Nathan Linial, Alex Samorodnitsky & Avi Wigderson (2000). A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents. Combinatorica20(4), 545-568. doi:10.1007/s004930070007. · Zbl 0973.15004 |
| [52] | Lovász László (1989) Singular spaces of matrices and their application in combinatorics. Boletim da Sociedade Brasileira de Matemática-Bulletin/Brazilian Mathematical Society 20(1): 87-99 · Zbl 0757.05035 · doi:10.1007/BF02585470 |
| [53] | Meena Mahajan & V. Vinay (1997). Determinant: Combinatorics, Algorithms, and Complexity. Chicago Journal of Theoretical Computer Science1997(5). · Zbl 0924.68088 |
| [54] | Peter Malcolmson (1978). A Prime Matrix Ideal Yields a Skew Field. Journal of the London Mathematical Societys2-18(2), 221-233. URL http://jlms.oxfordjournals.org/content/s2-18/2/221.short. · Zbl 0406.16013 |
| [55] | Laurent Manivel (2010). A note on certain Kronecker coefficients. Proceedings of the American Mathematical Society138(1), 1-7 · Zbl 1193.20010 |
| [56] | Ketan Mulmuley (1987). A fast parallel algorithm to compute the rank of a matrix over an arbitrary field. Combinatorica7(1), 101-104. doi:10.1007/BF02579205. · Zbl 0635.65040 |
| [57] | Ketan Mulmuley (2011). On P vs. NP and geometric complexity theory: Dedicated to Sri Ramakrishna. J. ACM58(2), 5. doi:10.1145/1944345.1944346. · Zbl 1327.68111 |
| [58] | Ketan Mulmuley (2012). Geometric Complexity Theory V: Equivalence between Blackbox Derandomization of Polynomial Identity Testing and Derandomization of Noether’s Normalization Lemma. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, 629-638. 10.1109/FOCS.2012.15. · Zbl 1102.05048 |
| [59] | Ketan Mulmuley & Milind A. Sohoni (2001). Geometric Complexity Theory I: An Approach to the P vs. NP and Related Problems. SIAM J. Comput.31(2), 496-526. doi:10.1137/S009753970038715X. · Zbl 0992.03048 |
| [60] | Ketan Mulmuley & Milind A. Sohoni (2008). Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties. SIAM J. Comput. 38(3), 1175-1206. 10.1137/080718115. · Zbl 1168.03030 |
| [61] | Kazuo Murota (2000). Matrices and matroids for systems analysis. Springer. · Zbl 0948.05001 |
| [62] | Vladimir L Popov (1982). The constructive theory of invariants. Izvestiya: Mathematics 19(2), 359-376 · Zbl 0501.14006 |
| [63] | Procesi C. (1976) The invariant theory of n × n matrices. Advances in Mathematics 19(3): 306-381 · Zbl 0331.15021 · doi:10.1016/0001-8708(76)90027-X |
| [64] | Ju. P. Razmyslov (1974). Trace identities of full matrix algebras over a field of characteristic zero. Mathematics of the USSR-Izvestiya8(4), 727. English translation available at http://iopscience.iop.org/0025-5726/8/4/A01. · Zbl 0311.16016 |
| [65] | T. G. Room (1938). The Geometry of Determinantal Loci. The Cambridge University Press. URL http://books.google.com.au/books?id=-kZtAAAAMAAJ. · Zbl 0020.05402 |
| [66] | Aidan Schofield & Michel Van den Bergh (2001). Semi-invariants of quivers for arbitrary dimension vectors. Indagationes Mathematicae12(1), 125-138. · Zbl 1004.16012 |
| [67] | Tutte W.T. (1947) The factorization of linear graphs. Journal of the London Mathematical Society 1(2): 107-111 · Zbl 0029.23301 · doi:10.1112/jlms/s1-22.2.107 |
| [68] | E. Witt (1937). Zyklische Körper und Algebren der Charakteristik p vom Grad pn. Struktur diskret bewerteter perfekter Körper mit vollkommenem Restklassenkörper der Charakteristik p. J. Reine Angew. Math176(01), 126-140. · JFM 62.1112.03 |
| [69] | Kai-Tak Wong (1974). The eigenvalue problem λ Tx + Sx. Journal of Differential Equations16(2), 270 - 280. ISSN 0022-0396. URL http://www.sciencedirect.com/science/article/pii/002203967490014X. · Zbl 0327.15015 |
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.
