# 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

## 1 Answer

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.