  This paper presents a deterministic, strongly polynomial time algorithm for
computing the matrix rank for a class of symbolic matrices (whose entries are
polynomials over a field). This class was introduced, in a different language,
by Lov\'asz [Lov] in his study of flats in matroids, and proved a duality
theorem putting this problem in $NP \cap coNP$. As such, our result is another
demonstration where ``good characterization'' in the sense of Edmonds leads to
an efficient algorithm. In a different paper Lov\'asz [Lov79] proved that all
such symbolic rank problems have efficient probabilistic algorithms, namely are
in $BPP$. As such, our algorithm may be interpreted as a derandomization
result, in the long sequence special cases of the PIT (Polynomial Identity
Testing) problem. Finally, Lov\'asz and Yemini [LoYe] showed how the same
problem generalizes the graph rigidity problem in two dimensions. As such, our
algorithm may be seen as a generalization of the well-known deterministic
algorithm for the latter problem.
  There are two somewhat unusual technical features in this paper. The first is
the translation of Lov\'asz' flats problem into a symbolic rank one. The second
is the use of submodular optimization for derandomization. We hope that the
tools developed for both will be useful for related problems, in particular for
better understanding of graph rigidity in higher dimensions.
