# Invertible matrix subtracted by permutation matrices

Sorry for the vague title, but I do not know how to describe the question briefly. If any improvements are possible please edit.

Given an arbitrary invertible matrix $$A$$ whose entries contains only $$0$$ and $$1$$, can we always find a permutation matrix $$P$$ such that $$A-P$$ also has non-negative entries? Equivalently, can we show that there always exists a permutation $$\sigma$$ such that $$A_{i,\sigma(i)}$$ are all nonzero?

When the number of $$1$$s exceeding $$n$$ is not so much, simple pigeon-hole argument can prove the case. However general cases seem to be too complecated to me. (Or the question is stupid and pigeon-hole can indeed do the job.)

There are similar posts on the site like

Characterizing sums of permutation matrices

but I am not familiar with the methods applied there so I failed to adapt them.

Bonus: Is the statement true for arbitrary matrices with nonnegative integral entries?

Any help would be appreciated.

Suppose that no such permutation exists. That is, for every permutation $$\sigma$$, $$A_{i,\sigma(i)} = 0$$ for at least one value of $$i$$. It follows that $$\prod_{i=1}^n A_{i,\sigma(i)} = 0$$ for every permutation $$\sigma$$. Thus, with the Leibniz formula for determinants, we find that $$\det(A) = \sum_{\sigma \in S_n}\text{sgn}(\sigma)\prod_{i=1}^n A_{i,\sigma(i)} = \sum_{\sigma \in S_n}\text{sgn}(\sigma)\cdot 0 = 0.$$ Thus, $$A$$ has determinant $$0$$ and is therefore not invertible.