Kristen Dawson

A positive semidefinite (psd) factorization of a nonnegative matrix M expresses each entry of M as the inner product of two psd matrices. If M is a slack matrix of a polytope, these factorizations correspond to spectrahedral lifts of this polytope. Our work characterizes the uniqueness of a psd factorization of a matrix of rank 3 using psd matrices of size 2. This characterization is obtained using tools from rigidity theory.

A positive semidefinite (psd) matrix is a symmetric matrix with nonnegative eigenvalues. A psd factorization of a nonnegative matrix M expresses each entry of M as the inner product of two psd matrices. If M is a slack matrix of a polytope, these factorizations correspond to spectrahedral lifts of this polytope. There are examples of polytopes with complicated descriptions that can be lifted to spectrahedra with much simpler descriptions. This transforms an NP-hard linear optimization problem to a semidefinite program that can be solved in polynomial time. Uniqueness (up to some trivial action) of a psd factorization of a matrix corresponds to uniqueness of the corresponding spectrahedral lift. Our work characterizes the uniqueness of a psd factorization of a matrix of rank 3 using psd matrices of size 2. The characterization is obtained using tools from rigidity theory.