Project III (MATH3382) 2023-24

Spectrahedra

Anne Taormina

Description

Let $A_{0},A_{1},\ldots A_{n}$ be real symmetric matrices of size $k$ and construct the symmetric linear matrix polynomial $A$ of size $k$ and dimension $n$ ,

A:=A_{0}+x_{1}A_{1}+\ldots+x_{n}A_{n},\qquad(x_{1},\ldots,x_{n})\in\mathbb{R}^% {n}.

The set $S(A)$ of points $(a_{1},\ldots,a_{n})\in\mathbb{R}^{n}$ where $A$ is positive semi-definite (i.e. all eigenvalues of $A$ are non-negative real numbers) is called a spectrahedron.

Spectrahedra share some properties with polyhedra, but enlarge that class considerably. They form a very interesting class of convex sets and their description via matrix polynomials makes them manageable. Besides their intrinsic geometric interest, spectrahedra are important tools in optimisation theory. Semi-definite programming is the computational problem of maximising a linear function over a spectrahedron, while the more well-known linear programming is semi-definite programming for diagonal matrices, or put in a different way, involves minimising a linear function over a polyhedron.

Applications of semi-definite programming are numerous, from polynomial optimisation (expressions of a polynomial as a sum of squares form a spectrahedron) to combinatorial optimisation and control theory. On the other hand, there is still a lot to discover in the world of spectrahedra. For instance, a complete characterisation of spectrahedra is not known beyond dimension 2.

The project will give you an opportunity to explore spectrahedra in dimensions 2 and 3 from a variety of perspectives, depending on your interest. One may want to construct explicit examples of spectrahedra, study theorems about them, learn about their rigid convexity, investigate their shadows, look at their use in optimisation theory and more.

Prerequisites

The project requires a command of basic matrix theory. Some explorations might be facilitated if you can code in Maple or Python for instance. The module Linear Algebra I (MATH1071) is a must.

Resources

Start by reading What is a spectrahedron? by Cynthia Vinzant

The geometry of spectrahedra by Cynthia Vinzant

A brief introduction to sums of squares by Grigoriy Blekherman

More resources will be provided if you choose this project.