Geometry and Representation Theory in the Study of Matrix Rigidity

Abstract

The notion of matrix rigidity was introduced by L. Valiant in 1977. He proved a theorem that relates the rigidity of a matrix to the complexity of the linear map that it defines, and proposed to use this theorem to prove lower bounds on the complexity of the Discrete Fourier Transform. In this thesis, I study this problem from a geometric point of view. We reduce to the study of an algebraic variety in the space of square matrices that is the union of linear cones over the classical determinantal variety of matrices of rank not higher than a fixed threshold. We discuss approaches to this problem using classical and modern algebraic geometry and representation theory. We determine a formula for the degrees of these cones and we study a method to find defining equations, also exploiting the classical representation theory of the symmetric group.