How do I proof that $A=\sum\limits_{i=1}^{m}x_{i}x_{i}^{T} $ is invertible if and only if $X$ has full rank?

Question

Show that $A=\sum\limits_{i=1}^mx_ix_i^T$ is invertible if and only if $x_1,\cdots,x_m$ span $\mathbb R^d$ for $x_i\in\mathbb R^d$.

Here are my thoughts: If $A$ is invertible $Aw=0$ only has the trivial solution $w=0$. We can write $$ Aw = \sum_{i=1}^{m}x_{i}x_{i}^{T}w = \sum_{i=1}^{m} \begin{pmatrix}x_{i1}\\...\\x_{id}\end{pmatrix} (x_{i1}w_{1}+x_{i2}w_{2}+...+x_{id}w_{d})=0$$ Now, assuming that $x_{1},..., x_{m}$ do span $ \mathbb{R}^{d} $, there can only be the trivial solution that all factors $c_{i}=(x_{i1}w_{1}+x_{i2}w_{2}+...+x_{im}w_{m})$ are zero. This can only be true if $w=0$ because otherwise there would be a non trivial solution to $X^{T}w=0$ which would be a contradiction to the assumption I made.

So that shows if $x_{1},..., x_{m}$ span $ \mathbb{R}^{d} \Longrightarrow A$ is invertible, right?

But how do I show that $A$ is invertible $\Longrightarrow $ $x_{1},..., x_{m}$ span $ \mathbb{R}^{d}$ also holds true?

Thank you!

Answer 1

If $w$ is orthogonal to all the $x_i's$, then $$Aw=\sum_{i=1}^m x_i(x_i^\top w)=0$$ i.e. $w$ is in the kernel of $A$. Conversely, if $w$ is in the kernel of $A$, then $$Aw=0\\ \implies w^\top Aw=0\\ \implies\sum_{i=1}^m(w^\top x_i)^2=0\\ \implies w^\top x_i=0\,\forall 1\le i\le m$$ i.e. $w$ is orthogonal to all the $x_i's$, hence, the kernel of $A$ and $X$ are same and therefore $A$ is invertible iff $X$ has full rank.

Another method is to note that $$A=\sum_{i=1}^m x_ix_i^\top\\ =\begin{pmatrix} x_1&x_2&\cdots &x_m\end{pmatrix} \begin{pmatrix}x_1^\top\\x_2^\top\\\vdots\\x_m^\top\end{pmatrix}\\ =XX^\top$$ Therefore, $A$ and $X^\top$ have the same rank leading to the desired result. (since, by the same arguments $Aw=0\implies (X^\top w)^\top(X^\top w)=0\implies X^\top w=0$ and conversely, $X^\top w=0\implies Aw=0$)

Answer 2

Hint: You can easily check that $A$ is a PSD Matrix. You need to check when will $A$ be a Positive Definite Matrix. $$\ y^TAy=\sum_{i=1}^my^Tx_ix_i^Ty=\sum_{i=1}^m(x_i^Ty)^2 $$ When can you find a $y$ s.t. $x_i^Ty=0 \ \forall i\in[m]?$ Can you express this as $By=0$ where colmuns/rows of $B$ are $x_i$? You just need to argue that Null-Space of $B$ is empty if and only if $x_1,\cdots,x_m$ span $\mathbb R^d$