# positive semidefinite matrix condition

There is a great work of Alizadeh that in section 4 speaks about Minimizing sum of the first few(k-largest) eigenvalues of a symmetric matrix. Instead of a symmetric model we use the weighted Laplacian $(L_c(G) = \displaystyle \sum_{ij \in E} c_{ij}E_{ij})$of graph $G = (N, E)$. Then the dual problem is the following model:

\begin{equation*} \begin{array}{llll} \min & k z + {\rm trace~}V \\ \rm{s.t.} & Iz + V - \sum_{ij \in E} c_{ij}E_{ij} \succeq 0 , \\ % U & \sum_{ij \in E} c_{ij} = 1 ,\\ % V & c \geq 0, ~ V \succeq 0 . \end{array} \end{equation*}

Again, we write the dual of the above model to obtain this model:

\begin{equation*} \begin{array}{llll} \max & x\\ \rm{s.t.} & {\rm trace~} Y = k, \\ & x \leq \langle E_{ij}, Y \rangle ~~~~ \textrm{for } ij \in E,\\ & 0 \preceq Y \preceq I. \end{array} \end{equation*}

Because $Y$ is a positive semidefinite matrix, i.e., $Y \succeq 0$, one property of such a matrices allows us to use the Gram representation: $Y = V^T V$ with $V \in \mathbb{R}^{n \times n}$. If $v_i$ denotes the $i$-th column of $V$ then how can one write condition $Y \preceq I$ in terms of $v_i$ which $I$ is identity matrix with all diagonal entries equal to $1$?

For example the gram representation of first constraint is: $${\rm trace~} Y = \sum_{i \in N} \| v_i \|^2 = k$$

• Where does this question come from? It looks like homework to me. – Igor Rivin Oct 17 '13 at 17:27
• @IgorRivin this is a part of an sdp optimization model and I could not figure out this constraint. It is from Alizadeh's paper(famous work) in sdp. – Royeh Oct 17 '13 at 19:08
• OK, fair enough. You might want to put the "back story" in the question in the future... – Igor Rivin Oct 17 '13 at 19:41
• @IgorRivin : I have edited and explained in more details. – Royeh Oct 18 '13 at 16:36

## 1 Answer

Probably you are looking for the following (Schur-complements lemma):

\begin{equation*} V^TV = Y \preceq I,\quad\leftrightarrow\quad \begin{bmatrix} I & V^T\\ V & I \end{bmatrix} \succeq 0. \end{equation*}

• @suvrit: Now, do you think with new explanation your suggestion will work? – Royeh Oct 18 '13 at 16:39
• I don't really understand what you're getting at. I could write your constraint as $\|V^TV\| \le 1$, which is a difficult nonlinear constraint, which you can then write it terms of singular values of $V$, but one doesn't gain much by that... – Suvrit Oct 18 '13 at 18:03
• I want to have an embedding model in terms of column of $V$, i.e. $v_i$'s. – Royeh Oct 18 '13 at 18:20