We'll prove this in two parts. Given an arbitrary matrix M, find a similar matrix in canonical form that can act as its representative. Then, show that different canonical matrices represent different classes. Thus each canonical matrix is a faithful representative of its class.
Let M be a matrix over an algebraically closed field F. If necessary, embed an integral domain in its ring of fractions, then extend to the algebraic closure.
Let M have an eigen value l with multiplicity s. Since the underlying field is algebraically closed, there is always an eigen value.
Let T = M with l subtracted from the main diagonal. We may write this as T = M-l, or M = T+l.
The determinant of T is zero, and T is a singular matrix. Use the previous theorem to find complementary subspaces K and R, such that K is nilpotent and R is nonsingular.
We know that K is T invariant, that is, T maps K into itself. But K is also invariant when scaled by the constant l. Put these together and K is invariant under M. Similarly, R is M invariant. We can therefore turn M into a block diagonal matrix, where the upper left block operates on K and the lower right block operates on R. Start by turning T into a block diagonal matrix, where the upper left block is a series of jordan simple blocks. We can do this because K is nilpotent. The last block operates on R, and is nonsingular. The change of basis that rearranged T has no effect on the diagonal matrix l. So the same change of basis, applied to M, produces the block diagonal matrix T plus the diagonal matrix l. In other words, we simply add l back in to find something similar to M. The blocks at the upper left, that come from K, are still simple jordan blocks, but now they have l down the main diagonal instead of 0.
Since the upper block of M, which operates on K, is lower triangular, its eigen values are its diagonal elements. These are all equal to l. If the lower right block has an eigen value of l, then the lower right block of T has a determinant of 0. However, this block is nonsingular, a contradiction. Therefore all the eigen values of l are accounted for. If l had multiplicity s, then K has dimension s, and the remaining submatrix has dimension n-s.
Now the submatrix in the lower right corner of M has an eigen value (other than l), and we can decompose it into blocks, as we did above. This eigen value is an eigen value of the original matrix M by similarity. We only need extend the base field by the eigen values of M. Repeat this process until the entire matrix is in jordan canonical form.
Every matrix M is similar to a jordan canonical matrix J, and J serves as the "canonical representative" for the class of matrices similar to M.
Next we need to show that our canonical representative is unique. In other words, different jordan canonical matrices belong to different classes, and are not similar to each other.
Note that a change of basis (using permutation matrices) can permute the blocks in a block diagonal matrix, so we need to be a bit more precise when describing the canonical representative. The simple jordan blocks establish the jordan form, without regard to order. If you like, you can sort the blocks by eigen value, and then by size, and place these blocks along the main diagonal from upper left to lower right. This produces a well defined canonical matrix. For our purposes, we will say that each equivalence class is represented by an unordered set of jordan blocks whose dimensions add up to n.
How can we prove two canonical matrices are not similar? Start by finding properties of a matrix that do not change when we switch to a similar matrix. One property that is invariant is the set of eigen values, including multiplicity. Thus, if two jordan forms are similar, the jordan blocks have the same eigen values, including multiplicity.
With this behind us, it is sufficient to focus on a particular eigen value l. There may be several ways to produce 7 instances of l. We could have two jordan blocks, size 3 and 4, or 7 jordan blocks of size 1. Let's see why these aren't similar.
One can recover the eigen vectors by looking at the jordan form. Given a simple jordan block jr(l), subtract l to find jr(0). This has rank r-1, leaving one eigen vector v. If v is expressed as a column vector, it consists of all zeros, except for 1 at the bottom. Verify that jr(l)*v = l*v, making v an eigen vector with eigen value l.
The number of jordan blocks, with eigen value l, establishes the number of linearly independent eigen vectors with eigen value l. the dimension of the eigen space does not change when we switch to a similar matrix, so the number of simple jordan blocks cannot change either.
This reaffirms the fact that a matrix is diagonalizable iff it has n independent eigen vectors. In other words, M is diagonalizable iff its jordan form has n simple blocks, each of size 1, leaving no room for ones on the subdiagonal.
But we're not out of the woods yet. What if one jordan form has two blocks with eigen value equal to l, and sizes 3 and 4, while a similar matrix presents jordan blocks of sizes 2 and 5? What's wrong with this picture?
The canonical matrices M1 and M2 are similar iff their cousins, with l subtracted from the main diagonal, are similar. Thus T1 and T2 are similar, even though they present jordan blocks of different sizes.
Let T1, restricted to K1, be a nilpotent transformation, and the same for T2 and K2. The jordan blocks that are nilpotent are the ones with 0 on the main diagonal, i.e. the blocks that use to have l on the main diagonal when they lived in M1. We want to associate these blocks, one for one, with the nilpotent jordan blocks in T2.
Given a jordan block of size p in T1, let z1 be a vector with T1p-1z1 nonzero, and T1pz1 equal to 0. This must be preserved by similarity, hence there is a z2 with index p under T2. This is part of the nilpotent subspace K2, and it has components taken from the jordan blocks in T2. The index, i.e. the size, of these blocks is at least p.
By symmetry, assume T1 has the larger blocks, of size p. The similar matrix T2 also has a jordan block of size p.
If T1 has another block of size p, then there is another vector, independent of the first jordan block, with index p. Similarity preserves linear independence, so there is a corresponding vector having index p under T2, that is independent of the previous vector and its recursive images. One jordan block cannot accommodate all these independent vectors. This implies a second jordan block of size p. Continue this process, and both T1 and T2 have the same number of blocks of size p.
Let the next largest blocks have size q. You might wonder about selecting a vector of index q, because there are plenty of these in the larger jordan blocks of size p. However, we're going to select a vector of index q that is independent of all the vectors that have gone before. It is not spanned by any of those jordan blocks. This is preserved by similarity, and it implies a block of size q in T2. The next block of size q implies another block of size q, and so on.
This process continues all the way down to the smallest blocks. The size distribution is the same, at least for the eigen value l, and since l was arbitrary, the canonical forms are the same.
Each jordan canonical form is a unique representative for its class of similar matrices.