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?

  • 1
    $\begingroup$ 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. $\endgroup$ May 15 '19 at 12:13
  • $\begingroup$ 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. $\endgroup$ May 15 '19 at 17:35
  • $\begingroup$ Fixed. I must have been half-asleep when I posted the question. $\endgroup$ 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<i_n$ and $j_1<\ldots<j_n$.

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

  • $\begingroup$ 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$. $\endgroup$ Jul 27 '19 at 9:58
  • $\begingroup$ No, in fact the statement in characteristic 2 is false: take the 4x4 matrix with 0 on the diagonal and 1 elsewhere. $\endgroup$ Jul 27 '19 at 14:45
  • $\begingroup$ Hm. I wonder what it is that goes wrong? The change I just mentioned does seem to remove the factor $2^{-n}$. $\endgroup$ Jul 27 '19 at 17:59
  • $\begingroup$ "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? $\endgroup$ Jul 27 '19 at 21:23
  • $\begingroup$ 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$? $\endgroup$ 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.

  • $\begingroup$ Ah, thanks, that was silly of me. Let me try to see whether I can improve the question. $\endgroup$ May 15 '19 at 12:15
  • $\begingroup$ @HAHelfgott Maybe your "true" question is answered by this or this? $\endgroup$ May 15 '19 at 12:21
  • $\begingroup$ @FedericoPoloni Thanks but not really. See above. $\endgroup$ May 15 '19 at 12:33
  • $\begingroup$ OK, updated the question. $\endgroup$ May 15 '19 at 12:43
  • 1
    $\begingroup$ 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$. $\endgroup$ May 15 '19 at 12:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.