Show that $A(A^TA)^{-1}A^T$ is symmetric positive definite

Question

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?

Answer 1

Some facts about positive semi-definite (PSD) matrices:

1. If $X$ is any matrix, then $X^\top X$ is always PSD.
2. The inverse of an (invertible) PSD matrix is also PSD.
3. 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.

Answer 2

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$.

Answer 3

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.