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

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" ?

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 ?

-
Take a $2\times n$ matrix $A$ with all entries 0 except $A_{1,1}=A_{2,n}=1$. –  Cam McLeman Oct 28 '10 at 12:53
I know that's kind of a worst case scenario. I am hoping when $m$ and $n$ are comparable, for example when $n=m+1$ or $m+2$ one can do much better. I feel there is a lot of redundancy in these cases. –  Vagabond Oct 28 '10 at 13:01
What? No, that worst case is always there to deal with. Take an mxm identity matrix and fill in the rest of the mxn matrix with zeroes. –  Tom Goodwillie Oct 28 '10 at 13:27
You guys are being somewhat too hard on Vagabond. I'm suprised nobody mentioned Plucker relations right away; they'll obviously help him/her understand. –  Sheikraisinrollbank Oct 28 '10 at 15:48
@Steven Sam I was curious about generalized vandermonde matrices whose determinants vanishes. As I was surfing through the literature quite at random I came across some argument in a paper which goes like this: its a $3x4$ matrix with rows $({a_{i}}^{j_k}- s^{j_k})(i=1,2,3),j=1,..,4$. Then it says note for all minors to vanish, it is enough to show that two of them vanish. See page 17 of this paper Tropical secant graphs of monomial curves arxiv.org/pdf/1005.3364 –  Vagabond Nov 1 '10 at 15:00

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.

-
@Sheikraisinrollbank Thank you this is very useful for my purpose, as you have guessed correctly I am not looking for an algorithm to computationally check it. –  Vagabond Oct 28 '10 at 16:13
Can you suggest a reference where I can find some detail about Plucker relations ? It would help if you can suggest something which has a few examples. –  Vagabond Oct 28 '10 at 16:49
Section 9.1 of Fulton's book Young Tableaux contains all of the algebraic relations of the $r \times r$ minors of a generic matrix. –  Steven Sam Oct 28 '10 at 19:58
@Steven Sam Thank you for the reference. –  Vagabond Oct 29 '10 at 5:14
Fulton's book is quite nice. There's also Joe Harris' algebraic geometry book, and though I don't have it with me right now I seem to recall that it contains a description of the Plucker relations. –  Sheikraisinrollbank Oct 29 '10 at 11:22

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.

-
Also, I would emphasize the first sentence of your third paragraph more strongly. If you want to compute the rank of a matrix in practice (and you have exact entries, dealing with round off error is a whole different subject) then the right algorithm is Gaussian elimination, not computing minors. –  David Speyer Oct 28 '10 at 15:22
@Steven Sam: The only linear maps that are relevant for the question are the ones coming from evaluation at a matrix, and these do not span the full dual space of the linear span of the minors. Certainly the Plucker relations show that despite the fact that the minors are linearly independent, it is not true that they can take on arbitrary values independent of one another. So the phrase "Your question amounts..." at the beginning of the second paragraph should be modified. –  Sheikraisinrollbank Oct 29 '10 at 11:19
@sheikraisinrollbank I certainly overlooked something, you are right. For example, the functions $x^2, xy, y^2$ are certainly linearly independent but the vanishing of $x^2, y^2$ (over a field) implies that $xy = 0$. But this ideal is not radical, so I should emphasize that determinantal ideals are radical, but I didn't want to get into why that is true. One could also cheat and say that $xy \ne 0$ when $x^2 = y^2 = 0$ for certain commutative rings $k$ :) –  Steven Sam Oct 29 '10 at 13:23
@Steven Sam: The determinantal ideal being radical doesn't help here; it's just not possible for the minors to take on any set of values, independent of one another. For instance, in the 2 by 4 case you can't have $m_{12}=0=m_{13}$ and $m_{14}=1=m_{23}$. The point really is what I wrote above: the relevant linear functionals in this case are the evaluation functionals at points, and these don't separate the span of the minors. –  Sheikraisinrollbank Oct 29 '10 at 14:37
@shiekraisinrollbank: I am aware that the minors can't take arbitrary values independent of one another. This answer was to the original question of when a matrix has rank $< r$. Since the ideal generated by the $r \times r$ minors generate a radical ideal and they linearly independent, they form a minimal generating set. Hence some proper subset of them vanishing cannot imply that the other ones vanish. That's all I am saying. I am not saying anything about the possible values they can take. –  Steven Sam Oct 29 '10 at 17:56

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.

-
Good point. Thanks! –  Thierry Zell Oct 28 '10 at 13:45
Nice answer! Short and to the point. –  Sheikraisinrollbank Nov 1 '10 at 11:03

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.

-
And what if one of the columns of the $m \times (m+1)$ matrix is all 0's? Your method of obtaining a relation would fail because it would like like $0=0$. In fact, this is precisely a scenario where you need to check all minors (because all but one possibly vanish) Any answer that suggests that you don't need to check all of the minors will be wrong. –  Steven Sam Oct 28 '10 at 13:41
Ooops! What I wrote works best for matrices whose entries are variables (as in the determinantal varieties case), but of course, as Jorgen's example points out, it does not work so well with matrices that have a lot of zero entries (you cannot get much out of the expansion along your new row if your last minor is multiplied by zero!). –  Thierry Zell Oct 28 '10 at 13:44