0
$\begingroup$

I need to construct an $m \times n$ binary matrix $B$ from a given row and columns distribution. What algorithms can be used for this? As a concrete example : $B$ a $12 \times 63$ matrix with row distribution $12 r^{19}$ and column distribution $12 c^2 + 39 c^3 + 9 c^7 + 3 c^8$. That is all $12$ rows have weight $19$; $12$ columns have weight $2$, $39$ columns have weight $3$, $\cdots$, $3$ columns have weight $8$. The weight of binary row or column is its sum or equivalently the number of nonzero entries. (This comes up in LDPC code constructions; the example is from LDPC Code Designs (2017), page 38)

$\endgroup$

2 Answers 2

3
$\begingroup$

One approach is to use integer linear programming (ILP) as follows. Let $r_i$ and $c_j$ be the desired row and column sums, respectively. Let binary decision variable $B_{i,j}$ be the entry in row $i$ and column $j$. The constraints are \begin{align} \sum_j B_{i,j} &= r_i &&\text{for all $i$}\\ \sum_i B_{i,j} &= c_j &&\text{for all $j$}\\ \end{align} Branch-and-cut is the most common algorithm for ILP, but it turns out that for your problem the linear programming relaxation always yields an integer solution. This particular problem is known as the transportation problem, with a supply node for row $i$ and a demand node for column $j$, and the variable $B_{i,j}$ represents the "flow" from node $i$ to node $j$. Usually the transportation problem has a linear objective function $\sum_{i,j} c_{i,j} B_{i,j}$ to be minimized, but yours is a feasibility problem; you can think of this as taking $c_{i,j}=0$ as the cost.

For your sample data, here is one such matrix:

1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
1 0 0 1 1 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 
0 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 1 0 1 1 1 1 1 1 1 
0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 
0 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 
$\endgroup$
1
  • $\begingroup$ Thanks for the answer. ILP seems like a good way to solve the problem. Using matlab's "intlinprog" I get the answer in a few seconds. $\endgroup$
    – unknown
    Commented Jan 4, 2022 at 17:36
2
$\begingroup$

Here is a very easy way to get the matrix.

First, make $12$ columns of weight $2$. You start from $B_{0,0}$ and color 2 consecutive cells downward in the $C_0$. And the you go to the next column AND the next row ($B_{r+1,c+1}$) and color 2 cells downward from there.

After you're done with the 6th column ($C_5$), you are at the bottom row. And then for the next column, you go back to the top row. And keep going. Luckily, until the $C_{50}$ you can keep doing this way, because both $2$ and $3$ divides $12$. You're done with $12c^2 + 39c^3$ so far.

The problem first happens on the $C_{51}$ where you should color $7$ cells, because you get to the bottom row ($B_{11,51}$)when you colored only $3$ cells. Then you should go to the top row while staying in the same column ($B_{0,51}$). Once you colored all $7$ cells, you go to the next column and the next row. And then you can continue this way until the end.

The below matrix is the outcome of the above procedure.

enter image description here

$\endgroup$
1
  • 1
    $\begingroup$ Thanks for the answer; I can see how this would work. Using matlab's ILP was less work than coding the above so I went with that. Interestingly enough the answer looks very similar to what you have (column weight increases from left to right...) $\endgroup$
    – unknown
    Commented Jan 4, 2022 at 17:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .