*This is a more carefully worded version of this 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.

12more comments