# Binary matrix with columns sums equal to an array numbers, with unique rows sums

I have this input array:

[5, 3, 2, 4, 1, 3, 4]


and want to build binary matrices where sums of each column equal to the coresponding input array elements.

The matrix is of size 7 x 5.
The sums of rows create an array of numbers (of size 5 in this case). So I need to generate different combinations of columns so that the arrays of rows sums are uninque.

The initial matrix is this:

$$\begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{matrix}$$

And the rows sums arrays will be

[7, 6, 5, 3, 1]


I understand that I could create all possible permutations for each column and then take only the unique rows sums arrays (like [7, 6, 4, 3, 2], [6, 6, 5, 3, 2]).

But could someone give an advice on how could it be optimized, or if there's an algorithm for this?

Thanks.

• So you want to find all possible (distinct) arrays of row sums given an array of column sums? – Arthur Aug 15 '18 at 16:46
• Well I'd like to have the corresponding matrices too (to know which columns are 0's an 1's). But at least row sums arrays would be fine too. – mortalis Aug 15 '18 at 16:54

## 1 Answer

Perform permutations only on unique column sum values. In the case of [5,3,2,4,1,3,4], you would want to perform permutations on the columns which are in bold: [5,3,2,4,1,3,4], and keep the last 2 columns fixed in all your permutations.

Next, take the set of complementary columns: The columns where your column sum values add up to the total number of rows. In this case, column sum values [3,2] and [4,1] are complementary. While performing permutations for those columns, you would want to avoid multiple occurrences of rows sum matrix having all values 1.

For example if all permutations of [3,2] are performed, there would be 5C2 occurrence of row sum matrix = [1,1,1,1,1] corresponding to only those 2 columns.

So, if you avoid that particular duplicate, I guess this method should work.

• Thanks for your advice. I'll definitely give it a try. – mortalis Aug 17 '18 at 18:36