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.