# Rank(A) and other algorithms as a polynomial

If $A = (\alpha_{ij}) \in \mathbb{C}^{nxm}$ we have simple algorithms by which to determine $\mathrm{rank}(A)$. However, is there a polynomial $f \in \mathbb{C}[\alpha_{ij}]$ where $f \colon \mathbb{C}^{nxm} \to \mathbb{N}$ such that $f(A) = \mathrm{rank}(A)$?

In general, is it possible to determine if a particular algorithm may be expressed as a polynomial or other more general function?

-
Why? Every function on F_q^n can be represented by a polynomial. This is a simple application of the Chinese remainder theorem. –  Qiaochu Yuan Jan 18 '10 at 21:41
My guess is a construction along the lines of Ryan Budney's answer works. –  Qiaochu Yuan Jan 18 '10 at 22:00

The preimage of a natural number under a polynomial map is always closed, yet the set of matrices with rank one is not closed. For example, the sequence $(A_n)_{n\geq1}$ in $M\_2(\mathbb C)$ with $A_n=\left(\begin{smallmatrix}1/n&0\\\0&0\end{smallmatrix}\right)$ has all its items of rank one, yet its limit has rank zero.

-
In other words: "no, because the rank isn't continuous." –  Qiaochu Yuan Jan 18 '10 at 20:12

The answer to your second question is that every algorithm determines a function. But if the last bit is ignored, then polynomial functions have very special properties (such as continuity and smoothness) and it's usually pretty obvious when you have one on your hands. I suppose you wanted to generalize from the determinant and the trace; these are very special and there are good reasons that they end up being polynomials in the entries of a matrix. Those reasons don't apply to the rank.

General comments: the only continuous functions from $\mathbb{C}^k$ to a discrete space like $\mathbb{N}$ are the constant functions, and any nonconstant polynomial function of $k$ complex variables has range $\mathbb{C}$.

-

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 $k\times 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=0\rbrace \subset \lbrace rank \leq 1\rbrace \subset \lbrace rank \leq 2\rbrace \cdots$ and the above function is measuring a type of "distance" in the ambient space from the $\lbrace rank \leq k-1\rbrace$ stratum.

-