# The generic nullspace of a graph

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.

• Shouldn't the direction of the directed edges be reversed in the example you gave? – 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.
• @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. – Fedor Petrov Nov 9 '17 at 10:37