Show $AA^T-(X^T X)^{-1}$ is positive semidefinite where $AX=I$. $A, X$ may not be invertible or square.
Attempt: One way is to check $$AA^T-(X^T X)^{-1}=$$$$\bigg(A-(X^TX)^{-1}X^T\bigg)\bigg(A-(X^TX)^{-1}X^T\bigg)^T$$ which is not hard if come up with this equality first. I feel this is like complete square with respect numbers but without a general procedure to follow. How do one complete square with matrices in general? Are there any more intuitive approach to the proof. Thank you.
Here is an alternative approach. To prove that $$ v^TAA^Tv\ge v^T(X^TX)^{-1}v $$ for every vector $v$, write $v=X^Tu$ for some vector $u$ (in fact, we may take $u=A^Tv$). Thus the problem boils down to showing that $$ I\ge X(X^TX)^{-1}X^T, $$ but this latter inequality is evident because $X(X^TX)^{-1}X^T$ is an orthogonal projection.
You may also rewrite the above solution in the form of completion of square (well, it actually isn't a square, but a Gram matrix): \begin{aligned} AA^T-(X^TX)^{-1} &=A\left[I-X(X^TX)^{-1}X^T\right]A^T\\ &=A\left[I-X(X^TX)^{-1}X^T\right]\left[I-X(X^TX)^{-1}X^T\right]A^T\\ &=\left[A-(X^TX)^{-1}X^T\right]\left[A-(X^TX)^{-1}X^T\right]^T. \end{aligned} The moral: try to exploit the use of orthogonal projections.