MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 5 down vote accepted

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.

share|cite|improve this answer
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}$.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.