# Finding the set of all $0$-$1$ vectors in an affine subspace

We are given a $0$-$1$ matrix $A$ with constant row and column sum, and we need to find out if there exists a $0$-$1$ vector in the solution space of $Ax = \mathbf{1}$ over $\mathbb{Q}$ (or $\mathbb{Z}$) where $\mathbf{1}$ is the all $1$ vector. If there exists such a binary vector then we would like to compute all of them or at least comment on the total number.

Are there any theoretical results in this direction? If not, then can we compute this without going through all $2^n$ possibilities where $n$ is number of columns of $A$?

In full generality it seems to be an NP-complete problem as pointed out here: https://mathoverflow.net/a/97140/34180. So, assume that $A$ is the incidence matrix of a highly symmetrical incidence structure whose full automorphism group is known.

Edit: If the row sum is $r$ and column sum $s$ then this can be interpreted as finding perfect matchings in an $s$-uniform $r$-regular hypergraph. The smallest case I am interested in is a $5$-uniform $5$-regular linear hypergraph (at most one edge through every pair of vertices) which has $1365$ edges (and the same number of vertices). Its full automorphism group is $G_2(4):2$ of order $503193600$.

• For a finite projective plane (whether classical or not) there can't be any solution, because you're asking for a set $S$ of points that meets every line in just one point, but then $|S|>1$ and the line through any two points of $S$ yields a contradiction. – Noam D. Elkies Jul 7 '14 at 18:24
• Also, the column sum better divide the number of rows of the matrix, otherwise you're stopped at the starting gate. Given the quotient q, one is "reduced" to n choose q possibilities. Gerhard "Divide And Conquer Also Works" Paseman, 2014.07.07 – Gerhard Paseman Jul 7 '14 at 19:31
• If you want to take advantage of symmetry, then you can shave off an order of magnitude or more running time by looking at just isomorphism types of structures built from a few columns. If there is a solution, there will be "lots" of them, and Robert Israel's suggestion has a chance of finishing quickly. Gerhard "Ask Me About System Design" Paseman, 2014.07.07 – Gerhard Paseman Jul 7 '14 at 19:36
• @NoamD.Elkies: Thank you for pointing it out. I should have put a better example. The particular ones that I am working with are generalized polygons. For example, if you look at the flag geometry of classical projective plane of order $q$ then you get a generalized hexagon of order $(q,1)$ which certainly has such a solution (corresponding to a perfect matching in the incidence graph of the projective plane). – Anurag Jul 8 '14 at 10:57
• I can’t say I know anything about incidence geometry, but if your problem amounts to finding perfect matchings as your last comment suggests, there are efficient polynomial-time algorithms for that. – Emil Jeřábek Jul 8 '14 at 11:09

Even though it is NP-complete, you can do a lot better than searching through all $2^n$ possibilities. In practice, you might try a SAT solver, with the clauses $\bigvee_{j: A_{ij} = 1} x_j$ for each row $i$ and $\overline{x_j} \vee \overline{x_k}$ for each pair $(j,k)$ such that for some row $i$, $A_{ij} = 1$ and $A_{ik} = 1$.
Counting or estimating the number of solutions (in a case where that number is not $0$) might be more difficult. See e.g. #-P-complete
Namely, if matrix $A$ has size $m\times n$, multiply it by sufficiently large constant $c$ and extend it at the bottom with an $n\times n$ identity matrix $I$ to get matrix $B=\left[\frac{c\cdot A}{I}\right]$ of size $(m+n)\times n$. Now, if $Ax=\mathbf{1}$, then $Bx$ represent a vector close to the vector $\left[\frac{c\cdot \mathbf{1}}{\mathbf{0}}\right]$. So it is worth to solve CVP for matrix $B$ and vector $\left[\frac{c\cdot \mathbf{1}}{\mathbf{0}}\right]$.
A vector $x$ obtained from solving this CVP problem will have small components, while the choice of $c$ ensures that it satisfies $Ax=\mathbf{1}$. It is not guaranteed to have 0-1 components, but you may be lucky.