Diagonalization is often presented as a useful tool for computing powers of matrices; however, if only few matrices are diagonalizable, the method might be not really powerful. Here, we prove that almost all matrices are diagonalizable over from different viewpoints.
Definition: Let be two polynomials. The resultant is defined as the product
where denote the algebraic closure of and denote the leading coefficients of and respectively; in the case of multiple roots, the factors are repeated according to their multiplicities.
Definition: The discriminant of a polynomial is defined by .
Lemma 1: Let be two polynomials. Then if and only if and are coprime.
Proof. If and have a common divisor then clearly they have a common root in hence . Conversely, suppose that and are coprime. According to Bézout’s identity of polynomials, there exist two polynomials such that
Because the equality still holds in , we deduce that and do not have any commom root in , hence .
We deduce easily the following corollary:
Lemma 2: Let be a polynomial. Then has only simple roots if and only if .
Because is a polynomial on the coefficients of , we will able to deduce the following theorems from lemmas 3, 4 and 5:
Theorem 1: The set of diagonalizable matrices is dense in .
Theorem 2: The set of diagonalizable matrices is a set of full measure (ie. its complement has measure zero).
Lemma 3: Let be a matrix. If its characteristic polynomial has only simple roots then is diagonalizable.
Proof. Let be the distinct eigenvalues of (ie. the roots of ), and for every , let be an eigenvector associated to .
We show that is a basis of by induction on . For , it is clear. Suppose that it is true for and let be such that
Suppose by contradiction that one is non-zero, say . Then
On the other hand,
Because when and according to our induction hypothesis, we deduce that , hence ie. : a contradiction.
Corollary 1: Let be the set of diagonalizable matrices. Then is the set of matrices whose eigenvalues are pairwise distinct.
Proof. For every matrix , let denote its characteristic polynomial. Let . In particular, is a polynomial on the coefficient of so is continuous. According to lemma 2 and 3, we deduce that the set of diagonalizable matrices whose eigenvalues are pairwise discinct is open in .
Let be a diagonalizable matrix with an eigenvalue of multiplicity at least two. There exist and two diagonal matrices such that
For all , let
Suppose that is diagonalizable; in particular, there exists a polynomial whose roots are simple such that . Clearly, the matrix vanishes the polynomial , so this matrix is diagonalizable, that is there exists such that
hence . Therefore, is diagonalizable if and only if and , so .
Finally, we deduce that .
Lemma 4: Let be a non-zero polynomial. Then is nowhere dense in .
Proof. Suppose that vanishes on an open ball and let . The restriction of on the straight line passing through and coincides with a polynomial in one variable. Because vanishes on , we deduce that has infinitely many roots hence and . Therefore, .
Lemma 5: Let be a non-zero polynomial. Then has measure zero in .
Proof. We prove by induction on that the null set of a non-zero polynomial in has measure zero. For , it is clear since is finite. Suppose the result holds for and let .
Let . It is possible to write as
where , are monomials and . Notice that implies so is finite since has only finitely many roots. Then
Because , we deduce that .
Then, if we have , hence
by our induction hypothesis. Therefore, and finally .
Proof of theorems 1 and 2. For every matrix , let denote its characteristic polynomial. Let . Because is a polynomial on the coefficients of , we deduce from corollary 1 and lemmas 3 to 5 that is dense in and is a set of full measure.
In fact, theorem 1 (resp. lemma 3) is a consequence of theorem 2 (resp. lemma 4).
Notice that there are no theorems similar to theorems 1 and 2 when we deal with diagonalization over . Indeed, the characteristic polynomial of has a negative discriminant, so there exists a neighborhood of such that the discriminant is negative on ; in particular, the matrices in are not diagonalizable.
However, it is possible to determine the closure of the set of diagonalizable matrices in :
Property: The closure of the set of diagonalizable matrices (over ) in is the set of triangularizable matrices.
Proof. Let be a triangularizable matrix. So there exist and such that
For all , let be such that when . Therefore, the matrix
is diagonalisable according to lemma 3. Because , we deduce that belongs to the closure of the set of diagonalizable matrices.
Conversely, let be the limit of diagonalizable matrices . Let (resp. ) be the characteristic polynomial of (resp. ). We can write
where and .
From now on, we fix some . For all , let be such that . Therefore,
(We used the fact that the coefficients of a characteristic polynomial are polynomials on the coefficient of the matrix to justify that .)
Therefore, the complex roots of are limits of roots of the so . We deduce that is triangularizable.
Now, we deal with a probabilistic viewpoint; intuitively, the following theorem states that a matrix in is diagonalizable over with a probability of one:
Theorem 3: Let be the number of matrices in whose coefficients are in and be the number of similar matrices whose (complex) eigenvalues are not pairwise distinct. Then
Proof. Let where denotes the characteristic polynomial of . We already know that is a polynomial on the coefficients of and that if and only if has a complex eigenvalue with multiplicity at least two. Therefore, if
By induction, we define for as the leading coefficient of . In particular, notice that and . For all , let us introduce the set
Then so .
If , the polynomial is non-zero so it has at most roots. We deduce that
(We have at least choices for and choices for each with .)
Therefore, , and because :
Again, theorem 3 does not hold for diagonalizations over or . For example,
over , and even
over , where is the number of diagonalizable (over or ) matrices whose coefficients are in .
More information can be found in the paper The probability that a matrix of integers is diagonalizable.