How can we show the following matrix is positive semidefinite or not

Question

Suppose $U$ is $m \times n$ and $rank(U) = n$. Also, that $A$ is $m \times m$ and is invertible. How can I show whether the following difference is positive semidefinite or not?

$$U(U^\top A U)^{-1}U^\top - A^{-1}.$$

I tried to factorize this difference, but couldn't.

Answer 1

One sufficient condition is that $A\prec 0$. In this case, let $B=-A$ and $V=B^{1/2}U$. Then \begin{aligned} &U(U^\top AU)^{-1}U^\top-A^{-1}\succeq0\\ &\Leftrightarrow B^{-1}-U(U^\top BU)^{-1}U^\top\succeq0\\ &\Leftrightarrow B^{1/2}\left(B^{-1}-U(U^\top BU)^{-1}U^\top\right)B^{1/2}\succeq0\\ &\Leftrightarrow I-V(V^\top V)^{-1}V^\top\succeq0, \end{aligned} which is true because $I-V(V^\top V)^{-1}V^\top$ is the orthogonal projection onto the orthogonal complement of the column space of $V$.

Answer 2

Consider $U:\mathbb R^n\to\mathbb R^m$. Since $U$ is rank $n$, we know that $\mathbb R^m=V\oplus W$, where $\dim_\mathbb RV=m$. So that $U^T|_{V}$ is invertible. The assumption that $U^TAU$ is invertible means that $A(V)=V$.

Consider now $a\in V$ and $b\in W$, so that $a+b$ is an arbitrary $m$-vector. Then one can see that $$ (U(U^TAU)^{-1}U^T-A^{-1})(a+b) = -A^{-1}b. $$ So you need $A$ to be negative semi-definite on the space $W$.