Vanishing patterns of minors of matrix

Question

Let $M$ be a $m\times n$ matrix with entries in, say $\mathbb{C}$; assume $n\leq m$. Denote by $I\subseteq\{1,2,\ldots, n\}$ a subset of the columns of M. I am interested in positive results to the following (admittedly not very precise) problem:

Let $M_I$ be the submatrix of $M$ formed by its columns labelled by $I$. Suppose we know which maximal minors of $M_I$ vanish; what are the possible vanishing patterns for the maximal minors of submatrices $M_{I'}$ where $I\subset I'\subseteq \{1,2,\ldots, n\}$. I would also be satisfied with answers relating just the number of vanishing maximal minors of $M_I$ and $M_{I'}$ (as opposed to the precise pattern of vanishing).

I know the answer is related to relations among minors of a generic matrix, as partially discussed here, for instance, but I am looking for precise references or information concerning my question.

Answer 1

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.

• Note too that for $j=1$ and $n=2$ we can do column operations on $M$ without changing which minors of $M$ vanish. Each all $0$ row , if any, will always leave a $0$ in column $1$ but otherwise we can arrange to have no other $0$ entries or to have the $0$'s indicate the all $0$ rows along with any other one equivalence class.

• For $j \gt 1$ I will just say that any $j$ rows of $M$ with span of dimension less than $j$ give a vanishing minor in $M_{I'}.$ I think one could show that by column operations in $M$ (which have no effect on which minors of $M$ vanish) we could arrange to have no other minors of of $M_I$ vanish.