# Decomposing a matrix into binary ones

Let $A$ denote the set of all 3×2 binary matrices (those containing only 0's and 1's) in which the sum of each column adds up to 2. Can I decompose $$B=\begin{bmatrix} 3/4 & 1/2 \\ 3/4 & 3/4 \\ 1/2 & 3/4 \end{bmatrix}$$ into a linear combination of matrices in $A$? For example, $$B=1/2 \begin{bmatrix}1 & 1 \\ 0 & 0 \\ 1 & 1\end{bmatrix} + 1/2 \begin{bmatrix}1 & 0 \\ 0 & 1 \\ 1 & 1\end{bmatrix}$$ or something like that.

EDIT: I want to show there is at least a matrix that cannot be decomposed. How about $$C=\begin{bmatrix} 3/4 & 2/3 \\ 3/4 & 2/3 \\ 1/2 & 2/3 \end{bmatrix}$$

• Your example doesn't seem to fit the requirement: $b_{1,1}$ should be $3/4$ by the first definition and the sum results in $b_{1,1} = 1/2\cdot 1 + 1/2\cdot 1 = 1$. Jul 20, 2017 at 12:45

There are exactly $9$ matrices in $A$. The dimension of the vector space $V$ of $3\times 2$ matrices is $6$.

The rank of the matrix (formed putting each matrix of $A$ in a row) $$\begin{pmatrix} 1&1&0&1&1&0\\ 1&1&0&1&0&1\\ 1&1&0&0&1&1\\ 1&0&1&1&1&0\\ 1&0&1&1&0&1\\ 1&0&1&0&1&1\\ 0&1&1&1&1&0\\ 0&1&1&1&0&1\\ 0&1&1&0&1&1 \end{pmatrix}$$ is $5$, and this means that $A$ does not generate $V$. The other answer shows that, nevertheless, the particular matrix $B$ is generated by $A$.

Multiply $B$ by four: $$4B=\begin{bmatrix}3&2\\3&3\\2&3\end{bmatrix}$$ Finding a decomposition into matrices in $A$ is then easy: $$4B=\begin{bmatrix}1&1\\0&0\\1&1\end{bmatrix}+\begin{bmatrix}0&1\\1&1\\1&0\end{bmatrix}+2\begin{bmatrix}1&0\\1&1\\0&1\end{bmatrix}$$ $$B=\frac14\begin{bmatrix}1&1\\0&0\\1&1\end{bmatrix}+\frac14\begin{bmatrix}0&1\\1&1\\1&0\end{bmatrix}+\frac12\begin{bmatrix}1&0\\1&1\\0&1\end{bmatrix}$$

For the scope of your question, speaking of matrices $3 \times 2$ or vectors $6 \times 1$ is exactly the same thing.

So the question translates into:
In 6D, given a vector, may I decompose it into a linear combination of binary vectors having $2$ ones in the first three components, and $2$ in the last three ?

There are $9$ different reference vectors, and thus the matter is to understand if they can form a base for $\mathbb{R}^6$.

As already stated in a previous answer, the rank of the resulting $6 \times 9$ matrix $\mathbf{A}$ (whose columns are the nine different vectors) is $5$, so you cannot represent whichever vector in $\mathbb{R}^6$, but only the vectors pertaining to a specific $5$D subspace of it.

The null-space of $\mathbf{A}^T$ is the vector $\mathbf {n} = (-1,-1,-1,1,1,1)^T$, as it is easy to verify.
That means that all the nine vectors are orthogonal to this one, and so that they span the subspace orthogonal to that.

The conclusion is that you can represent any vector lying in that subspace, i.e. such that the sum of its upper half is equal to that of the lower half, i.e. any matrix $3 \times 2$ ($\mathbf B$), such that the sum of its columns is the same.
The example of $\mathbf B$ that you give is one those.