# 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. – Nathaniel Johnston May 15 '19 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. – Manfred Weis May 15 '19 at 17:35
• Fixed. I must have been half-asleep when I posted the question. – H A Helfgott May 15 '19 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$. – H A Helfgott Jul 27 '19 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. – Anton Mellit Jul 27 '19 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}$. – H A Helfgott Jul 27 '19 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? – Anton Mellit Jul 27 '19 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$? – H A Helfgott Jul 27 '19 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. – H A Helfgott May 15 '19 at 12:15
• @HAHelfgott Maybe your "true" question is answered by this or this? – Federico Poloni May 15 '19 at 12:21
• @FedericoPoloni Thanks but not really. See above. – H A Helfgott May 15 '19 at 12:33
• OK, updated the question. – H A Helfgott May 15 '19 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$. – Robert Israel May 15 '19 at 12:59