0
$\begingroup$

The following problem was given as a homework problem, so I am not necessarily asking for a full solution, but rather a good hint on where to start.

A chess board, where some of the $64$ cells contain a piece, has the property that every row and every column contains $3$ pieces exactly. I need to show that one can remove some pieces, such that the resulting matrix has exactly one piece in every row and every column.

I feel like this must have an easy solution, but I have not been able to guess it. To give a little bit of context, this problem was given in relation to totally unimodular matrices and integrality of polyhedra.

$\endgroup$
  • 1
    $\begingroup$ You can post your answer as an answer. (See here and here.) $\endgroup$ – joriki Nov 26 at 22:32
0
$\begingroup$

I believe I actually found a possible solution myself. By identifying the matrix as a (3,3) biregular graph with 8 vertices on each side of the bipartition, one can see that there is a noninteger solution for the equations

$$x(\delta(v)) = 1 \ \forall v \in V$$ $$x(e) \geq 0 \ \forall e \in E$$

By Birkhoff's theorem, the set of solutions to these equations equal the perfect matching polytope, therefore there exists a perfect matching of our graph and hence a configuration of the chess board, which resembles a permutation matrix.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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