Algorithm that finds a matrix with a specific number of 1s in its rows & columns

Question

Question:

Given integer $n \geq 2$ and two lists of size $n$, $A$ and $B$, of non-negative integers, determine if there exists an $n \times n$ matrix whose $i$-th row has $A[i]$ $1$s and whose $j$-th column has $B[j]$ $1$s. If it does exist, then find it.

---

My attempt:

An extremely inefficient algorithm would be to find all possible matrices of size $n \times n$ and check each one. But I'm hoping to find a faster algorithm to do this task? My other thought was to set all the rows randomly such that the condition is satisfed along the rows. And then, starting from $j$ such that $B[j]$ is largest, start swapping elements around along a row to satisfy the column conditions (while keeping the row condition in-tact). However, I have no idea if this actually works, and how I would prove it works if it did.

Please do not give me any explicit solutions or code, but a hint in the right direction would be appreciated. Thank you!

Answer 1

This problem is not easy. The popular website GeeksforGeeks gives an answer that returns the wrong answer, "YES" when row sums are $ [3, 3, 3, 1]$ and column sums are $[4, 4, 1, 1]$.

---

How can we find a set of necessary and sufficient conditions that is easy to compute? How can we produce a wanted matrix if the conditions are satisfied?

One easy condition is that the sum of row sums must be equal to the sum of column sums, since both of them are equal to the total number of $1$s in the binary matrix.

However, that condition is not enough. For example, there is no binary matrix with row sums $[2,0]$ and column sums $[2,0]$. Why? Because a row sum of $2$ means every column of that row is $1$. So, every column sum must be at least $1$.

---

Let us check a much easier problem: given a lists of size $n$ non-negative integers $A$, determine if there exists a $n\times n$ matrix such that the $i$-th row has $A[i]$ $1$s. We can see immediately that if and only if each $A[i]$ is between $0$ and $n$ inclusive, there is such an matrix.

---

A useful property of row sums of a matrix is that if indices are ignored, all row sums as a collection do not change if we switch any two rows or any two columns. The same holds for the column sums. In other words, whether there exists an $n×n$ matrix with given row sums and column sums does not depend on the order of the row sums or the order of column sums. This observation suggests that we may sort the row sums as well as the column sums.

WLOG, let us fix a sequence of valid non-decreasing row sums. The problem now is to find the sequences of all valid non-decreasing column sums. There are a few venues to experiment and contemplate.

• How big or small can the biggest column sum be?
• How big or small can the smallest column sum be?
• Can we reduce the size $n$ by one if the biggest column sum is fixed?
• Can we combine two columns together?
• Compute all binary matrices with given row sums for some small $n$. List the columns sums. Are there any pattern?
• What happens to the first negative example in this answer?

Here is the last and most interesting hint. There is a nice $O(n\log n)$ characterization of the valid sums and a nice algorithm to produce a wanted matrix when the sums are valid.

---

Some hints above may not turn out to be very helpful. Hopefully, these hints can motivate you to continue searching for the right answer.

Be prepared that the right answer might be hard to find even though it could be considered simple. It is reasonable to imagine that I could not figure out an answer in a few minutes or in a few hours or even many months had I been given this problem as well as the hints above when I was a senior student.

Good luck!

---

Answer 2

This problem is equivalent to the bipartite b-matching problem on complete bipartite graphs, where you get a complete bipartite graph $G = (V, E)$ as input and an integral function $b : V \rightarrow \mathbb{N}$ that assigns an integer to each vertex. The goal is to find a subset of the edges $S \subseteq E$ such that $S \cap \delta(v) = b(v)$ for all $v\in V$, where $\delta(v)$ are the edges incident to $v$ in $G$.

The reduction is straight-forward (in both directions). The rows of the matrix correspond to one side of a complete bipartite graph and the columns to the other side.

This problem -similar to bipartite matching- can be easily reduced to the maximum-flow problem by adding a global source and connecting it to one side of the bipartite graph and a global sink and connecting it to the other side.

It is not hard to see the correctness of all previous reductions (the first one in both direction).