# An algorithm for creating a matrix with certain properties

I'm searching for an algorithm that efficiently does the following

Input:

• $n\in \mathbb{N}$
• $j_1,j_2,\ldots ,j_n$ with the property $j_1<j_2<\cdots<j_n$
• $b_1,\ldots ,b_n \in \mathbb{N}$
• $m\geq b_1+\cdots+b_n$

Output: a Matrix of $n\times m$ with the property described bellow:
To be more precise, I have a special case of an $n\times m$ matrix ($n$ is given, $m$ has a bounded lower value equal to $b_1+b_2+\cdots+b_n$ but we can choose it to be arbitrary large if we like).

We are also given a series of coordinates $j_1<\cdots<j_n$ that each defines a position in line 1,2 etc. For example if $j_1=3$ then the postion $(1,3)$ of the matrix. Matrix elements are 0 or 1 under the constrain that each column can have at most one 1 and each line $i$ exactly $b_i$ 1s.

From all the possible matrices we're interested in finding one ( one certainly exists) that has the the following property:

$\max\{|j_k-\mathrm{positionOf}(1)|, k= 1,\ldots,n$ and for all 1 appearing on each of the $i_k$ line$\}$ is the lowest of all the other possible matrices. Less formal, I want to find one of the matrices that minimizes the biggest distance of '1' from $j_k$ for all $j_k$.

Is there an algorithm (preferably of linear complexity) to find such an array? My best effort so far solves it in polynomial time but it's really a brute force solution and not very applicable.

Thank you in advance.

• Your write-up is not clear enough. By $i_k$ "line" are you talking about the kth row of your matrix? You name a lot of the elements of your problem but neglect to give a symbol for the matrix itself. This is an optimization problem, if I understand it, so asking for a linear time search for the optimal matrix seems to be ambitious. – hardmath Nov 29 '12 at 14:37
• Are you searching for the best matrix only? Will good approximation (not best) be enough? – Egor Skriptunoff Nov 29 '12 at 14:44
• The things perpendicular to the columns are usually called rows, not lines. (It's the same word for both in German.) I agree that "$k$-th row" instead of "$i_k$ line" would make more sense; everything else seems clear enough to me (if sometimes somewhat unorthodox). – joriki Nov 29 '12 at 14:55
• Of course, I mean row of the matrix not line. I'm only interested in the max value of the optimal matrix described above. – EQ1 Nov 29 '12 at 15:11
• As for searching for the best matrix, brute-force time complexity is not greater than O((max distance from $j_k$ to 1)*(sum of all $b_k$)). Is it not enough? – Egor Skriptunoff Nov 29 '12 at 15:13

## 1 Answer

Algorithm for searching the best value of max distance from $j_k$ to 1

dist = -1
repeat
dist = dist + 1
pos = -infinity
success = true
for k = 1 to n
pos = max(pos, j[k] - dist)
pos = pos + b[k]
if pos > j[k] + dist + 1 then
success = false
terminate the execution of "for" loop
end-if
end-for
until success
print(dist)

• +1 for getting the complexity bounded, but I don't think your loop properly accounts for the possibility that intervals [j[k]-dist,j[k]+dist] may overlap. – hardmath Nov 29 '12 at 20:49
• @hardmath - I think my algorithm is correct. (Do you have counterexample?) It relies on left justified filling to properly handle possible overlapping. – Egor Skriptunoff Nov 29 '12 at 22:40
• It is easy to prove this statement: If matrix exists for some "dist" value, then it can be transformed to left-justified form preserving it's "dist" value, so that matrix looks like a ladder, i.e., all "1" on k-th row located to the left of all "1" on (k+1)-th row. Thus, only left-justified matrices should be brute-forced. This is the idea of the algorithm. – Egor Skriptunoff Nov 29 '12 at 23:13
• That's the right idea, I have no doubt. I'm posting from my cellphone and will give an example when I get home. – hardmath Nov 29 '12 at 23:31
• Let's assume (the OP doesn't specifically say) that the j[k] are positive integers (though the example given is, j=3); also the column indexes are necessarily positive integers. I guess my change comes down to initializing pos=1 rather than -infinity. Given dist, then the first available position in row 1 is pos = max(pos,j-dist). After left-filling b ones, the next "empty" position is in pos+b, and I agree with how you test for failure (and update pos), and the for-loop continues. – hardmath Nov 30 '12 at 1:03