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

Question

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.

Answer 1

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.