Let $M$ be an $m\times n$ matrix of rank $r$. I am interested to express $M$ as $C_1 + \ldots + C_r$ where each $C_i$ is a rank-1 matrix. How many $C_i$'s of rank-1 am I allowed to fix (if any) and still be able to complete a valid decomposition?
$\begingroup$ $\endgroup$
3 
- 1$\begingroup$ This is "unlikely" to happen. It might be better to elaborate why you are looking for such a thing. $\endgroup$copper.hat– copper.hat2024-12-11 01:07:14 +00:00Commented Dec 11, 2024 at 1:07
- $\begingroup$ I am interested in the conditions that would make it possible to write $M_1 = C_1 + C_2 + \ldots + C_{r_1}$ and $M_2 = C_1 + C'_2 + \ldots + C'_{r_2}$ for two matrices $M_1$ and $M_2$ of ranks $r_1$ and $r_2$, respectively. I want $M_1$ and $M_2$ to share a matrix in the decomposition. $\endgroup$yia– yia2024-12-11 03:13:22 +00:00Commented Dec 11, 2024 at 3:13
- 1$\begingroup$ Even that does not seem feasible in general. In particular, if one of the matrices has rank 1, there won't be a solution in most cases. I think for rank-1-decompositions sharing a matrix to exist, the images of the matrices must intersect non-trivially. $\endgroup$Tzimmo– Tzimmo2024-12-13 10:10:31 +00:00Commented Dec 13, 2024 at 10:10
Add a comment |
2 Answers
$\begingroup$ $\endgroup$
2 As soon as you fix one of the $C_i$, you can almost never expect to find a decomposition anymore. For example, take $m = n = 2$, $r = 2$ and fix $C_1 = \begin{pmatrix}1 & 0 \\ 0 & 0\end{pmatrix}$. For most invertible (= rank 2) matrices $M$, also $M - C_1$ is invertible and has rank 2 again. Take $\begin{pmatrix}a & 0 \\ 0 & 1\end{pmatrix}$ for $a \neq 0, 1$. This means that you can never find a $C_2$ of rank 1 such that $M = C_1 + C_2$, because we already know that $C_2 = M - C_1$ does not have rank 1.
- $\begingroup$ Thank you for your response. I am wondering about the very special cases when you can find the decomposition and the conditions on $m, n$, and $r$ to achieve that. $\endgroup$yia– yia2024-12-11 00:10:33 +00:00Commented Dec 11, 2024 at 0:10
- $\begingroup$ That is a very broad question. $\endgroup$copper.hat– copper.hat2024-12-11 18:45:40 +00:00Commented Dec 11, 2024 at 18:45
$\begingroup$ $\endgroup$
There is a straightforward criterion to test if such an extension is possible.
Assume we are given: an $m \times n$ matrix $M$ of rank $r$ and $k$ rank 1 matrices $C_1,\dots,C_k$ where $k \leq r$. Then there exists $r-k$ rank 1 matrices $C_{k+1}, \dots, C_{r}$ such that $M = C_1 + \dots +C_k+ C_{k+1}+\dots+ C_r$ iff $\operatorname{rank}(M-R_k)=r-k$ where $R_k = C_1 + \dots + C_k$.
Proof of sufficiency: We know that any rank $t$ matrix can be written as the sum of $t$ rank 1 matrices using the singular value decomposition of the matrix, so $M-R_k$ can be written as the sum of $r-k$ rank 1 matrices and we are done.
Proof of necessity: Assume $M = C_1 + \dots +C_k+ C_{k+1}+\dots+ C_r$ where each $C_i$ is of rank 1. There exists an $m\times 1$ vector $u_i$ and an $n \times 1$ vector $v_i$ such that $C_i = u_iv_i^T$. Hence, $M = \begin{bmatrix}u_1 & \dots & u_r \end{bmatrix} \begin{bmatrix}v_1^T \\ \dots \\ v_r^T \end{bmatrix} = UV^T$ (say). Since $U$ has $r$ columns its rank cannot exceed $r$, also since the rank of $U$ must be at least the rank of $M$ its rank cannot be less than $r$, so the rank of $U$ must be exactly $r$ and the $u_i$'s must form a basis of the column space of $M$. Similarly, the $v_i$'s form a basis of the row space. Next note $M-R_k = \begin{bmatrix}u_{k+1} & \dots & u_r \end{bmatrix} \begin{bmatrix}v_{k+1}^T \\ \dots \\ v_r^T \end{bmatrix}=U_k V_k^T$ (say). So, $\operatorname{rank}(M-R_k) \leq \operatorname{rank}(U_k) = r-k.$ Also, $ U_k^T (M-R_k) = U_k^TU_k V_k^T$, and $V_k^T = (U_k^TU_k)^{-1}U_k^T (M-R_k)$ ( note $U_K^TU_k$ is invertible because the columns of $U_k$ are independent). Hence, $r-k = \operatorname{rank}(V_k^T) \leq \operatorname{rank}(M-R_k)$. Hence, we must have $\operatorname{rank}(M-R_k) = r - k$ and we are done.
