4
$\begingroup$

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$.

$\endgroup$
7
  • 2
    $\begingroup$ 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. $\endgroup$ Jul 7, 2014 at 18:24
  • $\begingroup$ 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 $\endgroup$ Jul 7, 2014 at 19:31
  • 1
    $\begingroup$ 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 $\endgroup$ Jul 7, 2014 at 19:36
  • $\begingroup$ @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). $\endgroup$
    – Anurag
    Jul 8, 2014 at 10:57
  • $\begingroup$ 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. $\endgroup$ Jul 8, 2014 at 11:09

2 Answers 2

4
$\begingroup$

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$.
This can sometimes solve a problem with hundreds of clauses and variables in a reasonable time.

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

$\endgroup$
1
  • $\begingroup$ Thank you. This seems helpful. I will try to see how well it works in my particular problems. I am sure I can exploit the symmetry as well. $\endgroup$
    – Anurag
    Jul 8, 2014 at 11:15
2
$\begingroup$

You may also like to pose this problem as a Closest Vector Problem and use LLL algorithm to solve it.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.