# [Math] Rank of sum of rank-$1$ matrices

linear algebramatricesmatrix-rank

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$.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 4, "wp-katex-eq": 0, "align": 1, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://imathworks.com/math/math-rank-of-sum-of-rank-1-matrices/", "fetch_time": 1713814294000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2024-18/segments/1712296818337.62/warc/CC-MAIN-20240422175900-20240422205900-00634.warc.gz", "warc_record_offset": 268455381, "warc_record_length": 5860, "token_count": 453, "char_count": 1135, "score": 4.1875, "int_score": 4, "crawl": "CC-MAIN-2024-18", "snapshot_type": "latest", "language": "en", "language_score": 0.7417377233505249, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00034-of-00064.parquet"}