Invertible matrix subtracted by permutation matrices

Question

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.

Answer 1

The answer is yes. The simplest approach is to use the determinant. Here's a proof by contrapositive.

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.

The conclusion follows.

Regarding your "bonus" question, the same approach works for matrices with non-negative integer entries.