Why is there not a test for diagonalizability of a matrix

Question

Let $A$ be square.This question is a bit opinion based, unless there is a technical answer.I think it is helpful tho. Also this question is closely related to this question : quick way to check if a matrix is diagonalizable.

Based on the answers, there is no known way to determine diagonalizability as a map $A \mapsto$ $\{$True, False$\}$. (see also note)

This doesn't happen for invertibility (determinant measures that) or over reals/complex numbers, existence of perpendicualar diagonalization/ unitarily diagonalizable using $A = A^{t}$ or $A^*A = AA^*$ conditions.

My question is is there a reason why there is no known way to check diagonalizability in general? I guess people must have tried, although possibly a very hard task. But considering determinant is also really complicated function, yet motivatable why the above map have never been found explicitly$?$

Note: A simple answer would be its too hard, but a better answer would be what makes it a hard task. Like, is the theory of that map really not that connected to anything we know?

Note: I chose this formalism of map $A\mapsto\{0,1\}$ basically because I thought the term 'algebraic way' to determine is ambigious. I was looking for a explicitly writable function as a code in $A$ (i.e finite, and requiring only computation but not conditional arguments).

Note: Some conditional arguments in some algorithms can be written as a computation (if $x>0$: return $x$ else return $0$ could be explicitly written as max($0,x$) but if algebraic multiplicity $>1$ is not possible explicitly). I admit it is rather hard to formalize, but it is enough to check if there is a polynomial or continuous function in $A$ when equal to $0$ determines diagonalizability.

Answer 1

There is no continuous function $f$ in the entries of the matrix s.t. $A$ is diagonalizable iff $f(A) = 0$ or iff $f(A) \neq 0$. (Like the case for invertibility, where $A$ is invertible iff $\det(A) \neq 0$; or the case for unitary diagonalizability, where $A$ is unitarily diagonalizable iff $AA^\ast - A^\ast A = 0$.) Indeed, if such an $f$ exists, then the set of diagonalizable matrices is either closed or open. Neither is the case. We have,

$$\begin{pmatrix} 1 & 1 \\ \epsilon & 1 \end{pmatrix}$$

is diagonalizable if $\epsilon \neq 0$ (in the real case, $\epsilon > 0$). But it is not diagonalizable if $\epsilon = 0$. Thus, the set of diagonalizable matrices is not closed. Moreover,

$$\begin{pmatrix} 1 & \epsilon \\ 0 & 1 \end{pmatrix}$$

is not diagonalizable if $\epsilon \neq 0$, but it is diagonalizable if $\epsilon = 0$. Thus, the set of diagonalizable matrices is not open either.

(I presented the example in $2 \times 2$ matrices, but it can be easily adapted to $n \times n$ for any $n \geq 2$.)

Answer 2

Here is a salvage: there is a continuous function $f(A)$ of a matrix $A$, even a polynomial function, which checks whether the eigenvalues of $A$ are distinct (over an algebraic closure). Any such matrix is diagonalizable, although not conversely, and this is frequently a useful substitute for the diagonalizability condition in proofs since it implies diagonalizability and is often easier to prove things about.

Namely, we can take $f(A)$ to be the discriminant $\Delta$ of the characteristic polynomial of $A$. This is a homogeneous polynomial of degree $n(n-1)$ in the coefficients of $A$ which is equal to $\prod_{i \neq j} (\lambda_i - \lambda_j)$ where $\lambda_i$ are the eigenvalues of $A$, and so it is nonzero iff $A$ has distinct eigenvalues. For example, when $n = 2$, if we write the entries of $A$ as

$$A = \begin{bmatrix} a & b \\ c & d \end{bmatrix}$$

then the characteristic polynomial is $\chi_A(t) = t^2 - (a + d) t + (ad - bc)$, and its discriminant is

$$\Delta = (a + d)^2 - 4(ad - bc) = \boxed{ (a - d)^2 + 4bc }.$$

You can check that this vanishes on all Jordan blocks, and more generally that it is zero iff the characteristic polynomial has a repeated root of $\frac{a+d}{2}$.

As David explains, the problems all stem from diagonalizable matrices with repeated eigenvalues, which are difficult to distinguish from non-diagonalizable matrices (so difficult no continuous function can distinguish them). If we had to work numerically to finite precision then it would actually be impossible to distinguish these, and it would even be impossible to numerically distinguish non-diagonalizable matrices from diagonalizable matrices with distinct eigenvalues some of which are very close together.

Edit: Here is some more discussion. We can consider Hagen von Eitzen's example of the matrices

$$X(\varepsilon) = \begin{bmatrix} 1 & 1 \\ 0 & 1 + \varepsilon \end{bmatrix}$$

which have distinct eigenvalues for $\varepsilon \neq 0$ but suddenly become non-diagonalizable at $\varepsilon = 0$. This is interesting because if a matrix has distinct eigenvalues then it has a basis of eigenvectors which is unique up to scaling (note that this is not true if it is diagonalizable but with repeated eigenvalues), but a non-diagonalizable matrix doesn't have a basis of eigenvectors. So, what happens to the eigenvectors of $X(\varepsilon)$ as $\varepsilon \to 0$?

One of them doesn't change at all, namely $v_1 = \begin{bmatrix} 1 \\ 0 \end{bmatrix}$, and this one remains an eigenvector as $\varepsilon \to 0$. So all of the interesting action must be happening with the other eigenvector, associated to the eigenvalue $1 + \varepsilon$. This eigenvector can be taken to be

$$v_{1 + \varepsilon} = \begin{bmatrix} 1 \\ \varepsilon \end{bmatrix}.$$

So now we can see what happens: as $\varepsilon \to 0$ not only do the eigenvalues collide, but the eigenvectors also collide! We can also see that if we had to work numerically to finite precision and $\varepsilon$ was very small, it would be very difficult to tell these eigenvectors apart numerically.

This suggests the general idea that we can think of matrices who have some eigenvalues very close to each other as having eigenvectors which are also very close to each other, which collide if we collide their eigenvalues. Matrices like this are "barely diagonalizable"; it's hard to distinguish these very close eigenvectors, and it gets harder the closer the eigenvalues are.

Answer 3

A matrix is diagonalizable if and only if its minimal polynomial has distinct roots and a real matrix is diagonalizable over $\mathbb{R}$ iff additionally all the roots are real. But given a real or complex polynomial $f(x)$ both of these criteria can be checked without too much difficulty:

• $f$ has multiple roots over $\mathbb{C}$ iff $\gcd(f, f') \ne 1$ which can be verified using the Euclidean algorithm.
• Supposing $f$ is real and does have distinct roots over $\mathbb{C}$, https://math.stackexchange.com/a/4087390 describes a process to find how many real roots it has, thereby checking if all the roots are real.

Thus it suffices to find, given an $n \times n$ matrix $A$ say over $F = \mathbb{R}$ or $\mathbb{C}$, its minimal polynomial $f(x)$, ie a monic polynomial $f(x)$ of minimal degree such that $f(A) = 0$. Such a polynomial of degree $k$ is a linear dependence between $1, A, A^2, \dots, A^{k} \in F^{n^2}$ with the coefficient of $A^{k}$ equal to $1$. For a given $k$, Gaussian elimination either shows that there is no linear dependence or produces one. Dividing by the coefficient of highest power of $A$ that appears, any non-trivial dependence can be turned into a monic polynomial of degree $\le k$. In particular it suffices to check each $k = 1, 2, \dots$ (and in fact some $k \le n$ must work because of the characteristic polynomial).

This is likely not the most efficient algorithm, eg Gaussian elimination can likely be replaced by something faster, and it may be better to do a binary search for $k$ rather than check them one by one.