Patterns of zeros in nonsingular $0,1$ matrices

61 Views Asked by At

I am reviving a question that the OP, Svyashennik Sanya, deleted. Since it will not be visible to all users, I restate it here.

It is true that a non-singular $n\times n$ real matrix, all of whose elements are either $0$ or $1$, always has an $(n-1)\times(n-1)$ submatrix with a transversal all whose elements are $0$? By a "transversal" I mean a set of $n-1$ elements comprising one from each row and one from each column of the minor. (The OP used the term "diagonal", but I like "transversal" better.)

I verified this for $n\leq5$ with an exhaustive, brute-force python script. The $n=6$ case would take too long to run. (The OP claimed, in a comment, to have proved it when the the original matrix has a row or column of all $1$'s, but I didn't understand the proof. That comment was deleted before the post was deleted, so I presume the proof was incorrect.)

I don't know if Svyashennik Sanya deleted the question because he or she found a counterexample or a simple proof, or just because no one had answered. (Well, I answered, but I quickly realized that I'd misunderstood the question and deleted my answer.) If the former, and you're reading this, please undelete your question and answer it.

I can't think of any reason why this should be true, but the fact that it's true for $n\leq 5$ gives me pause.

I've been playing with this problem for the last four days, and I've made no progress. Of course, one immediately thinks of the Laplace expansion by minors, but that doesn't seem to lead anywhere.

Any ideas?

EDIT

Perhaps I should mention that one idea I had was to show that a square, $0,1$ matrix with no $0$-transversal is singular. Then all the $(n-1)\times(n-1)$ minors are $0$ and the original matrix has determinant $0$. Sadly, this isn't true. Any $2\times2$ matrix with three $1$'s and one $0$ is a counterexample.

1

There are 1 best solutions below

0
On BEST ANSWER

If $M$ is a nonsingular $n \times n$ matrix and $J$ denotes the $n \times n$ all-ones matrix, then $J - M$ has rank at least $n-1$, so it must have an invertible $(n-1) \times (n-1)$ minor. This minor must have an all-ones transversal, which translates to an all-zeroes transversal in a minor of $M$.