Matrix Semi-Definite Inequality Does the following inequality hold? If matrix $A$ is a $n \times n $ positive semi-definite, $A \succeq 0$, and $U$ is one $n \times k$ unit column-orthogonal matrix ($k \leq n$), $U^{T}U=I$, do we have
$$A \succeq UU^{T} A U U^{T}$$ ? 
 A: Yes.  In the case of $k=n$, this is trivial.  Otherwise, select a $(n-k) \times n$ matrix $U'$ such that the (square) matrix $V = [U \; U']$ is orthogonal.
We note that
$$
A = V V^T A VV^T = (UU^T + (U')(U')^T)A(UU^T + (U')(U')^T)
$$
The key, then, is to show that
$$
(UU^T + (U')(U')^T)A(UU^T + (U')(U')^T) \succeq UU^TAUU^T
$$
To do so, consider the expression $x^T A x$, and note that an arbitrary $x$ can be broken into components $x^\perp$ and $x^{||}$ which are respectively orthogonal and parallel to the image of $U$.

More rigorous proof:
Let $x \in \Bbb F^n$ be arbitrary, and split $x$ into $x^\perp$ and $x^{||}$ as defined above.  We note that
$$
x^T A x \leq 
(x^\perp)^TA x^{\perp} + 
(x^{||})^T A x^{||}
$$
Now, noting that $(x^\perp)^T U = U^T x^\perp = 0$ and taking both $U$ and $U'$ as above, we have
$$
x^T UU^T A UU^T x \\
=(x^\perp + x^{||})^T UU^T A UU^T (x^\perp + x^{||})\\ 
= (x^{||})^T UU^T A UU^T x^{||}\\
=(x^{||})^T (UU^T + (U')(U')^T)A(UU^T + (U')(U')^T) x^{||} \\
= (x^{||})^T A x^{||}\\
\leq x^T A x
$$

EDIT: The above is incorrect as written.  I will salvage it if I can.
A: This is generally false.
A simple example can be constructed as follows. 
Assume $A$ to have the form
$$
A=\left[\begin{array}{cc}A_{11}&A_{12}\\A_{21}&A_{22}\end{array}\right]\begin{array}{l}\}\;n_1\\\}\;n_2\end{array}, \quad n_1+n_2=n,
$$
and let $U\in\mathbb{R}^{n\times n_1}$ consists of the first $n_1$ columns of the identity (clearly, $U^TU=I_{n_1}$). Then 
$$
UU^TAUU^T=\begin{bmatrix}A_{11} & 0 \\ 0 & 0\end{bmatrix}
$$
and hence
$$
B:=A-UU^TAUU^T=\begin{bmatrix}0&A_{12}\\A_{21}&A_{22}\end{bmatrix}.
$$
The matrix $B$ cannot be semi-definite unless $A_{12}=A_{21}^T=0$ (as a consequence of row/column inclusions for semi-definite matrices), which is of course not true in general.
