# Does a non-singular matrix have a large minor with disjoint rows and columns and full rank?

Say I have an $$n$$-by-$$n$$ non-singular matrix $$A$$ all of whose diagonal entries are $$0$$. We call an $$m$$-by-$$m$$ minor of $$A$$ good if its set $$I$$ of row indices and its set $$J$$ of column indices ($$I,J\subset \{1,2,\dotsc,n\}$$) are disjoint. Can one give a good lower bound on the size $$m$$ of the largest non-singular good minor of $$A$$?

(Perhaps $$m = \lfloor n/2\rfloor$$?)

EDIT: All right, so obviously there aren't enough conditions - the answer is too easy. What if $$A$$ is antisymmetric?

• If I understand correctly, $m = \lfloor n/2 \rfloor$ is not possible (at least when $n$ is even), as evidenced by the matrix with $0$ on the diagonal and $1$ everywhere else. Commented May 15, 2019 at 12:13
• is it intended that in the question both $I$ and $J$ are sets of column indices? I suppose $I$ is the set of row indices. Commented May 15, 2019 at 17:35
• Fixed. I must have been half-asleep when I posted the question. Commented May 15, 2019 at 17:38

I am assuming the question is for antisymmetric matrix. Then $$n$$ is even. The claim follows from the properties of Pfaffian (see wikipedia):

If $$M$$ is $$2n$$ by $$2n$$ anti-symmetric matrix, then $$\det(M)=Pf(M)^2$$, where

$$Pf(M) = 2^{-n} \sum_{I\sqcup J=[1,2n]} \pm \det(M_{I,J})$$,

where $$I, J$$ specify partition of the set $$\{1,\dots,2n\}$$ into two subsets of size $$n$$. For each such partition we take the corresponding minor. The sign is the sign of the permutation $$(i_1,j_1,i_2,j_2,\dots,i_n,j_n)$$ where $$I=\{i_1,\dots,i_n\}$$ and $$J=\{j_1,\dots,j_n\}$$ so that $$i_1<\ldots and $$j_1<\ldots.

If all the minors were zero, then the Pfaffian would be zero.

• A small addition: it's easy to derive a modified version of the expression for the Pfaffian given here so as to avoid negative powers of $2$, so the argument here would seem to work even in characteristic $2$. Commented Jul 27, 2019 at 9:58
• No, in fact the statement in characteristic 2 is false: take the 4x4 matrix with 0 on the diagonal and 1 elsewhere. Commented Jul 27, 2019 at 14:45
• Hm. I wonder what it is that goes wrong? The change I just mentioned does seem to remove the factor $2^{-n}$. Commented Jul 27, 2019 at 17:59
• "it's easy to derive a modified version of the expression for the Pfaffian given here so as to avoid negative powers of 2", what do you mean by that exactly? Commented Jul 27, 2019 at 21:23
• Well, can't you write the Pfaffian as $\sum^*_{I\sqcup J} \pm \det(M_{I,J})$, where the sum $\sum^*$ is taken over all partitions into sets $I=\{i_1,\dotsc,i_n\}$, $J=\{j_1,\dotsc,j_n\}$ such that not only $i_1<\dotsc<i_n$ and $j_1<\dotsc<j_n$ but also $i_r<j_r$ for all $1\leq r\leq n$? Commented Jul 27, 2019 at 22:26

The matrix with zeroes on the diagonal and ones everywhere else is nonsingular, but all its "good" minors of size bigger than 1 are singular, since they have all entries equal to 1.

• Ah, thanks, that was silly of me. Let me try to see whether I can improve the question. Commented May 15, 2019 at 12:15
• @HAHelfgott Maybe your "true" question is answered by this or this? Commented May 15, 2019 at 12:21
• @FedericoPoloni Thanks but not really. See above. Commented May 15, 2019 at 12:33
• OK, updated the question. Commented May 15, 2019 at 12:43
• If $A$ is antisymmetric and nonsingular, $n$ must be even. In the case $n=4$ I can confirm that there must be a good minor of size $2$. Commented May 15, 2019 at 12:59