Rank of sum of rank-$1$ matrices

If you sum a certain number of rank-$1$ matrices:

$$X = u_1 u_1^T + u_2 u_2^T + \cdots + u_N u_N^T$$

Is the result guaranteed to be rank-$N$ assuming the individual $U$ vectors are linearly independent?


If the vectors $\{u_k\}_{k=1}^N$ are linearly independent and $N\lt n$, then using the Gram-Schmidt Process, we can construct a basis $\{u_k\}_{k=1}^n$ for $\mathbb{R}^n$ containing the original vectors.

Consider $$ M_1=\sum_{k=1}^Nu_ku_k^T $$ and $$ M_2=\sum_{k=N+1}^nu_ku_k^T $$ Note that if $N=n$, then $M_2=0$.

Suppose that $(M_1+M_2)v=0$, that means that $$ \sum_{k=1}^nu_k\left(u_k^Tv\right)=0 $$ Since $u_k$ are independent, this means that $u_k^Tv=0$ for all $k$. Since $\{u_k\}_{k=1}^n$ is a basis, $v=0$. Thus, $$ (M_1+M_2)v=0\implies v=0 $$ Therefore, $M_1+M_2$ has rank $n$. Since the rank of $M_1+M_2$ is no greater than the sum of the ranks of $M_1$ and $M_2$, $M_1$ must have rank $N$, because the rank of $M_2$ is at most $n-N$.

So, yes: if $\{u_k\}_{k=1}^N$ are linearly independent, $\displaystyle\sum_{k=1}^Nu_ku_k^T$ has rank $N$.


Assuming that $N$ (the number of vectors) is the same as $n$ (the dimension of the space) then yes. Otherwise it may need to be as involved as @robjohn's answer.

Consider nonzero $v_1\in\operatorname{span}\{u_2,\ldots,u_N\}^{\perp}$. Then $Xv_1=u_1(u_1^Tv_1)$ is a nonzero scalar multiple of $u_1$. (If it were zero, then we have that $v_1$ is also orthogonal to $u_1$, and so all of the $u_i$ are in $v_1^{\perp}$ which is $(n-1)$-dimensional, a contradiction to the linear independence assumption.)

Similarly, nonzero scalar multiples of each $u_i$ are in the range of $X$. So it is a rank $N$ matrix (since the $u_i$ are independent.)