How can I find rank of $A=\sum_{i=1}^4 x_ix_i^T$ without actually finding the matrix $A$?

Question

Suppose $A=\sum\limits_{i=1}^4 x_ix_i^T$ where

$x_1=(1,-1,1,0)^T,x_2=(1,1,0,1)^T,x_3=(1,3,1,0)^T$ and $x_4=(1,1,1,0)^T$.

How can I find the rank of $A$ without explicitly finding the matrix $A$ and then transforming $A$ to an echelon matrix?

I know that $\operatorname{rank}(A)=3$ proceeding the usual way.

We have $\operatorname{rank}(x_ix_i^T)=1$ for each $i$, but that doesn't help me much here. Also, $x_1=2x_4-x_3$. Does that imply there are $3$ linearly independent rows/columns in $A$?

As this question was supposed to be solved in the exam with limited time at hand, I am left to wonder if it can be solved rather quickly.

Answer 1

The matrix $A$ can be written as $A=XX^T$ where $X=[x_1\ x_2\ x_3\ x_4]$. Now use the fact that $\operatorname{rank}XX^T=\operatorname{rank}X$, so all you need to do is the find the rank of $X$.

Answer 2

Observe that for any vector $c$, $$Ac = \sum_{i=1}^{4} x_ix_i^Tc = \sum_{i=1}^{4} (x^Tc)x_i$$

The image of a linear map is a vector space. That means that for every $Ac$ we can find some set of vectors which spans this set. Can you find such a set (even if the set is linearly dependent)? If you can find such a set, then you just need to count how many linearly independent vectors you need to span the same space (i.e. remove vectors which are linearly dependent).