Is there a numerical measure of diagonalizability for matrices? Is there an effectively computable function $f$ from matrices to numbers such that $f(M)$ is nonzero if and only if $M$ is diagonalizable?
 A: I am not sure if this answers your question. If not, I will delete it.
There is no continuous functions $f\colon\mathbb{R}^{n\times n}\longrightarrow\mathbb R$ such that $f(M)\neq0$ if and only if $f$ is diagonalizable. I will prove it when $n=2$, but the general case is similar. If there was such a function, we would have$$(\forall t\in\mathbb{R}\setminus\{0\}):f\left(\begin{bmatrix}0&t\\0&0\end{bmatrix}\right)=0.$$But then$$f\left(\begin{bmatrix}0&0\\0&0\end{bmatrix}\right)=\lim_{t\to0}f\left(\begin{bmatrix}0&t\\0&0\end{bmatrix}\right)=0,$$which cannot happen, since $\left[\begin{smallmatrix}0&0\\0&0\end{smallmatrix}\right]$ is diagonalisable.
A: If $A\in M_n(\mathbb{Q})$, then its minimal polynomial $p_A$ is effectively computable (eventually using a software with complexity $O(n^3)$) and the following non-continuous function $f$ is s.t. $f(A)=0$ iff $A$ is diagonalizable over $\mathbb{C}$.
$f:A\in M_n(\mathbb{Q})\rightarrow gcd(p_A(x),{p_A}'(x))-1$.
EDIT 3. Remark 1. We may replace $\mathbb{Q}$ with a finite algebraic extension of $\mathbb{Q}$. On the other hand, if the $(a_{i,j})$ are not exactly known and if some eigenvalues are very closed, then we cannot conclude with regard to the diagonalisability of $A$; this comes mainly from the non-continuity of $f$.
Remark 2. The set $Z$ of non-diagonalizable complex matrices is a Zariski close set; then it has zero measure and its interior is void. For example, if you randomly choose a matrix in $M_{10}([[-100,100]])$, then it is "always" diagonalizable (because it has distinct eigenvalues).
Thus, you are right; it is natural to construct a function $g$ that is $0$ exactly on $Z$ rather than a function $f$ that is $\not= 0$ exactly on $Z$. We choose such a function $g$ as follows:
Let $sign(u)=1,0,-1$ when $u>0,u=0,u<0$. Then put $g(A)=sign(|discrim(p_A)|)$ where $discrim(.)$ is the discriminant.
If $A$ is diagonalizable over $\mathbb{C}$, then $discrim(p_A)\not= 0$ and $g(A)=1$. If $A$ is not, then $discrim(p_A)=0$ and $g(A)=0$.
