On the orbit closure intersection problems for matrix tuples under conjugation and left-right actions

Abstract

Let G be a linear algebraic group acting on the vector space V. Given v, v' ∈ V, the orbit closure intersection problem asks to decide if the orbit closures of v and v' under G intersect. Due to connections with polynomial identity testing, the orbit closure intersection problems for the conjugation and left-right actions on matrix tuples received considerable attention in computational complexity and computational invariant theory, as seen in the works of Forbes-Shpilka (RANDOM 2013), Allen-Zhu-Garg-Li-Oliveira-Wigderson (STOC 2018), and Derksen-Makam (Algebra & Number Theory 2020). In this paper, we present new algorithms for the orbit closure problem for the conjugation and left-right actions on matrix tuples. The main novel feature is that in the case of intersecting orbit closures, our algorithm outputs cosets of one-parameter subgroups that drive the matrix tuples to a tuple in the intersection of the orbit closures.

Locations

• SZTAKI Publication Repository (Hungarian Academy of Sciences) - View - PDF
• Society for Industrial and Applied Mathematics eBooks - View