Particular additive matrix decomposition

Question

I have a matrix that I need to decompose into a sum of individual matrices. I want to find the minimum number of individual matrices I need in order to do this. The individual matrices must have a particular form which I will explain in a moment.

So, a very simple example would be the following. My initial $3 \times 3$ matrix is

$$ \begin{pmatrix} 0.0 & 0.4 & 0.3 \\ 0.5 & 0.0 & 0.3 \\ 0.5 & 0.6 & 0.0 \end{pmatrix} $$ The matrices that sum to this matrix must have each cell being $0$ or a particular number (call it $X_n$). If the entry in a cell is not zero then the symmetric cell must be zero (i.e. if cell $[1,3]$ is say $0.1$ then cell $[3,1]$ be must $= 0$). The sum of the $X_n$ must be $= 1$. So I could decompose the matrix above as follows: $$ \begin{split} \text{Matrix }1 &= \begin{pmatrix} 0.0 & 0.3 & 0.3 \\ 0.0 & 0.0 & 0.3\\ 0.0 & 0.0 & 0.0\\ \end{pmatrix}\\ \\ \text{Matrix }2&= \begin{pmatrix} 0.0 & 0.0 & 0.0 \\ 0.5 & 0.0 & 0.0 \\ 0.5 & 0.5 & 0.0 \end{pmatrix}\\ \\ \text{Matrix }3 & = \begin{pmatrix} 0.0 & 0.1 & 0.0 \\ 0.0 & 0.0 & 0.0\\ 0.0 & 0.0 & 0.0\\ \end{pmatrix}\\ \\ \text{Matrix }4 &= \begin{pmatrix} 0.0 & 0.0 & 0.0 \\ 0.0 & 0.0 & 0.0 \\ 0.0 & 0.1 & 0.0 \end{pmatrix} \end{split} $$ The actual matrices I will have will be bigger than this and might have entries like 0.51678.

I have searched around, but this doesn't seem to be a standard decompsition problem. So my inital thought was to set it up as an integer programming problem (turning 0.51678 into 51678 say) and increase the number of types I allow until I get a feasible solution.

My question is if I am wrong and there is a standard algorithm for doing this, or whether the integer approach seems stupid and another approach would be better.

I would be very grateful for any thoughts.

(If it matters, I mostly program in R but can use Python, Julia ... too).

Answer 1

I want to be sure I understood well your problem. The fact that the symmetric of a non-zero cell must be equal to 0. Does it implies that you are making a sum of triangular matrices?

I know that this kind of matrices is allowed in your examples (which is not a triangular matrice):

\begin{pmatrix} 0.0 & 0.3 & 0.3 \\ 0.0 & 0.0 & 0.0\\ 0.0 & 0.3 & 0.0\\ \end{pmatrix}

But I think it can always be translated to a triangular matrix like that one: \begin{pmatrix} 0.0 & 0.3 & 0.3 \\ 0.0 & 0.0 & 0.3\\ 0.0 & 0.0 & 0.0\\ \end{pmatrix}

Yes, I didn't follow the rules (I didn't answer the question, I've asked for clarifications) because I don't have 50 in reputation so I cannot comment on the question asked.

Answer 2

You did not specify whether your $X_n$ scalars need be nonnegative, so I'll assume not (but will assume their absolute values are bounded by some constant $M$). Let $B$ be the matrix to which your terms must sum. Suppose you list out all possible matrices of the required form where the nonzero component is 1. So, for example, let $$A_1=\left(\begin{array}{ccc} 0 & 1 & 1\\ 0 & 0 & 1\\ 0 & 0 & 0 \end{array}\right),$$ $$A_2=\left(\begin{array}{ccc} 0 & 0 & 0\\ 1 & 0 & 0\\ 1 & 1 & 0 \end{array}\right)$$ etc. The key here is that any matrix meeting your requirements to be a term in the sum will be a scalar multiple of one of these matrices. Now let $x_i \in [-M,M]$ and $y_i\in \{0,1\}$ be variables for $i=1,\dots,N$, where $N$ is the number of $A$ matrices you have. Your problem can be written as the mixed integer linear program $$\begin{align*} \min & \sum_{i=1}^{N}y_{i}\\ \textrm{s.t.} & \sum_{i=1}^{N}A_{i}x_{i}=B\\ & -My_{i}\le x_{i}\le My_{i}\:\forall i. \end{align*}$$Note that there is no need to round or rationalize the components of $B$. If the number of possible $A$ matrices is too large, you can use a subset of them and (assuming the subset provides feasible model) get a suboptimal but possibly okay solution.