# Optimizing a matrix quadratic form with respect to Loewner order

Fix integers $$1 \leq k \leq n$$. Let $$P \in \mathbb{R}^{n \times k}$$ be such that $$P^T P$$ has full rank.

Let $$\mathcal{X}$$ denote the set of unit trace, real $$n \times n$$ symmetric positive semidefinite matrices.

Question: Given any $$X \in \mathcal{X}$$ is it possible to find $$Y \in \mathcal{X}$$ such that $$Y$$ has rank at most $$k$$ and such that $$P^T X P \preceq P^T YP?$$

This is obviously true if $$k = 1$$. Indeed, then for a nonzero $$p \in \mathbb{R}^n$$, we have for any $$X \in \mathcal{X}$$, that $$Y = \frac{1}{p^T p} pp^T \in \mathcal{X}$$ and $$p^T Y p = p^Tp \geq p^T Xp.$$ Does this hold for $$k > 1$$?

You may assume without loss of generality that $$P^TP = I_k$$; otherwise orthonormalize its columns / apply Gram-Schmidt to get a new $$P$$ with this property. (If you want a closed formula, you can set $$P \gets P(P^TP)^{-1/2}$$.)
Then, for any $$X\in\mathbb{R}^{n\times n}$$ (even without assuming definiteness/trace conditions), the matrix $$Y = PP^T X PP^T$$ has rank $$k$$ and satisfies $$P^TYP = P^TXP$$.
• Hm. But what about the trace condition? Your $Y$ does not satisfy $\mathrm{tr}(Y) = 1$. Commented Sep 5 at 20:21
• I guess one can simply pre-multiply $Y$ by $\alpha^{-1}$ where $\alpha = \mathrm{tr}(P^T X P)$. Then using the fact that $\mathrm{tr}(P^T X P ) \leq \|P P^T\| \mathrm{tr}(X) \leq 1$, we have $$\alpha^{-1} P^T X P \succeq P^T XP$$ as needed. Commented Sep 5 at 20:25
If you meant that you want that property to hold for all matrices $$X$$ simultaneously, then the answer is that there exists no trace-1 matrix with that property for $$k\geq 2$$. Let again $$P$$ have orthonormal columns without loss of generality, and assume that it has at least two columns $$p_1$$ and $$p_2$$. Then testing the condition on $$X_1 = p_1 p_1^T$$ and $$X_2 = p_2 p_2^T$$ gives $$p_1^T Y p_1 \geq 1$$, $$p_2^T Y p_2 \geq 1$$, and these two inequalities cannot hold together because $$1 = \operatorname{Tr} Y \geq p_1^T Y p_1 + p_2^T Y p_2$$ (in an orthogonal basis that starts with $$p_1, p_2$$, the RHS contains the first two elements on the diagonal of $$Y$$).