Skip to main content
3 of 4
added 1853 characters in body
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

This seems like a matroid question but I'll take an elementary approach. It may be that my remarks just knock off the easy observations. I don't think anything changes if you switch to $\mathbb{Z}$ although fields of finite characteristic are different. We may as well assume that $M_{I'}=M$ and that $M_I$ is the $j$ leftmost columns.

So we have a set $S=\{{v_1,v_2,\cdots,v_m\}}$ of $m$ symbols and a family $\mathcal{F}$ of $n$-subsets from $S$. We wonder when there is a way to assign the $v_i$ to be $m$ row vectors from $V=\mathbb{C}^n$ so that $\mathcal{F}$ is exactly the bases for $V$ made from $S.$ That is an interesting question in and of itself. But you to think of the $v_i$ as rows of a matrix $M$ (so the question is equivalent to which minors vanish and which don't) and wonder what more can we say given the additional information from $M_I?$

Whatever is true for $M_I$, it could be that there are no bases from rows of $M$ (i.e. all minors vanish). If so, that is the end of it. Otherwise we can call a subset of $S$ independent if it is a subset of a basis. Then it is required that given an independent set $T$ of size $k$ and a basis $B$, there is a basis made up of $T$ and some $n-k$ elements from $B$. So that is a non-trivial restriction and it applies to the information that we are provided about $M_I.$ However there are families $\mathcal{F}$ which meet this requirement and can be realized by matrices over $\mathbb{Z}_2$ but not over $\mathbb{C}$ and also families which can not be realized by a matrix over any field.

Assume $M_I$ is the first $j$ columns. It will follow from below that

(*) if every minor for $M_I$ vanishes, the same is true for $M$ and that

(* *) otherwise we may assume that the top minor of $M_I$ is the $j \times j$ identity matrix and

(* * *) that we know which entries of $M_I$ are zero and that the leading non-zero entry of each row is a $1.$

I don't actually make use of these last two but they are helpful to think about.


  • If $j=1$ then we know which entries in column $1$ are zero. A minor of $M$ with all zero in the first column will vanish. Any other first column might or might not lead to a non-zero minor.

  • In general, a minor for $M$ with all leftmost $j \times j$ minors vanishing also vanishes (hence (*)). What else can one say? I argue below that the answer is nothing more for the case $n=2.$ Otherwise I can think of a bit more, but not much.

Column operations on $M_{I'}$ will affect the values of the minors but not which ones vanish. And permuting the rows is just a relabelling which does not change the problem. Hence (* * ). And then just the minors which use $j-1$ of the top $j$ rows will tell you the rest of (* * *) since multiplying a row by a (non-zero) constant does not change anything.

  • What about the case $n=2?$ We can represent the family $\mathcal{F}$ by a graph with $m$ nodes labelled $v_1,\cdots,v_m$ (or unlabeled) and an edge for each putative basis. Then before including the information from column $1$ (aka $M_I$) we can say that the graph must be a complete multipartite graph possibly with some isolated vertices (call two non-zero rows equivalent if each is a multiple of the other, then the edges connect precisely the non-equivalent pairs.) Now the additional information from $M_I$ is which entries in column one are zero and which are not. The isolated vertices (if any) must come from the rows with a leading zero and the remaining rows (if any) with a leading zero form an equivalence class for the graph. Other than that the remaining classes can be anything.

  • About the case $n \gt 2$ I will just say that the information about $M_I$ tells us not only which $j \times j$ sub-matrices are nonsingular, but also the rank of any set of rows from $M_I.$ So if we choose $n$ rows with rank $j$ (the maximum possible rank) then the corresponding rows of $M$ might or might not be a basis, however it definitely won't be a basis if the rank is less than $j$.

Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104