Consider the following result which I recently came across in a research paper in my area (Signal Processing)



> 
> Let $X$ be a $N\times N$ positive semidefinite (psd) matrix whose rank
>  is $r$. Let $A$ be any symmetric $N\times N$ matrix. Then, there exist
>  a set of vectors $x\_1,\dots,x\_r$ such that \begin{align} X & =
>  \sum\_{i=1}^{r}x\_ix\_i^T \\ x\_i^TAx\_i &=
>  \frac{\mbox{trace}\{AX\}}{r},~~~\forall i \end{align}
> 
> 
> 


The following is the proof for it which I can't verify.


**Proof:**
Consider the following step-wise procedure whose inputs are $X$ and $A$. 


$~~$0.$~~$ Inputs are $X$ (given $X\geq 0$, $rank(X)=r$) and $A$ (symmetric).


1. Decompose $X=RR^T$.
2. Generate the eigen decomposition $R^TAR=U\Lambda U^T$.
3. Let $h$ be any $N\times 1$ vector such that $\lvert h\_i\rvert=1$ (each entry of $h$). Generate the vector $x\_1$ and matrix $X\_1$ as 
\begin{align}
x\_1&=\frac{1}{\sqrt{r}}RUh \\
X\_1&=X-x\_1x\_1^T 
\end{align}
4. Outputs are $X\_1$ and $x\_1$.


The paper then claims that 


* $X\_1$ is psd and has rank $r-1$
* $x\_1^TAx\_1=\frac{1}{r}trace(AX)$


**While I am able to verify the second claim, am not able to verify the first one? How is it true?** If this can be done, the rest of the proof is straight forward. I am looking for a rigorous proof.


Read this if you are interested to know where this proof heads. Now do the stepwise algorithm earlier with inputs $X\_1$ and $A$ to get $x\_2$ and $X\_2$ such that \begin{align}X\_2&=X\_1-x\_2x\_2^T\\&=X-x\_1x\_1^T-x\_2x\_2^T\end{align} and $$x\_2^TAx\_2=\frac{1}{r-1}trace(AX\_1)=\frac{1}{r}trace(AX)$$ Then the result of the paper is that you can do this procedure $r$ times and get a rank-one decomposition $$X=\sum\_{i=1}^{r}x\_ix\_i^T$$ with the property $$x\_i^TAx\_i\,=\,\frac{1}{r}trace(AX),~\forall i$$for any given psd X with rank $r$ and any symmetrix $A$. 



Proof for a Rank-One Decomposition Theorem of Positive (semi) Definite Matrices
I don't know what's going on with the paper, but here is an argument regarding existence of such decompositions.


Given a rank one decomposition 
$$X = \sum\_{i=1}^R x\_ix\_i^T$$
one has $\sum\_{i=1}^R x\_i^TAx\_i = {\rm Trace}(AX)$, so the question is how to make these pairings $x\_i^TAx\_i$ equal to each other. Consider the minimum of the function
$$
\sum\_{i} (x\_i^TAx\_i-\frac 1R{\rm Trace}(AX))^2
$$
over the set of all possible rank one decompositions of $X$ (which is easily a compact set). Suppose this minimum occurs at some $\{x\_i\}$ and is positive.


By reindexing, we may assume that $x\_1^TAx\_1<\frac 1R {\rm Trace}(AX)$ and is the minimum of $x\_i^TAx\_i$ and that $x\_2^TAx\_2>x\_1^TAx\_1$.
Consider a small rotation $\alpha$: 
$$y\_1(\alpha)=x\_1 \cos \alpha + x\_2 \sin \alpha,~ y\_2(\alpha) = -x\_1\sin\alpha + x\_2\cos\alpha,$$
so that $y\_1y\_1^T+y\_2y\_2^T=x\_1x\_1^T+x\_2x\_2^T$. By minimality,
$$
 y\_1^T(\alpha)Ay\_1(\alpha) \leq x\_1^TAx\_1 
$$
at all sufficiently small $\alpha$, else we can move the pairings closer together by replacing $x\_1$ and $x\_2$
by $y\_1$ and $y\_2$ for small $\alpha$ and keeping $x\_{>2}$, which would contradict the minimality. This first of all implies by differentiating at $\alpha=0$ that
$$
x\_1^TAx\_2=0.
$$
Thus we get 
$$
y\_1^T(\alpha)Ay\_1(\alpha) = x\_1^TAx\_1\cos^2\alpha + x\_2^TAx\_2\sin^2\alpha
=x\_1^TAx\_1 + (x\_2^TAx\_2-x\_1^TAx\_1)\sin^2\alpha > x\_1^TAx\_1 
$$
which is a contradiction.


