# Sparse matrix factorization of a rank deficient matrix by decomposition into linearly independent components

I've got a little conjecture I need to prove for a theoretical result related to causal Bayes net search with latent variables under sparsity constraints. If you're interested in the application please feel free to email me at adambrod@andrew.cmu.edu.

Here's the problem:

Suppose we have a $p\times q$ real matrix $A$ such that 1) $A$ is rank deficient so $\textrm{rk}(A)=r<\min(p,q)$, and 2) there are no zero elements in $A$.

I want to prove that there is no factorization of $A$ into two matrices with fewer total non-zero elements than some factorization of $A$ into two matrices $B$ and $C$ of dimensions $p\times r$ and $r\times q$.

The proof strategy I'm employing is proof by induction on rank.

The base case, $\textrm{rk}(A)=1$ is trivial ($B$ and $C$ must have at least $p+q$ non-zero elements between the two of them in order for every element of $A$ to be non-zero and that is the maximum number of elements in a pair of matrices with dimensions $p\times r$ and $r\times q$).

The induction step is as follows: Subtract a matrix $D$ of rank 1 from $A$ such that the resulting matrix $S$ is of rank $r-1$. This corresponds to removing all of the "influence" of some specific row vector $v$ from $A$, such that $v$ is linearly independent of the remainder, $S$. $D$ can be expressed as the outer product of some column vector $w$ with $v$. Suppose $wv$ is the sparsest factorization of $D$ (the possibility of this is implied by our base case). Let $RT$ be the sparsest factorization of $S$ of dimensions $p\times r-1$ and $r-1\times q$ respectively. My conjecture is that the sparsest factorization of $A$ is achieved by appending these two sparsest factorizations, that is, the sparsest factorization of $A$ is the product of $R$ with $w$ appended as the $r$th column and $T$ with $v$ appended as the $r$th row. Because $D$ and $S$ are linearly independent this seems quite plausible, but a rigorous demonstration eludes me.

Any solutions, suggestions, or references would be greatly appreciated, and of course, if you provide me with personal information (name/department affiliation), I would be happy to acknowledge your assistance in any publications I apply this result in.

Thanks!