Is a solution of a linear system of semidefinite matrices a convex combination of rank 1 solutions? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T06:07:54Z http://mathoverflow.net/feeds/question/74561 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/74561/is-a-solution-of-a-linear-system-of-semidefinite-matrices-a-convex-combination-of Is a solution of a linear system of semidefinite matrices a convex combination of rank 1 solutions? Colin Tan 2011-09-05T07:07:24Z 2011-09-05T12:05:33Z <p>The cone of symmetric positive semidefinite $n\times n$ matrices is the convex hull of rank $1$ matrices. That is, every symmetric positive semidefinite matrix is a convex combination of rank 1 matrices.</p> <blockquote> <p>Does this property generalize to solutions of linear systems of semidefinite matrices? </p> </blockquote> <p>Let me be precise. Fix $k$ symmetric $n\times n$ matrices $A_1,\ldots, A_k$. Consider the system of linear equations $\langle A_1,X\rangle=\cdots = \langle A_k, X\rangle = 0$, which you want to solve for a symmetric semidefinite $n\times n$ matrix $X\succeq 0$. Here, the inner product of two matrices is $\langle(a_{ij}),(b_{ij})\rangle=\sum_{i,j = 1}^n a_{ij}b_{ij}$.</p> <p>The set of solutions $X$ forms a closed convex subcone $C$ of the cone of semidefinite $n\times n$ matrices. Is $C$ the convex hull of its rank 1 matrices? Namely, is every solution a convex combination of rank 1 solutions?</p> http://mathoverflow.net/questions/74561/is-a-solution-of-a-linear-system-of-semidefinite-matrices-a-convex-combination-of/74562#74562 Answer by Igor Rivin for Is a solution of a linear system of semidefinite matrices a convex combination of rank 1 solutions? Igor Rivin 2011-09-05T07:59:24Z 2011-09-05T07:59:24Z <p>The answer seems obviously "no", since a system of equations need not have <em>any</em> rank one solutions (for example, the solution set can be the line $x I_n,$ where $I_n$ is the identity matrix.)</p> http://mathoverflow.net/questions/74561/is-a-solution-of-a-linear-system-of-semidefinite-matrices-a-convex-combination-of/74563#74563 Answer by Robert Israel for Is a solution of a linear system of semidefinite matrices a convex combination of rank 1 solutions? Robert Israel 2011-09-05T08:00:42Z 2011-09-05T08:00:42Z <p>No. Try $n=k=2$ with $A_1 = \pmatrix{1 &amp; 0\cr 0 &amp; -1\cr}$ and $A_2 = \pmatrix{1 &amp; 1\cr 1 &amp; -1\cr}$. The only symmetric matrices $X$ with $(A_1,X) = (A_2,X) = 0$ are multiples of $I$, so there are no rank 1 solutions.</p>