*This is a more carefully worded version of [this](https://math.stackexchange.com/questions/1719656/factor-a-square-matrix-bf-a-into-product-bf-b-bf-c-where-bf-c) question, here tailored to professional mathematicians.*


Consider a matrix ${\bf A}\in{\bf M}\_{n\times n}({\mathbb R})$ with possibly positive, negative and zero-valued entries and ${\rm Det}[{\bf A}] \neq 0$. 



> 
> Is there an algorithm to write ${\bf A}$ as a product of two matrices
>  ${\bf B}{\bf C}$ where ${\bf B} \in{\bf M}\_{n\times n}({\mathbb R})$ and ${\bf C} \in{\bf M}\_{n\times n}({\mathbb R}\_\ge)$ in which ${\bf B}$ has the maximum number of $0$
>  entries (i.e., is sparse) and all the entries of ${\bf C}$ are
>  non-negative? Again, the cost metric is the number of non-zero
>  entries in ${\bf B}$.
> 
> 
> 


**Example**


Suppose ${\bf A} = \left( { \ \ 1\ \ \ \ 2 \atop -6\ -8} \right)$. 


Here are three factorizations, ${\bf B}{\bf C}$, with their associated costs.


* $\left( { \ \ 1\ \ \ \ \ 2 \atop -6\ -8} \right)\left( {1\ \ \ \ 0 \atop 0\ \ \ \ 1} \right)$, Cost = $4$
* $\left( {0\ \ \ \ \ 2 \atop 1\ \ \ \ -14} \right)\left( {1\ \ \ \ \ \ 6 \atop 1/2\ \ \ \ 1} \right)$, Cost = $3$
* $\left( {1\ \ \ \ \ 0 \atop 0\ \ \ \ -2} \right)\left( {1\ \ \ \ \ 2 \atop 3\ \ \ \ \ 4} \right)$, Cost = $2$


I do not need an algorithm to find a *unique* decomposition, just a principled method for finding at least one having minimum cost. 


As far as I know, despite immense work on matrix factorization, this precise problem has never been solved. (*Polar decomposition*, *Cholesky decomposition*, *LUD decomposition*, *Gram-Schmidt orthogonalization* and *Sparse matrix approximation* are not quite appropriate.)


**Motivation**


The general computational task is to perform the linear operation ${\bf A}{\bf x}$, where ${\bf A}$ has the conditions listed above and ${\bf x}$ is an $n$-dimensional real-valued vector of non-negative entries. The overall computational task can be split into two linear systems. The first system can perform ${\bf C}{\bf x}$ at extremely low computational cost (assume zero cost), but the entries of ${\bf C}$ must be non-negative. The second system can perform ${\bf B}{\bf y}$ (where ${\bf y} = {\bf C}{\bf x}$) and the entries of ${\bf B}$ can be positive or negative or zero but there is a unit cost for each non-zero entry of ${\bf B}$. 


We seek to split the overall computation of ${\bf A}{\bf x}$ into the two systems to minimize the overall computational cost.



Factor matrix ${\bf A}$ into the product ${\bf B}{\bf C}$ where ${\bf C}$ has no negative entries and ${\bf B}$ has few non-zero entries
Let $v\_1, \dots, v\_n$ denote the rows of $A$. 


Let $u$ be a vector with all positive entries that is not a linear combination of $v\_2, \dots, v\_n$. Then we may write $v\_1 = c u + a\_2 v\_2 + \dots a\_n v\_n$ for some scalars $c, a\_2, \dots, a\_n$.


Now choose $\epsilon$ small enough that for all $j$ from $2$ to $n$, $u + \epsilon \sum\_{i=2}^j a\_i v\_i$ has all positive entries.


Let $C$ be the matrix with rows $u + \epsilon \sum\_{i=2}^j a\_i v\_i$ for $j$ from $1$ to $n$. Then by construction $C$ has all positive entries.


Each vector $v\_i$ can be written as a linear combination of two rows of $C$. For $v\_i$ this is by subtracting two adjacent rows and dividing by $\epsilon$, and for $v\_1$ it is $c-1/\epsilon$ times the first row plus $1/\epsilon$ times the last row.


We conclude that there is a sparse matrix $B$ with $2n$ entries such that $BC = A$.


This is optimal assuming each of the $v\_i$ has both positive and negative entries, as the corresponding row of $B$ must have both positive and negative entries and hence at least $2$ entries. If $A$ has any rows that are either non-negative or non-positive, then this algorithm might not be optimal, as the example in the original question shows. However, this algorithm produces matrices where $BC$ is very sensitive to slight changes in $C$ and thus may be unsuitable for practical applications.


