Diagonal in full column-rank binary matrix

Question

Suppose you have a full column-rank square matrix whose entries are either $0$ or $1$. Is it always possible to shuffle the columns of this matrix such that the diagonal of the new matrix produced by this shuffling consists entirely of $1$’s?

Answer 1

Hint

Consider the determinant of your matrix $A$, written the sum over all permutations $\pi$ of $\{1,\dots,n\}$ of $$ (-1)^{\text{sign } \pi}a_{1,\pi(1)}a_{2,\pi(2)}\cdots a_{n,\pi(n)} $$ Can it be the case that all of these summands are zero?

Answer 2

Hints.

Let $S_i$ consist of the numbers of those columns that have $1$ at the $i$-th place.

1. Prove that $|S_{i_1}\cup\ldots\cup S_{i_k}|\geq k$ for any integer $k$ $(1\leq k\leq n)$ and any $1\leq i_1<\ldots<i_k\leq n$. (Here $n$ is the order of the given matrix.)

2. Use Philip Hall's theorem on a system of distinct representatives (see, for example, M. Hall's book 'Combinatorial Theory', Theorem 5.1.1).