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. 



The generic nullspace of a graph
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.


