# Algorithm to find if there are N 1's in a matrix where no two 1's are in same row or column

I am trying to find an algorithm to determine whether a $$N\times N$$ matrix of ones and zeroes could have a sublist of ones, such that in that sublist we have only one $$1$$ from each row or column.

## 1 Answer

This is the perfect matching problem in a bipartite graph: construct a bipartite graph with nodes $$1,...,N$$ on one side and nodes $$-1,...,-N$$ on the other side, and with an edge from $$i$$ to $$-j$$ if your matrix has a 1 in row $$i$$, column $$j$$. Then a perfect matching in this graph corresponds to a subset of ones in the matrix having the property that no two of them are in the same row or column.

## Textbook algorithm

The Hopcroft-Karp algorithm solves the problem; it can determine if a perfect matching exists in time $$O(\sqrt{N} M)$$ where $$M$$ is the number of ones in your matrix (clearly, $$M \le N^2$$).

## A simpler randomized algorithm

If you are satisfied with a randomized algorithm (with a small probability of error), there is indeed a conceptually simpler algorithm due to László Lovász. Create a new matrix $$X$$ in which every 1 in the original matrix is replaced by a random integer between 1 and some bound $$P>100 \cdot N$$; zeros in the original matrix remain zeros in $$X$$. Compute the determinant of $$X$$. If $$det(X) \neq 0$$, then for sure the original matrix has a perfect matching; if $$det(X) = 0$$, then with probability at least $$1-1/100$$, the original matrix does not have a perfect matching. (If you want to be sure that the value of the determinant does not overflow, you can do the computations modulo $$P$$ if you choose $$P$$ to be prime.) Computing the determinant will take time $$O(N^3)$$ with standard decomposition methods.

## An even simpler (and slower) method

The simplest polynomial-time algorithm I know for bipartite perfect matching is due to Linial, Samorodnitsky and Wigderson and runs in time $$O(N^4 \log N)$$. Let $$c_j$$ denote the sum of the elements in column $$j$$. The algorithm is as follows:

For $$N^2 \log N$$ iterations do:
1. Normalize each column so that it sums to 1
2. Normalize each row so that it sums to 1
3. Compute $$c_1,\ldots,c_N$$
4. If $$\sum_{j=1}^N (c_j-1)^2 < 1/N$$ return YES
Return NO

## If $$N$$ is tiny

If you want something even simpler (?) to implement (but much, much slower if $$N$$ is large), you could just enumerate all permutations over $$N$$ elements, and for each of these check if the corresponding set satisfies your property. That is, for each permutation $$\pi: \{1,\ldots,N\} \to \{1,\ldots,N\}$$, you check if cell $$(i, \pi(i))$$ of the matrix contains a 1, for each $$i=1,\ldots,N$$. The standard libraries of some programming languages have support for generating all permutations of a set; for example, itertools.permutations in Python or next_permutation in C++. However, this approach based on enumeration will take time about $$N \cdot N!$$, which is more than exponential in $$N$$. It will probably only be acceptable if $$N$$ is at most around 10-12.

• Is there anything simpler? I am not trying to find a the set. Just to know if exists or not. Jan 22, 2019 at 17:00
• I updated my answer with two simpler methods. Anyway, I would not say Hopcroft-Karp is hard to implement. Jan 22, 2019 at 18:05