Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
2  
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
3  
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

5 Answers 5

up vote 22 down vote accepted

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.

share|improve this answer
    
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
2  
@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
3  
@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
3  
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.).

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

share|improve this answer
4  
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).

share|improve this answer
    
@Emerton. " If a set in its source has positive measure, than so does its image.". May I ask more information about this "so" you use? –  Anweshi Jan 22 '10 at 18:23
    
@Emerton. I wish I could accept your answer. However Mariano gave the same answer at essentially the same time and I was in dilemma. Please see meta here. tea.mathoverflow.net/discussion/178 –  Anweshi Jan 22 '10 at 19:14
1  
Dear Anweshi, Don't worry about it! –  Emerton Jan 22 '10 at 19:35

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

share|improve this answer
7  
"Diagonalizable" to the OP means similar to a diagonal matrix. To you it means unitarily equivalent to a diagonal matrix. Two different things. –  Gerald Edgar Jan 31 '13 at 20:04

Your Answer

 
discard

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.