# Proving “almost all matrices over C are diagonalizable”.

This is an elementary question, but a little subtle so I hope it is suitable for MO.

Let $T$ be an $n \times n$ square matrix over $\mathbb{C}$.

The characteristic polynomial $T - \lambda I$ splits into linear factors like $T - \lambda_iI$, and we have the Jordan canonical form:

$$J = \begin{bmatrix} J_1 \\\ & J_2 \\\ & & \ddots \\\ & & & J_n \end{bmatrix}$$

where each block $J_i$ corresponds to the eigenvalue $\lambda_i$ and is of the form

$$J_i = \begin{bmatrix} \lambda_i & 1 \\\ & \lambda_i & \ddots \\\ & & \ddots & 1 \\\ & & & \lambda_i \end{bmatrix}$$

and each $J_i$ has the property that $J_i - \lambda_i I$ is nilpotent, and in fact has kernel strictly smaller than $(J_i - \lambda_i I)^2$, which shows that none of these Jordan blocks fix any proper subspace of the subspace which they fix. Thus, Jordan canonical form gives the closest possible to a diagonal matrix. The elements in the superdiagonals of the Jordan blocks are the obstruction to diagonalization.

So far, so good. What I want to prove is the assertion that "Almost all square matrices over $\mathbb{C}$ is diagonalizable". The measure on the space of matrices is obvious, since it can be identified with $\mathbb{C}^{n^2}$. How to prove, perhaps using the above Jordan canonical form explanation, that almost all matrices are like this?

I am able to reason out the algebra part as above, but is finding difficulty in the analytic part. All I am able to manage is the following. The characteristic equation is of the form

$$(x - \lambda_1)(x - \lambda_2) \cdots (x - \lambda_n)$$

and in the space generated by the $\lambda_i$'s, the measure of the set in which it can happen that $\lambda_i = \lambda_j$ when $i \neq j$, is $0$: this set is a union of hyperplanes, each of measure $0$.

But here I have cheated, I used only the characteristic equation instead of using the full matrix. How do I prove it rigorously?

-
The 'obvious measure' on $\mathbb C^{n^2}$ is not a probability measure... – Mariano Suárez-Alvarez Jan 22 '10 at 16:49
You are right. I have modified accordingly. – Anweshi Jan 22 '10 at 16:54
Now that you have Mariano's argument notice the kind of things you can do with it -- for example, you can give a simple proof of Cayley-Hamilton by noticing that the set of matrices where Cayley-Hamilton holds is closed, and true on diagonalizable matrices for simple reasons. – Ryan Budney Jan 22 '10 at 17:05

The discriminant of the characteristic polynomial of a matrix depends polynomially on the coefficients of the matrix, and its vanishing detects precisely the existence of multiple eigenvalues. Therefore the set where the discriminant does not vanish is contained in the set of diagonalizable matrices.

Now the set where a non-zero polynomial vanishes is very, very thin (in many senses: it does not contain open sets, it has zero Lebesgue measure, etc) so in consequence the set of diagonalizable matrices is correspondingly thick.

-
Thanks. This use of the discriminant provided the rigor I was looking for. So the missing part was not analytic, it was still algebraic.. – Anweshi Jan 22 '10 at 16:56
In particular, even if you don't want to do any measure theory, it's not hard to see that the complement of the set where a non-zero polynomial vanishes is dense. – Qiaochu Yuan Jan 22 '10 at 17:20
@Anweshi: The analytic part enters when Mariano waves his hands---"Now the set where a non-zero polynomial vanishes is very, very thin"---so there is a little more work to be done. – Tom LaGatta Jan 22 '10 at 17:23
@Anweshi: see en.wikipedia.org/wiki/Smith%E2%80%93Volterra%E2%80%93Cantor_set for an example of a closed set which contains no open and of positive measure. – Mariano Suárez-Alvarez Jan 22 '10 at 17:33
All this fuss about "the analytic part"---just use the Zariski topology :-) – Kevin Buzzard Jan 23 '10 at 9:51

The discriminant argument shows that for for $n \times n$ matrices over any field $k$, the Zariski closure of the set of non-diagonalizable matrices is proper in $\mathbb{A}^{n^2}$ -- an irreducible algebraic variety -- and therefore of smaller dimension. Being contained in a proper algebraic subset of affine or projective space is a very strong and useful way of saying that a set is "small" (except in the case that $k$ is finite!): in particular, its complement is Zariski dense.

One can use this observation to reduce many theorems in linear algebra to the diagonalizable case, the idea being that any polynomial identity that holds on a Zariski-dense set of all $n \times n$ matrices must hold (by definition of the Zariski topology!) for all matrices.

As a very simple example, one can immediately deduce that the characteristic polynomials $AB$ and $BA$ coincide, because if $A$ is invertible, the matrices are similar.

With a bit more care, one can derive the entire theory of determinants and characteristic polynomials from such specialization arguments. In fact by purely algebraic means it is possible to reduce to the case of $k = \mathbb{R}$ (and thereby define the determinant in terms of change of volume, etc.).

-
Thanks! This was very useful. – Anweshi Jan 22 '10 at 18:17
Pete: being a closed subset of A^n which isn't A^n is still a powerful statement when k is finite, because, as you well know, affine n-space over a finite field is still an infinite set. I once had to think twice about the following: "proper + quasi-finite implies finite, but projective 1-space over a finite field is proper and quasi-finite---umm---aah I see the point". – Kevin Buzzard Jan 23 '10 at 12:19
@KB: Here I meant the Zariski topology on $\mathbb{A}^n(k)$ -- I don't want to suggest scheme theory as a prerequisite for linear algebra! -- so that this is the discrete topology iff $k$ is finite. – Pete L. Clark Jan 23 '10 at 12:26
... c.f. Exercise 21 of math.uga.edu/~pete/8320homework1.pdf – Pete L. Clark Jan 23 '10 at 12:28
Also recall the existence of space-filling curves over finite fields. Anyway, I think by now you take my point... – Pete L. Clark Jan 23 '10 at 12:31

In addition to the other answers, all of which are quite good, I offer a rather pedestrian observation: If you perturb the diagonal in each Jordan block of your given matrix $T$ so all the diagonal terms have different values, you end up with a matrix that has $n$ distinct eigenvalues and is hence diagonalizable. Such a perturbation can of course be as small as you wish.

Edit: As gowers points out, you don't even need the Jordan form to do this, just the triangular form.

-
Or you could simply upper-triangularize your matrix and do the same. – gowers Jan 22 '10 at 23:15
The added benefit is that the same argument proves that Zariski closed sets are of measure zero. Of course, I do not know how to write it in detail with the epsilons and deltas, but I am convinced by the heuristics. I am almost tempted to accept this answer over the others! – Anweshi Jan 24 '10 at 0:32
@Harald. It perturbs me that I cannot complete this argument rigorously. Will you be able to help? – Anweshi Jan 24 '10 at 1:31
You're right, my argument really only proves that the set of non-diagonalizable matrices has empty interior. As a closed set with empty interior can still have positive measure, this doesn't quite clinch the argument in the measure-theoretic sense. – Harald Hanche-Olsen Jan 24 '10 at 16:34
@Hanche. That is Sard's theorem. – Anweshi Feb 2 '10 at 23:36

The map from $\mathbb C^{n^2}$ to the space of monic polynomials of degree $n$ which associates to a matrix $M$ its char. polynomial is the best kind of map you could imagine (algebraic, surjective, open, ... ). If a set in its source has positive measure, than so does its image.

Now the set of polynomials with repeated roots is the zero locus of a non-trivial polynomial (the discriminant), and so has measure zero. Thus so does its preimage.

In short, the space of matrices in ${\mathbb C}$ whose eigenvalues are distinct has full measure (i.e. its complement has measure zero). Any such matrix is diagonalizable (its Jordan Normal Form is a diagonalization).

-
Dear Anweshi, a matrix is diagonalizable if only if it is a normal operator. That is, if and only if $A$ commutes with its adjoint ($AA^{+}=A^{+}A$). This equation is a restriction for a matrix $A$. Therefore, the set of diagonalizable matrices has null measure in the set of square matrices. That is, almost all complex matrices are not diagonalizable. Regards! -Dardo