8
$\begingroup$

This problem appear in my research, but I am unable to solve it. There should be an easy argument, but I have not yet found it.

Informal version An integer $k\geq 2$ is fixed. We are given a matrix (left in image), where each column contains a block with entries in $1,\dotsc,k-1.$ The matrix has the special property that each row sums to a multiple of $k.$ Can we always find some blocks that when we remove $k$ from their (nonzero) entries, all row sums become zero?

Here is the picture to illustrate the problem for an example with $k=5$, where the given matrix is the left one, and the corrected one is on the right.

illustration

Formal version of problem

It may be formulated as follows: We are given an integer $k\geq 2.$ (One may assume it is prime, if it helps).

We fill in columns in a matrix $M$ such that the following holds: Each column $j$ is of the form $(0,0,\dotsc,0,c_j,c_j,\dotsc,c_j,0,\dotsc,0)$ where $0\lt c_j \lt k.$ The sum of each row $j$ in $A$ is of the form $kb_j$ with $b_j$ integer.

Let $A$ be the matrix with 1 at the non-zero positions of $M.$ Then we may write the last requirement as $Ac=kb$ where $c$ is the vector of column values, and $kb$ is the sum of the entries in respectively row.

Now, my question is, can we always find a vector $x\in \{0,1\}^s$ (entries either 0 or 1) such that $A(c-kx)=0$? (This corresponds to selecting a subset of columns in the matrix $M$ such that when $k$ is subtracted from the non-zero elements in them, all row sums becomes zero.

I believe the problem can be reduced to the linear system $Ax=b$ where $A$ and $b$ are as above, and we still seek a vector solution with 0,1 entries. Is there some theory that may tell if this is solvable?

The case $k=2$ is the same as the following setup, if it helps with the image: a finite set of intervals covers [0,1], such that each point is covered an even number of times. Then, we may always color the intervals red and black, such that each point is covered by the same number of black intervals, as red intervals. I have an inductive proof of this special case, but it does not translate to larger $k.$

$\endgroup$
1
  • $\begingroup$ I have made several thousand computer simulations for k=3 and k=5, and in each case, I have found a solution, to I am quite confident that there is no counterexample. $\endgroup$ Jun 4, 2013 at 9:48

1 Answer 1

8
$\begingroup$

The problem is indeed equivalent to solving $Ax=b$ with $x\in\{0,1\}^n$ (for $A$ a matrix of size $m\times n$). To see that this always has a solution, consider the optimization problem $$\text{maximize } \mathbf{1}^TAx\quad \text{s.t. } \begin{pmatrix} -I_n\\\\ I_n\\\\ A \end{pmatrix}x\leqslant \begin{pmatrix} 0\\\\ 1\\\\ b \end{pmatrix}. $$ The constraint matrix is totally unimodular, hence there is an integer optimal solution, i.e. an optimal solution $x^*\in\{0,1\}^n$.

Clearly, $\mathbf{1}^Tb$ is an upper bound for the optimal objective value, which is achieved precisely by the feasible solutions $x$ with $Ax=b$. Now $\tilde x=c/k$ is a fractional solution with objective value $\mathbf{1}^Tb$. This implies $\mathbf{1}^T A x^* =\mathbf{1}^Tb$, thus $Ax^*=b$.

$\endgroup$
1
  • $\begingroup$ Nice proof! Very elegant! $\endgroup$ Jun 4, 2013 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.