patternMinor
How hard is recovering a binary matrix from its check sums?
Viewed 0 times
checkrecoveringharditsbinaryhowfrommatrixsums
Problem
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_{n1}$ and $C_{1n}$.
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).
INPUT: Two vectors $R_{n1}$ and $C_{1n}$.
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).
Solution
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.
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.
Context
StackExchange Computer Science Q#62899, answer score: 5
Revisions (0)
No revisions yet.