Let $A$ be a matrix whose entries are either indeterminates or fixed to zero. For example, consider $$A = \left( \begin{array}{ccc} 0 & x_{12} & 0 \\ 0 & 0 & 0 \\ 0 & x_{32} & 0 \end{array} \right).$$ It is natural to associate a graph with such matrix, with the directed edge $(i,j)$ present in the graph whenever $A_{ji}$ is not zero (i.e., is an indeterminate). For example, the matrix $A$ above is associated with the graph $$ \circ \leftarrow \circ \rightarrow \circ$$

It is easy to see that $\det(A)$ is generically nonzero if and only if the associated graph has a perfect matching. Here a perfect matching is a collection of $n$ directed edges, none of which share a source or a destination; and generically means with probability one over the set of values the indeterminates can take. In the above example, we have that $\det(A)$ is generically zero and the associated graph does not have a perfect matching.

My question is whether this observation can be strengthened to say something about what the nullspace of $A$ looks like, generically.

Question 1: Are there any characterizations of the generic nullspace of such matrices?

In particular, there is a natural conjecture to make. For a set $S$ of vertices in the graph, let $T(S)$ be the set of in-neighbors of $S$. If $|T(S)| < |S|$, then we can find vectors $q$ supported on $S$ such that $q A = 0$; indeed, since the submatrix of $A$ with rows corresponding to $S$ has at most $|T(S)|$, nonzero columns, we can generically come up with at least $|S|-|T(S)|$ independent vectors this way.

Question 2: Is it true that the nullspace of $A$ generically equals ${\rm span}(\{q_i\})$ where $\{q_i\}$ is the collection of vectors obtained this way?

As an illustration, in the above example we can take $S=\{2\}, T(S)=\emptyset$, which leads to the vector $q_1 = [0, 1, 0]$. We can also take $S=\{1,3\}, T(S)=\{2\}$, which leads to a nonzero vector supported on $\{1,3\}$ in the left-nullspace (in this case, we cansay explicitly it leads to the vector $q_2 = [-x_{32},0,x_{12}]$); and together $q_1, q_2$ indeed do span the null space of $A$ generically. One can, of course, also take $S=\{1,2,3\}, T(S)=\{2\}$, but whatever one gets from this will be redundant.

Since the graph has a perfect matching if and only if there does not exist an $S$ with $|T(S)|<|S|$, if true this conjecture would reduce to the earlier observation about nonsingularity of $A$.

It seems like this sort of question should have been studied, though I have not been able to find a reference.

  • $\begingroup$ Shouldn't the direction of the directed edges be reversed in the example you gave? $\endgroup$ – Rodrigo de Azevedo Nov 8 '17 at 8:24

The answer to question 2 is positive. By König's theorem, you may find $r$ indeterminates belonging to distinct rows and columns, and cover all indeterminates by, say $r_1$ columns and $r_2=r-r_1$ rows. Then the rank of a matrix equals $r$ (it can not be neither more or less), and the kernel has a dimension $n-r$. We have $n-r_1$ columns such that all indeterminates in them belong to $r_2$ rows. This gives $(n-r_1)-r_2=n-r$ linearly independent vectors of your type, and this is the whole kernel already.

| cite | improve this answer | |
  • $\begingroup$ @morgan they are covered by $r_1=1$ columns and $r_2=0$ rows. When I say that five rows and seven columns cover a certain set of elements, I mean that their union does cover it, not intersection. $\endgroup$ – Fedor Petrov Nov 9 '17 at 10:37

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.