Singular tuples of matrices is not a null cone (and the symmetries of algebraic varieties). (English) Zbl 1476.14081
The authors define \(\text{SING}_{n,m}\) to be all \(m\)-tuples of \(n\times n\) complex matrices spanning only singular matrices. \(\text{SING}_{n,m}\) plays a central role in algebra, algebraic geometry, and computational complexity theory. There are algorithms for memberships in a general class of algebraic varieties called the null cones of linear group actions. However, such algorithms cannot be used for \(\text{SING}_{n,m}\) since it is not the null cone of any reductive group action (Theorem 1.9, page 85).
To prove this, the authors identify the group of symmetries of \(\text{SING}_{n,m}\) (Theorem 1.12, page 85). Their work generalizes a result of Frobenius for the case when \(m=1\), and suggests a more general method to determine the symmetries of algebraic varieties.
To prove this, the authors identify the group of symmetries of \(\text{SING}_{n,m}\) (Theorem 1.12, page 85). Their work generalizes a result of Frobenius for the case when \(m=1\), and suggests a more general method to determine the symmetries of algebraic varieties.
Reviewer: Mee Seong Im (Annapolis)
MSC:
| 14L24 | Geometric invariant theory |
| 14Q20 | Effectivity, complexity and computational aspects of algebraic geometry |
| 15A86 | Linear preserver problems |
| 17B45 | Lie algebras of linear algebraic groups |
| 16G20 | Representations of quivers and partially ordered sets |
| 68Q25 | Analysis of algorithms and problem complexity |
| 15A30 | Algebraic systems of matrices |
| 13A50 | Actions of groups on commutative rings; invariant theory |
| 15A72 | Vector and tensor algebra, theory of invariants |
Keywords:
invariant theory; null cone; orbit closure; multi-determinantal algebraic varieties; algebraic varieties; singular matrices; vanishing idealReferences:
| [1] | Z. Allen-Zhu, A. Garg, Y. Li, R. Oliveira and A. Wigderson, Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing, STOC’18—Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York (2018), 172-181. · Zbl 1427.90213 |
| [2] | S. A. Amitsur, Rational identities and applications to algebra and geometry, J. Algebra 3 (1966), 304-359.83] · Zbl 0203.04003 |
| [3] | P. Bürgisser, C. Franks, A. Garg, R. Oliveira, M. Walter and A. Wigderson, Efficient algorithms for tensor scaling, quantum marginals, and moment polytopes, 59th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2018, IEEE Computer Society, Los Alamitos (2018), 883-897. |
| [4] | P. Bürgisser, A. Garg, R. Oliveira, M. Walter and A. Wigderson, Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory, 9th Innovations in Theoretical Computer Science, LIPIcs. Leibniz Int. Proc. Inform. 94, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Wadern (2018), Article No. 24. · Zbl 1462.90097 |
| [5] | P. Bürgisser, M. Levent Doğan, V. Makam, M. Walter and A. Wigderson, Polynomial time algorithms in invariant theory for torus actions, preprint (2021), https://arxiv.org/abs/2102.07727. |
| [6] | P. M. Cohn, Skew fields. Theory of general division rings, Encyclopedia Math. Appl. 57, Cambridge University, Cambridge 1995. · Zbl 0840.16001 |
| [7] | H. Derksen and G. Kemper, Computational invariant theory, Encyclopaedia Math. Sci. 130, Springer, Heidelberg 2015. · Zbl 1332.13001 |
| [8] | H. Derksen and V. Makam, Generating invariant rings of quivers in arbitrary characteristic, J. Algebra 489 (2017), 435-445. · Zbl 1393.16008 |
| [9] | H. Derksen and V. Makam, Polynomial degree bounds for matrix semi-invariants, Adv. Math. 310 (2017), 44-63. · Zbl 1361.15033 |
| [10] | H. Derksen and V. Makam, Degree bounds for semi-invariant rings of quivers, J. Pure Appl. Algebra 222 (2018), no. 10, 3282-3292. · Zbl 1410.16020 |
| [11] | H. Derksen and V. Makam, On non-commutative rank and tensor rank, Linear Multilinear Algebra 66 (2018), no. 6, 1069-1084. · Zbl 1392.15034 |
| [12] | H. Derksen and V. Makam, Explicit tensors of border rank at least \(2d-2\) in \(K^d\otimes K^d\otimes K^d\) in arbitrary characteristic, Linear Multilinear Algebra 67 (2019), no. 10, 2104-2116. · Zbl 1425.15023 |
| [13] | H. Derksen and V. Makam, Algorithms for orbit closure separation for invariants and semi-invariants of matrices, Algebra Number Theory 14 (2020), no. 10, 2791-2813. · Zbl 1460.13011 |
| [14] | H. Derksen and J. Weyman, Semi-invariants of quivers and saturation for Littlewood-Richardson coefficients, J. Amer. Math. Soc. 13 (2000), no. 3, 467-479. · Zbl 0993.16011 |
| [15] | J. Dieudonné, Sur une généralisation du groupe orthogonal à quatre variables, Arch. Math. 1 (1949), 282-287. · Zbl 0032.10601 |
| [16] | D. Ž. Doković and C.-K. Li, Overgroups of some classical linear groups with applications to linear preserver problems, Linear Algebra Appl. 197/198 (1994), 31-61. · Zbl 0793.15018 |
| [17] | M. Domokos and A. N. Zubkov, Semi-invariants of quivers as determinants, Transform. Groups 6 (2001), no. 1, 9-24. · Zbl 0984.16023 |
| [18] | E. B. Dynkin, Maximal subgroups of the classical groups, Trudy Moskov. Mat. Obšč. 1 (1952), 39-166. · Zbl 0048.01601 |
| [19] | J. Edmonds, Systems of distinct representatives and linear algebra, J. Res. Nat. Bur. Standards Sect. B 71 (1967), no. 4, 241-245. · Zbl 0178.03002 |
| [20] | D. Eisenbud and J. Harris, Vector spaces of matrices of low rank, Adv. Math. 70 (1988), no. 2, 135-155. · Zbl 0657.15013 |
| [21] | M. A. Forbes and A. Shpilka, Explicit Noether normalization for simultaneous conjugation via polynomial identity testing, Approximation, randomization, and combinatorial optimization, Lecture Notes in Comput. Sci. 8096, Springer, Heidelberg (2013), 527-542. · Zbl 1407.68535 |
| [22] | M. Fortin and C. Reutenauer, Commutative/noncommutative rank of linear matrices and subspaces of matrices of low rank, Sém. Lothar. Combin. 52 (2004/07), Article ID B52f. · Zbl 1069.15011 |
| [23] | C. Franks, Operator scaling with specified marginals, STOC’18—Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York (2018), 190-203. · Zbl 1428.47004 |
| [24] | G. Frobenius, Über die Darstellung der endlichen Gruppen durch linear Substitutionen, Akad. Wiss. Berlin (1987), 994-1015. · JFM 28.0130.01 |
| [25] | W. Fulton, Young tableaux, London Math. Soc. Stud. Texts 35, Cambridge University, Cambridge 1997. · Zbl 0878.14034 |
| [26] | A. Garg, L. Gurvits, R. Oliveira and A. Wigderson, A deterministic polynomial time algorithm for non-commutative rational identity testing, 57th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2016, IEEE Computer Society, Los Alamitos (2016), 109-117. |
| [27] | A. Garg, L. Gurvits, R. Oliveira and A. Wigderson, Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling, Geom. Funct. Anal. 28 (2018), no. 1, 100-145. · Zbl 1387.68133 |
| [28] | B. Gelbord and R. Meshulam, Spaces of singular matrices and matroid parity, European J. Combin. 23 (2002), no. 4, 389-397. · Zbl 1007.05039 |
| [29] | R. M. Guralnick, Invertible preservers and algebraic groups, Linear Algebra Appl. 212/213 (1994), 249-257. · Zbl 0814.15002 |
| [30] | L. Gurvits, Classical complexity and quantum entanglement, J. Comput. System Sci. 69 (2004), no. 3, 448-484. · Zbl 1093.81012 |
| [31] | D. Happel, Relative invariants and subgeneric orbits of quivers of finite and tame type, J. Algebra 78 (1982), no. 2, 445-459. · Zbl 0494.16015 |
| [32] | D. Happel, Relative invariants of quivers of tame type, J. Algebra 86 (1984), no. 2, 315-335. · Zbl 0526.16020 |
| [33] | G. Ivanyos, Y. Qiao and K. V. Subrahmanyam, Non-commutative Edmonds’ problem and matrix semi-invariants, Comput. Complexity 26 (2017), no. 3, 717-763. · Zbl 1421.13002 |
| [34] | G. Ivanyos, Y. Qiao and K. V. Subrahmanyam, Constructive non-commutative rank computation is in deterministic polynomial time, Comput. Complexity 27 (2018), no. 4, 561-593. · Zbl 1402.68197 |
| [35] | V. Kabanets and R. Impagliazzo, Derandomizing polynomial identity tests means proving circuit lower bounds, Comput. Complexity 13 (2004), no. 1-2, 1-46. · Zbl 1089.68042 |
| [36] | J. M. Landsberg, Geometry and complexity theory, Cambridge Stud. Adv. Math. 169, Cambridge University, Cambridge 2017. · Zbl 1387.68002 |
| [37] | J. M. Landsberg and M. Michałek, Abelian tensors, J. Math. Pures Appl. (9) 108 (2017), no. 3, 333-371. · Zbl 1386.14191 |
| [38] | C.-K. Li and S. Pierce, Linear preserver problems, Amer. Math. Monthly 108 (2001), no. 7, 591-605. · Zbl 0991.15001 |
| [39] | L. Lovász, On determinants, matchings, and random algorithms, Fundamentals of computation theory (Berlin/Wendisch-Rietz 1979), Math. Res. 2, Akademie-Verlag, Berlin (1979), 565-574. · Zbl 0446.68036 |
| [40] | V. Makam, Hilbert series and degree bounds for matrix (semi-)invariants, J. Algebra 454 (2016), 14-28. · Zbl 1366.16020 |
| [41] | R. Meshulam, On the maximal rank in a subspace of matrices, Quart. J. Math. Oxford Ser. (2) 36 (1985), no. 142, 225-229. · Zbl 0565.15006 |
| [42] | R. Meshulam, On k-spaces of real matrices, Linear and Multilinear Algebra 26 (1990), no. 1-2, 39-41. · Zbl 0692.15010 |
| [43] | J. S. Milne, Algebraic groups: The theory of group schemes of finite type over a Field, Cambridge Stud. Adv. Math. 170, Cambridge University, Cambridge 2017. · Zbl 1390.14004 |
| [44] | K. D. Mulmuley, Geometric complexity theory V: Efficient algorithms for Noether normalization, J. Amer. Math. Soc. 30 (2017), no. 1, 225-309. · Zbl 1402.14078 |
| [45] | K. D. Mulmuley and M. Sohoni, Geometric complexity theory. I. An approach to the P vs. NP and related problems, SIAM J. Comput. 31 (2001), no. 2, 496-526. · Zbl 0992.03048 |
| [46] | K. D. Mulmuley and M. Sohoni, Geometric complexity theory. II. Towards explicit obstructions for embeddings among class varieties, SIAM J. Comput. 38 (2008), no. 3, 1175-1206. · Zbl 1168.03030 |
| [47] | D. Mumford, J. Fogarty and F. Kirwan, Geometric invariant theory, 3rd ed., Ergeb. Math. Grenzgeb. (3) 34, Springer, Berlin 1994. · Zbl 0797.14004 |
| [48] | O. E. Raz and A. Wigderson, Subspace arrangements, graph rigidity and derandomization through submodular optimization, preprint (2019), https://arxiv.org/abs/1901.09423. · Zbl 1452.68089 |
| [49] | C. Reutenauer, Inversion height in free fields, Selecta Math. (N. S.) 2 (1996), no. 1, 93-109. · Zbl 0857.16021 |
| [50] | A. Schofield and M. van den Bergh, Semi-invariants of quivers for arbitrary dimension vectors, Indag. Math. (N. S.) 12 (2001), no. 1, 125-138. · Zbl 1004.16012 |
| [51] | A. Shpilka and A. Yehudayoff, Arithmetic circuits: A survey of recent results and open questions, Found. Trends Theor. Comput. Sci. 5 (2009), no. 3-4, 207-388. · Zbl 1205.68175 |
| [52] | L. G. Valiant, The complexity of computing the permanent, Theoret. Comput. Sci. 8 (1979), no. 2, 189-201. · Zbl 0415.68008 |
| [53] | J. Weyman, Cohomology of vector bundles and syzygies, Cambridge Tracts in Math. 149, Cambridge University, Cambridge 2003. · Zbl 1075.13007 |
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.
