Polynomial-Time Optimal Group Selection via the Double-Commutator Eigenvalue Problem

A new paper by Mitchell A. Thornton tackles the longstanding problem of optimal group selection in the algebraic diversity framework. Previously, finding the finite group whose spectral decomposition best matches an unknown covariance matrix required enumerating all subgroups of the symmetric group S_M — an exponential-time operation. Thornton proves this combinatorial problem reduces to a generalized eigenvalue problem derived from the double commutator of the covariance matrix. The resulting algorithm runs in O(d²M² + d³) time, where d is the dimension of a generator basis, making it polynomial-time.

The solution is closed-form: the minimum eigenvector of the double-commutator matrix directly constructs the optimal group generator without iterative optimization. Crucially, the method is exact — if the optimal generator lies in the span of the basis, the minimum eigenvalue is zero; otherwise, its magnitude provides a certifiable optimality gap. The paper also links this to independent component analysis (JADE), structured matrix nearness, and simultaneous matrix diagonalization, positioning the double-commutator formulation as the only known approach that is simultaneously polynomial-time, closed-form, and certifiable.