# Binary Matrix with constant row and column sum contains a permutation matrix

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.

• You can post your answer as an answer. (See here and here.) – joriki Nov 26 '19 at 22:32

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