linear algebra - Rank(A) and other algorithms as a polynomial

On the other hand there is a way to sort of "rescue" your idea. A matrix has rank $ geq k$ if and only if one of its $ktimes k$ submatrices has non-zero determinant.

So there is a (real) polynomial function $mathbb C^{nm} to mathbb R$ which is non-zero if and only if your matrix has rank $geq k$. The function is the sum of the modulus squared of all $k times k$ minors. The function is zero if and only if your matrix has rank $< k$.

Another way to look at what I'm saying is that the rank function on your space of matrices is constructing a stratification -- $lbrace rank=0rbrace subset lbrace rank leq 1rbrace subset lbrace rank leq 2rbrace cdots$ and the above function is measuring a type of "distance" in the ambient space from the $lbrace rank leq k-1rbrace$ stratum.