Show that $A(A^TA)^{-1}A^T$ is symmetric positive definite Let $A$ be $m\times n$ matrix with full column rank where $m > n$. Let $P = A(A^TA)^{-1}A^T$. How do we show that $P$ is SPD (symmetric positive definite)? Proving that it is symmetric is trivial, but how can I show it is positive definite?
 A: Some facts about positive semi-definite (PSD) matrices:

  
*
  
*If $X$ is any matrix, then $X^\top X$ is always PSD.
  
*The inverse of an (invertible) PSD matrix is also PSD.
  
*A matrix $X$ is PSD if and only of $x^\top Xx\ge 0$ for all vectors $x$.
  

So we try 3. on the matrix $P$:
$$x^\top P x=x^\top A(A^\top A)^{-1} A^\top x=\underbrace{(A^\top x)^\top}_{y^\top} (A^\top A)^{-1}\underbrace{A^\top x}_{y}=y^\top\underbrace{(A^\top A)^{-1}}_{X}y=y^\top X y\ge 0.$$
The last inequality follows from the fact that $X$ is PSD by 1. and 2. This shows semi-definiteness of $P$.  However, it seems $P$ cannot be (strictly) positive definite. Note first, that it is a projection:
$$PP=A(A^\top A)^{-1} \underbrace{A^\top A(A^\top A)^{-1}}_{I} A^\top =P$$
(this might suffice to show that $P$ is positive semi-definite). Further note that
$$Pv=A \underbrace{(A^\top A)^{-1} A^\top v}_u=Au \in \mathrm{span}(a_1,..,a_n),$$
where $a_1,...,a_n$ are the columns of $A$. Since the columns space is $m$-dimensional but $\mathrm{span}(a_1,...,a_n)$ is $n$-dimensional with $n<m$, we see that $P$ is a projection onto a proper subspace of $\Bbb R^m$. Hence, there exist a non-zero $v\in\ker(P)$ and $P$ cannot be (strictly) positive definite.
A: Note that $P$ is an m-by m projection matrix on $Col(A)$ thus for $\vec w\neq \vec 0$ and $\vec w \perp Col(A)$ we have $P\vec w=0$ and $w^TPw=0$.
Thus $P$ is a semi-positive definite matrix, indeed $\forall\vec x$ we can write $\vec x=a\vec v+b\vec w$ and since


*

*for $\vec v\in Col(A) \implies \vec v^TP\vec v=\vec v^T \vec v\ge0$

*for $\vec w\perp Col(A) \implies \vec w^TP \vec w=0$


we have that


*

*$\vec x^TP\vec x\ge0$ with $\vec x^TP\vec x=0$ for some $\vec x \neq \vec 0$.

A: Symmetry: 
$$(A(A^TA)^{-1}A^T)^T=(A^T)^T((A^TA)^{-1})^TA^T=A(((A^TA)^T)^{-1}A^T=A(A^TA)^{-1}A^T$$
Positive semidefinite:
$$\langle A(A^TA)^{-1}A^Tx,x\rangle=\langle(A^TA)^{-1}A^Tx,A^Tx\rangle=\langle(A^TA)^{-1}y,y\rangle$$
where $y:=A^Tx$, also $A^TA$ is invertible since $A$ has full column rank so $(A^TA)^{-1}$ exists and makes sense. Using $(A^TA)^{-1}y:=z$ then $y=A^TAz$ so finally we have
$$\langle(A^TA)^{-1}y,y\rangle=\langle z,A^TAz\rangle=\langle Az,Az\rangle=||Az||^2\geqslant 0$$
as required. 
