# Gram representation of a positive semidefinite condition

Suppose $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 instance: $\langle Y, I \rangle = \sum_{i \in N} \| v_i \|^2$.

• Did you post (and delete) the same question yesterday on this site or MO? I remember that someone answered exactly the same question yesterday, and the answer given was that $\pmatrix{I&V^T\\ V&I}\succeq0$. – user1551 Oct 19 '13 at 8:10
• But this is not going to work in my case. – Royeh Oct 19 '13 at 9:45

## 1 Answer

$Y\preceq I$ if and only if $x^\ast (I-Y)x\ge0$ for all vector $x$. Since the norm of $x$ does not matter, we may consider only unit vectors and the previous condition is equivalent to $\|Vx\|_2\le1$ for all unit vector $x$, i.e. the operator 2-norm $\|V\|_2$ (i.e. the largest singular value of $V$), is $\le1$.

• So, by using your comment one can have the following, right? $$\| V \|_2 = \| V \|_F = \sqrt{{\rm trace~} A^T A} = \sqrt{\sum_i \| v_i \|^2}$$ Which the condition will be in the form: $$Y \preceq I \Rightarrow \sum_i \| v_i \|^2 \leq 1$$ – Royeh Oct 19 '13 at 10:28
• @Saber No. $\|V\|_2=\max_{\|x\|_2=1}\|Vx\|_2=\sigma_1(V)$ is the operator 2-norm, not the Frobenius norm $\|V\|_F$. However, since all norms on a finite-dimensional vector space are equivalent, there exist some constant $C>0$ (that is dependent of $n$ but not $V$) such that $\|V\|_2\le C\|V\|_F$. So, in theory, $\|V\|_F\le\frac1C$ is a sufficient condition for $Y\preceq I$, but this condition is not very useful in practice. – user1551 Oct 19 '13 at 10:31
• But I do not need the singular value. I have to have just an constraint which have only $v_i$ as a variable, nothing more!! – Royeh Oct 19 '13 at 10:36