Singular tuples of matrices is not a null cone (and the symmetries of algebraic varieties)

Abstract

Abstract The following multi-determinantal algebraic variety plays a central role in algebra, algebraic geometry and computational complexity theory: <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:msub> <m:mi>SING</m:mi> <m:mrow> <m:mi>n</m:mi> <m:mo>,</m:mo> <m:mi>m</m:mi> </m:mrow> </m:msub> </m:math> {{\rm SING}_{n,m}} , consisting of all m -tuples of <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mi>n</m:mi> <m:mo>×</m:mo> <m:mi>n</m:mi> </m:mrow> </m:math> {n\times n} complex matrices which span only singular matrices. In particular, an efficient deterministic algorithm testing membership in <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:msub> <m:mi>SING</m:mi> <m:mrow> <m:mi>n</m:mi> <m:mo>,</m:mo> <m:mi>m</m:mi> </m:mrow> </m:msub> </m:math> {{\rm SING}_{n,m}} will imply super-polynomial circuit lower bounds, a holy grail of the theory of computation. A sequence of recent works suggests such efficient algorithms for memberships in a general class of algebraic varieties, namely the null cones of linear group actions. Can this be used for the problem above? Our main result is negative: <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:msub> <m:mi>SING</m:mi> <m:mrow> <m:mi>n</m:mi> <m:mo>,</m:mo> <m:mi>m</m:mi> </m:mrow> </m:msub> </m:math> {{\rm SING}_{n,m}} is not the null cone of any (reductive) group action! This stands in stark contrast to a non-commutative analog of this variety, and points to an inherent structural difficulty of <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:msub> <m:mi>SING</m:mi> <m:mrow> <m:mi>n</m:mi> <m:mo>,</m:mo> <m:mi>m</m:mi> </m:mrow> </m:msub> </m:math> {{\rm SING}_{n,m}} . To prove this result, we identify precisely the group of symmetries of <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:msub> <m:mi>SING</m:mi> <m:mrow> <m:mi>n</m:mi> <m:mo>,</m:mo> <m:mi>m</m:mi> </m:mrow> </m:msub> </m:math> {{\rm SING}_{n,m}} . We find this characterization, and the tools we introduce to prove it, of independent interest. Our work significantly generalizes a result of Frobenius for the special case <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mi>m</m:mi> <m:mo>=</m:mo> <m:mn>1</m:mn> </m:mrow> </m:math> {m=1} , and suggests a general method for determining the symmetries of algebraic varieties.

Locations

• arXiv (Cornell University) - View - PDF
• Journal für die reine und angewandte Mathematik (Crelles Journal) - View