0
$\begingroup$

I often see this formula used in the rank 1 or rank 2 cases for Quasi-Newton methods, but I am wondering how this can be proven in the general rank $m$ case. As a linear algebra problem, I would like to show that for $v_1,v_2, \ldots,v_m \in \mathbb{R}^n$ linearly independent and $\lambda_1, \lambda_2, \ldots, \lambda_m \in \mathbb{R} \setminus \{0\}$ I have that $$ \sum_{i = 1}^{m}\lambda_i v_i v_i^T$$ has rank $m$

Any suggestions or proofs would be greatly appreciated.

$\endgroup$
1
$\begingroup$

A simple change of basis will do it. Let $M=\sum_{i=1}^m \lambda_m v_iv_i^T$ and let $B=\begin{bmatrix}v_1&v_2&\cdots&v_m&v_{m+1}&\cdots&v_n\end{bmatrix}$ be the matrix for a basis $\{v_i\}$ that extends the independent set $\{v_1,v_2,\dots,v_m\}$. This $B$ is invertible.

We claim that $M=BXB^T$, where $X$ is the diagonal matrix $$X=\begin{bmatrix}\lambda_1&0&\cdots&0&0&\cdots\\ 0&\lambda_2&\cdots&0&0&\cdots\\ \vdots&\vdots&\ddots&\vdots&\vdots&\ddots\\ 0&0&\cdots&\lambda_m&0&\cdots\\ 0&0&\cdots&0&0&\cdots\\ \vdots&\vdots&\ddots&\vdots&\vdots&\ddots\end{bmatrix}$$ This $X$ clearly has rank $m$. After multiplying on the left and right by invertible matrices $B$ and $B^T$, the rank will be unchanged, and $M$ will have rank $m$.
Why does this work? Just run the matrix multiplication: $$BX = \begin{bmatrix}v_1\lambda_1&v_2\lambda_2&\cdots&v_m\lambda_m&0&\cdots&0\end{bmatrix}$$ $$BXB^T = v_1\lambda_1v_1^T + v_2\lambda_2v_2^T+\cdots+v_m\lambda_mv_m^T+0+\cdots+0=\sum_{i=1}^m \lambda_iv_iv_i^T$$ There it is. Note that we didn't use anything about $\mathbb{R}$; this is true over any field.

A useful related concept: the tensor rank of a matrix. The rank of a matrix $A$ is equal to the smallest $k$ such that we can write $A=\sum_{i=1}^k u_iv_i^T$ as a sum of rank-1 tensors. This argument (well, a slight modification of it) shows that if each set $\{u_i\}$ and $\{v_i\}$ are linearly independent, then the tensor rank of the sum is the full $k$.

$\endgroup$
  • $\begingroup$ wow, this is a fantastic explanation. Thanks so much! $\endgroup$ – geo17 Feb 16 '19 at 22:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.