# How hard is recovering a binary matrix from its check sums?

I am interested in combinatorial (worst-case) one-way functions. I came across this problem which may be related to coding theory problems (I am not an expert in coding theory).

INPUT: Two vectors $R_{n*1}$ and $C_{1*n}$.

QUESTION: Is there a binary matrix $A_{n*n}$ such that vector $R$ contains the parity check of each row in $A$ and vector $C$ contains the parity check of each column in $A$.

The parity check of a row (or column) is the sum of all bits Mod 2 (XOR operation).

What is the time complexity of this problem? Is it NP-complete? Is it efficiently solvable? Is this a known problem in coding theory?

Also, it is interesting to know the time-complexity of a variant in which vectors $R$ and $C$ contains the integer sum of the one's in each row and column in $A$.

EDIT: It is interesting to note that the Sum problem becomes $NP$-complete if the directed graph is required to be acyclic (see the link in Yuval's answer).

• When you are given the actual sums, this is a known as the digraph realization problem. Aug 26, 2016 at 13:12
• For the parity problem, you need the sum of row parities and column parities to be the same, and this probably suffices. Aug 26, 2016 at 13:15

## Parity problem

It is clear that $\sum_i R_i \equiv \sum_j C_j \pmod{2}$ must hold if any solution exists. On the other hand, if this holds then some solution exists. Let $R$ contain $a$ ones, and let $C$ contain $b$ ones. We can assume without loss of generality that $a \geq b$. Arrange the rows and the columns so that \begin{align*} &(R_1,C_1) = \cdots = (R_{n-a},C_{n-a}) = (0,0) \\ &(R_{n-a+1},C_{n-a+1}) = \cdots = (R_{n-b},C_{n-b}) = (1,0) \\ &(R_{n-b+1},C_{n-b+1}) = \cdots = (R_n,C_n) = (1,1) \end{align*} Note that there is an even number of occurrences of the second type. We now construct a block diagonal matrix with the following blocks: $$\begin{pmatrix} 0 \end{pmatrix} \times (n-a), \quad \begin{pmatrix} 1 & 0 \\ 1 & 0 \end{pmatrix} \times (a-b), \quad \begin{pmatrix} 1 \end{pmatrix} \times b$$

# Sum problem

When the actual sums are given, we have the digraph realization problem, which can be solved efficiently.