Simplifying the problem:
Given
* a positive integer $r$
* positive integers $m, n \geq 2$
* a partial binary matrix $\mathrm A \in {, 0,1}^{m \times n}$ (where $$ denotes an unknown entry)
determine whether it is possible to complete the given partial matrix $\mathrm A$ with values in ${0,1}$ such that the resulting completed matrix has rank at most $r$.
Let us consider an example.
Example
Let $r = 2$, $m = n = 3$ and
$$\mathrm A = \begin{bmatrix} 1 & 1 & 1\ 0 & 1 & 1\ 0 & 0 & *\end{bmatrix}$$
Visual inspection of partial matrix $\mathrm A$ tells us that if the unknown $(3,3)$ entry is $0$, then the rank of the completed matrix is $2$. However, it would be nice not to have to rely on visual inspection.
If the rank is at most $2$, then there are matrices $\mathrm U, \mathrm V \in {0,1}^{3 \times 2}$ such that $\rm A = U V^{\top}$ holds at all known entries of $\rm A$. From the $(1,1)$ entry, we obtain the equation
$$(u_{11} \cdot v_{11}) \oplus (u_{12} \cdot v_{12}) = 1$$
where addition and multiplication are done over the finite field $\mathbb F_2$. 945
Translating the equation above to propositional logic, we obtain
$$\Phi_{11} := \mbox{Xor} \left( u_{11} \land v_{11}, u_{12} \land v_{12} \right)$$
If $a_{ij} = 1$, we have $\Phi_{ij}$. If $a_{ij} = 0$, we have $\neg \Phi_{ij}$. Taking the conjunction of the CNFs of $\Phi_{ij}$ or $\neg \Phi_{ij}$, we obtain the following formula
$$\Psi := \mbox{CNF} (\Phi_{11}) \land \mbox{CNF} (\neg \Phi_{21}) \land \mbox{CNF} (\neg \Phi_{31}) \land \mbox{CNF} (\Phi_{12}) \land \mbox{CNF} (\Phi_{22}) \land \mbox{CNF} (\neg \Phi_{32}) \land \mbox{CNF} (\Phi_{13}) \land \mbox{CNF} (\Phi_{23})$$
which is in CNF by construction. If $\Psi$ is satisfiable, then there are matrices $\mathrm U, \mathrm V \in {0,1}^{3 \times 2}$ such that $\rm A = U V^{\top}$ holds at all known entries of $\rm A$. 677