Optimization, Complexity and Invariant Theory

Abstract: Let P be a matrix property, e.g. having rank at most (or at least) k, being nilpotent, having no multiple eigenvalues, etc. We will survey some old and new results and problems on the maximal dimension of linear spaces of matrices having property P. In particular, we will discuss the following topics: 1. Spaces of matrices of rank at most k: Flanders type theorems and their connections with matching theory. 2. Bounded rank subspaces of the exterior algebra and weak matchings in hypergraphs. 3. The Edmonds and Lovasz min-max theorems, and the search for efficient deterministic algorithms for PIT. 4. Spaces of matrices of rank at least k: The cases of algebraically closed vs. finite fields. 5. Spaces of real nonsingular matrices: Clifford algebras and topological upper bounds. 6. Spaces of nilpotent elements: Gerstenhaber type theorems and their Lie algebra extensions.