How many minors I need to check to conclude all minors will vanish ?

Question

Given a $m \times n$ matrix $n>m$, I was trying to check if all its $m \times m$ minor vanish.

I remember hearing that one really does not need to check all possible minors in order to conclude that all of them would vanish.

If such a result is true, how many minors will do the job and which ones ?

I am wondering if it is even possible to calculate the value of all minors based on the value of a nicely chosen "generating subset" ?

---

Edit:- The question which I had asked does not have an affirmative answer as explained
by Steven Sam. But matrix minors do satisfy some relationships see the answer by Sheikraisinrollbank below. If someone can modify the question to a more appropriate one (in light of Steven Sam and Sheikraisinrollbank answers ) please feel free to do so.

I have often come across a situation (more so at present than ever before) where in order to answer a problem in my subject area I am led to questions which are totally different areas about which I have absolutely no familiarity. Most often these are quite basic and I would suppose well known to any one who works in those areas. It is natural that a person who is not familiar with a given field will end up asking for "a result of the following kind" rather than a precise question. For a person who is knowledgeable I understand the question may be irritating or look ill posed but mind you the hapless fellow is not a graduate student in the given field and please do not judge him accordingly. I think its desirable that if someone knows how to reformulate the question to something so that it becomes well posed or meaningful it should be done. Why not edit the question to something so that it becomes a valid well posed question, to something which is obviously much more interesting than which was originally posed ?

Answer 1

To counterbalance Steven Sam's answer some (b/c the OP's intuition is correct in a sense):

It's true that the right way to check that all m by m minors are zero in practice is Gaussian elimination. However, while the minors may be linearly independent, they satisfy quadratic relations ("Plucker relations", see for instance the wikipedia article on Grassmannians) that allow you to deduce some things. In the simplest non-trivial case of 2 by 4 matrices, writing $m_{ij}$ for the $(i,j)$th $2$ by $2$ minor one has $$m_{12}m_{34}-m_{13}m_{24}+m_{14}m_{23}=0.$$ This might have some theoretical value for the OP's situation that Gaussian elimination does not. For instance, in this case it allows one to deduce that if $m_{12}$ and $m_{13}$ are both zero then either $m_{14}$ or $m_{23}$ is zero. But it's hard to know if this helps without knowing somewhat more about the motivating problem.

Answer 2

The other answers and comments provided examples where all but one of the minors vanish, so you see that you need to check all of them. Let me put this in different context. Define the $m \times n$ generic matrix $X$ over a field $k$ (or a commutative ring) to have its entries $x_{i,j}$, where the $x_{i,j}$ are variables in a polynomial ring $k[x_{i,j}]$. The determinantal variety of this matrix is the ideal generated by the $r \times r$ minors ($r$ being the size you're interested in).

Your question amounts to asking if these $\binom{m}{r} \binom{n}{r}$ generators are linearly independent (over $k$) and if they generate a radical ideal. Let me at least frame the linear independence issue using some representation theory. It's definitely overkill, but I think it's an instructive way to think about trying to find equations when you have a large amount of symmetry. There is an action of $G = {\bf GL}_n(k) \times {\bf GL}_m(k)$ on the generic matrix via $(A,B) \cdot X = AXB^{-1}$ which preserves rank. Hence the set of conditions for this matrix to have rank $< r$ must be preserved by $G$. We can rewrite $k[x\_{i,j}]$ as $k[V^* \otimes W] \cong {\rm Sym}(V \otimes W^\*)$ where $V$ and $W$ are $k$-vector spaces of ranks $m$ and $n$, respectively. The $r \times r$ minors are polynomials of degree $r$, hence sit inside of ${\rm Sym}^r(V \otimes W^\*)$. In fact, they must span a $G$-submodule. Furthermore, this $G$-submodule is $\bigwedge^r V \otimes \bigwedge^r W^\*$ (which can be seen in various ways), which we know has dimension $\binom{m}{r} \binom{n}{r}$. Hence they are linearly independent (as polynomials over $k$). This explains why you will always find examples where all but 1 of the minors can vanish (when we specialize the $x_{i,j}$ to specific values in $k$).

As to why the ideal is radical, one can see this using the theory of Gröbner bases. (I'll freely make use of language from that theory.) Specifically, if one uses an antidiagonal term order (an ordering of the variables for which the antidiagonal term is the leading term for each $r \times r$ minor; take for example $x\_{1,1} > x\_{1,2} > \cdots > x\_{1,n} > x\_{2,1} > x\_{2,2} > \cdots > x\_{2,n}> \cdots > x\_{n,n}$), then the $r \times r$ minors form a Gröbner basis for the ideal they generate. See Theorem 16.28 of Miller and Sturmfels, Combinatorial Commutative Algebra, or also Corollary 4.10 of Sturmfels and Sullivant, "Combinatorial secant varieties" for a different proof. So the initial ideal is radical because it is generated by squarefree monomials, and this implies that the original ideal is radical.

But practically speaking, for determining the rank of a matrix, you should do Gauss-Jordan elimination. That would be faster.

Answer 3

For any set of $(j_i)_{i=1}^m$, with $1\le j_1 < \cdots < j_m \le n$, let $A$ be the matrix with elements $A_{ij} = \delta_{ij_i}$. Every minor except the one defined by the columns $j_i$ vanishes, so in order to ensure that every minor vanishes you would have to check all of them.

Answer 4

Whenever you take $m+1$ columns in your matrix, there are $m+1$ different minors you can form from those columns. If $m$ of those vanish, the $(m+1)$-st does too, and more generally you can compute the $(m+1)$-st from the other $m$.

In order to see this, add one of the rows you already have to form a square matrix. It's determinant is 0, and knowing this gives you a relation between those minors by expanding along the row you added. If the rank of your matrix is exactly $m$, I don't think you can improve this, or not by much anyway. If the rank is smaller, of course, that's another story.

This is related also to Determinantal Varieties, though you would need to ask someone more knowledgeable than me about the details.