Search

The following multi-determinantal algebraic variety plays a central role in algebra, algebraic geometry and computational complexity theory: SING n , m {{\rm SING}_{n,m}} , consisting of all m-tuples of n × n {n\times n} complex matrices which span only singular matrices. In particular, an efficient deterministic algorithm testing membership in SING n , m {{\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: SING n , m {{\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 SING n , m {{\rm SING}_{n,m}}. To prove this result, we identify precisely the group of symmetries of SING n , m {{\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 = 1 {m=1} , and suggests a general method for determining the symmetries of algebraic varieties. [ABSTRACT FROM AUTHOR]

Using the Grosshans Principle, we develop a method for proving lower bounds for the maximal degree of a system of generators of an invariant ring. This method also gives lower bounds for the maximal degree of a set of invariants that define Hilbert's null cone. We consider two actions: The first is the action of SL (V) on S 3 (V) ⊕ 4 , the space of 4-tuples of cubic forms, and the second is the action of SL (V) × SL (W) × SL (Z) on the tensor space (V ⊗ W ⊗ Z) ⊕ 9. In both these cases, we prove an exponential lower degree bound for a system of invariants that generate the invariant ring or that define the null cone. [ABSTRACT FROM AUTHOR]