• Conjugacy Class of Similar Matrices
• Eigen Vector, Eigen Value
• Similarity and Eigen Vectors
• Diagonalizable
• Schur's Theorem
• Trace and Norm
• Block Diagonal
• Direct Sum, Invariant, Complementary
• Nilpotent Transformation
• Jordan Canonical Form
• Complementary Spaces in a Singular Transformation
• A Jordan Form for Each Conjugacy Class

If x and v belong to a group, xv/x is the conjugate of v by x. Conjugate this by y and it's the same as conjugating v by yx. And if u is the conjugate of v by x then v is the conjugate of u by 1/x. Conjugates clump together into conjugacy classes. So far it's just group theory; but this chapter explores the conjugacy classes of matrices, with a couple of twists.

1. We don't usually leave the group when looking for conjugators. However, when conjugating a matrix, it is sometimes helpful to extend the base field. If M is a matrix of real numbers, X might be a matrix of complex numbers, whence XM/X is the conjugate of M. It is perhaps easiest to embed our matrices in a closed field from the start.

2. Everything in a group is invertible, but not all matrices are invertible. Even if M is singular, it has conjugates, and a conjugacy class. (If you want to be technical, we are looking for conjugacy classes in a monoid.) The only requirement is that the conjugator be invertible. Well that make sense, you have to divide by the conjugator on the other side.

3. Each conjugacy class has a preferred matrix, a preferred representative, which is called the jordan canonical form (named after Camille Jordan). The jordan form is much easier to work with. For example, compute Mⁿ by switching to the jordan form J. Conjugation is an isomorphism that respects multiplication, so there is no trouble here. Jⁿ is easy to calculate, because J is diagonal, or nearly so. Conjugate back, and find Mⁿ.

Conjugacy class of M:
M ⇔ XM/X ⇔ YM/Y ⇔ … ⇔ ZM/Z = J (the jordan form of M )

Conjugate matrices are also called similar matrices.

Verify that the determinant does not change with conjugation. We are multiplying and dividing by the determinant of the conjugator. Thus similar matrices have the same determinant.

Let the rank of M be k. Thus the rows of M span a space of dimension k. Multiply by X on the left and each row in XM is a linear combination of rows of M. The rows span a subspace of the original space. However, X is invertible, and the action is reversible, so each row of M is spanned by the rows of XM, and the space is the same.

On the other side, multiplication by X inverse is a linear map with no kernel, since X is nonsingular. The dimension of the domain equals the dimension of the range. Thus the rank of M is the rank of M/X. Put this all together and similar matrices have the same rank.

Two matrices are unitarily similar if one is the conjugate of the other by a unitary (orthonormal) matrix. The product of unitary matrices is unitary, as is the inverse, so matrices clump together into well defined equivalence classes, using unitary matrices as conjugators. These are refinements of the "similar" classes described above.

So why is this chapter on linear algebra here, in the middle of groups? Because the next chapter will explore invertible matrices, as a group, and jordan forms can simplify the analysis.

An eigen vector is a vector that is scaled by a linear transformation, but not moved. Think of an eigen vector as an arrow whose direction is not changed. It may stretch, or shrink, as space is transformed, but it continues to point in the same direction. Most arrows will move, as illustrated by a spinning planet, but some vectors will continue to point in the same direction, such as the north pole.

The scaling factor of an eigen vector is called its eigen value. An eigen value only makes sense in the context of an eigen vector, i.e. the arrow whose length is being changed.

In the plane, a rigid rotation of 90° has no eigen vectors, because all vectors move. However, the reflection y = -y has the x and y axes as eigen vectors. In this function, x is scaled by 1 and y by -1, the eigen values corresponding to the two eigen vectors. All other vectors move in the plane.

The y axis, in the above example, is subtle. The direction of the vector has been reversed, yet we still call it an eigen vector, because it lives in the same line as the original vector. It has been scaled by -1, pointing in the opposite direction. An eigen vector stretches, or shrinks, or reverses course, or squashes down to 0. The key is that the output vector is a constant (possibly negative) times the input vector.

These concepts are valid over a division ring, as well as a field. Multiply by K on the left to build the K vector space, and apply the transformation, as a matrix, on the right. However, the following method for deriving eigen values and vectors is based on the determinant, and requires a field.

Given a matrix M implementing a linear transformation, let the vector x represent an eigen vector and let l be the eigen value. Solve x*M = lx.

Rewrite lx as x times l times the identity matrix and subtract it from both sides. The right side drops to 0, and the left side is x*M-x*l*identity. Pull x out of both factors and write x*Q = 0, where Q is M with l subtracted from the main diagonal. The eigen vector x lies in the kernel of the map implemented by Q. The entire kernel is known as the eigen space, and of course it depends on the value of l, a different eigen space for each eigen value l.

The eigen space is nontrivial iff the determinant of Q is 0. Expand the determinant, giving an n degree polynomial in l. This is called the characteristic polynomial of the matrix. The roots of this polynomial are the eigen values. There are at most n eigen values.

Substitute each root in turn and find the kernel of Q. This is the set of vectors x such that x*Q = 0.

In summary, a somewhat straightforward algorithm extracts the eigen values, by solving an n degree polynomial, then derives the eigen space for each eigen value.

Some eigen values will produce multiple eigen vectors, i.e. an eigen space with more than one dimension. The identity matrix, for instance, has an eigen value of 1, and an n-dimensional eigen space to go with it. In contrast, an eigen value may have multiplicity > 1, yet there is only one eigen vector. This is illustrated by the 2×2 matrix with ones on the top and lower right, and zero in the lower left. This tilts the x axis counterclockwise and leaves the y axis alone. The eigen values are 1 and 1, and the eigen vector is [0,1], namely the y axis.

Let two eigen vectors have the same eigen value. Specifically, let a linear map multiply the vectors v and w by the scaling factor l. By linearity, 3v+4w is also scaled by l. In fact every linear combination of v and w is scaled by l. When a set of vectors has a common eigen value, the entire space spanned by those vectors is an eigen space for the given eigen value.

This is not surprising, since the eigen vectors associated with l are precisely the kernel of the transformation defined by the matrix M with l subtracted from the main diagonal. This kernel is a vector space, and so is the eigen space of l.

Select a basis b for the eigen space of l. The vectors in b are eigen vectors, with eigen value l, and every eigen vector with eigen value l is spanned by b. Conversely, an eigen vector with some other eigen value lies outside of b.

Different eigen values always lead to independent eigen spaces.

Suppose we have the shortest counterexample. Thus c₁x₁ + c₂x₂ + … + c_kx_k = 0. Here x₁ through x_k are the eigen vectors, and c₁ through c_k are the coefficients that prove the vectors form a dependent set. Furthermore, the vectors represent at least two different eigen values. Thus k is at least 2.

Let the first 7 vectors share a common eigen value l. If these vectors are dependent then one of them can be expressed as a linear combination of the other 6. Make this substitution and find a shorter list of dependent eigen vectors that do not all share the same eigen value. Now the first 6 have eigen value l, and the rest have some other eigen value. Remember, we selected the shortest list, so this is a contradiction. Therefore the eigen vectors associated with any given eigen value are independent.

Scale all the coefficients c₁ through c_k by a common factor s. This does not change the fact that the sum of c_ix_i is still zero. However, other than this scaling factor, we will prove there are no other coefficients that carry these eigen vectors to 0.

If there are two independent sets of coefficients that lead to 0, scale them so the first coefficients in each set are equal, then subtract. This gives a shorter linear combination of eigen vectors that yields 0. If there is but one vector left standing, then c_jx_j = 0, which is impossible. These dependent eigen vectors cannot share one common eigen value, that has already been ruled out; thus multiple eigen values are represented. This is a shorter list of dependent eigen vectors with multiple eigen values, which is a contradiction. Therefore, if a set of coefficients carries our eigen vectors to 0, it must be a scale multiple of c₁ c₂ c₃ … c_k.

Now take the sum of c_ix_i and multiply by M on the right. In other words, apply the linear transformation. The image of 0 ought to be 0. Yet each coefficient is effectively multiplied by the eigen value for its eigen vector, and not all eigen values are equal. In particular, not all eigen values are 0. The coefficients are not scaled equally. The new linear combination of eigen vectors is not a scale multiple of the original, and is not zero across the board. It represents a new way to combine eigen vectors to get 0. If there were two eigen values before, and one of them was zero, there is but one eigen value now. However, this means the vectors associated with that one eigen value are dependent, and we already ruled that out. Therefore we still have two or more eigen values represented. This cannot be a shorter list, so all eigen vectors are still present. In other words, all our original eigen values were nonzero. Hence a different linear combination of our eigen vectors yields 0, and that is impossible. Therefore the eigen spaces produced by different eigen values are linearly independent.

Here is a simple application of eigen vectors. A rigid rotation in 3 space always has an axis of rotation. Let M implement the rotation. The determinant of M, with l subtracted from its main diagonal, gives a cubic polynomial in l, and every cubic has at least one real root. Since lengths are preserved by a rotation, l is ±1. If l is -1 we have a reflection. So l = 1, and the space rotates through some angle θ about the eigen vector. That's why every planet, every star, has an axis of rotation.

Let P be a nonsingular matrix that proves A is similar to B. In other words, PA/P = B.

Let v be an eigen vector of A, such that v*A = sv for some scaling factor s. Take the preimage of v under P. In other words, w*P = v. Now w*P*A = sv, and when we apply P inverse, we get sw. Thus w is an eigen vector for B, with the same eigen value s.

By symmetry, an eigen vector w of the matrix B becomes an eigen vector v of the matrix A, with the same eigen value s.

All this shows the set of eigen values is the same, but doesn't verify multiplicity. You can show equal characteristic polynomials, and hence the same eigen values, by looking at B-s*I, where s is a variable that represents the eigen value, and I is the identity matrix. This is the same as P*A/P - s*I,
or P*A/P - P*s*I/P,
or P*(A-s*I)/P.

Take determinants, remembering that det(P) and det(P^-1) cancel, and the determinant of B with s subtracted from the main diagonal is the same as the determinant of A with s subtracted from the main diagonal. Both matrices produce the same characteristic polynomial, and both matrices have the same eigen values, multiplicities included.

You've seen the term "diagonalizable" before. Gaussian elimination can diagonalize a matrix M, using elementary row operations, iff M is nonsingular. This section defines diagonalizable in a new way. M is diagonalizable iff if has n independent eigen vectors. This is an unrelated concept; some matrices are diagonalizable here, and not there, and some are diagonalizable there, and not here. Sorry for the confusion.

A matrix M is diagonalizable if it is similar to a diagonal matrix. Write this as PM/P = D, where P is nonsingular and D is a diagonal matrix.

The eigen vectors of D are the coordinate vectors, each scaled by the corresponding entry on the main diagonal of D. There are n independent eigen vectors. Pull this back to M and find n independent vectors.

Conversely, let M have n independent eigen vectors. Let P map the unit basis onto these n independent vectors. In other words, the rows of P are the eigen vectors of M. Apply M, which scales these vectors, then apply P inverse, which pulls the vectors back to the coordinate axes. The composite is a matrix that scales the coordinate vectors, and that has to be a diagonal matrix. The diagonal entries are the eigen values. Therefore a matrix is diagonalizable iff it has n independent eigen vectors.

Note that some of these eigen values could be 0, Squashing the eigen vectors down to a point. The corresponding diagonal matrix has zeros on its main diagonal.

When M is diagonalizable, the diagonal equivalent D is the jordan form of M. As you might imagine, D is easier to work with. If M does not have n independent eigen vectors, there is more work to do.

Schur's theorem states that any matrix is unitarily similar to a lower triangular matrix.

Remember that a unitary (orthogonal) matrix implements a rigid rotation in space. So the phrase "unitarily similar" is just like turning your head. You're looking at the same linear transform from another direction. From this vantage point, the first coordinate is scaled, the second coordinate is a linear combination of the first two coordinates, and so on, building a lower triangular matrix. Of course you could turn your head the other way and the transform becomes upper triangular. In fact that's how most textbooks present the theorem. But jordan forms are traditionally lower triangular, with ones on the subdiagonal, so I'm going to build a lower triangular matrix for consistency.

This theorem only works over an algebraically closed field, such as the complex numbers. To illustrate, consider a linear map in R² that rotates the plane 90 degrees. There is no real eigen vector, and there won't be after you conjugate by a real matrix. Yet a lower triangular matrix always has at least one eigen vector. Forget unitary; this matrix isn't similar to a lower triangular matrix at all, unless you bring in the complex numbers.

With that example behind us, let's assume the field includes the entries of M and all the eigen values of M.

Proceed by induction on the number of dimensions. A 1×1 matrix is automatically a lower triangular matrix, so consider an n×n matrix.

Find an eigen value s and an eigen vector x. Thus xM = sx.

Assume there is a well defined dot product, as is the case in the reals or the complex numbers. Use the Gram Schmidt process to build B, an orthogonal basis with x as its top row. Scale each row so that it's length is 1, whence B becomes unitary. If you can't build a unitary basis, then let B be any basis and move on.

Wait a minute - why can't we build a unitary basis?

Well this is abstract algebra, not real analysis, so the base field might be the integers mod p. A vector like [1,3,5] has length 0 mod 7, and cannot be scaled to a length of 1. So if unitary cannot be achieved, then let B be any basis and move on. M will be similar to a lower triangular matrix, but not unitarily similar.

Since x is eigen, the top row of BM is sx. Let C be the inverse of B. Consider B*M*C. To find the top row, multiply the top row of BM (which is sx) by the columns of C. The result is s in the upper left, and zeros across. Thus BMC begins to look like a lower triangular matrix.

By similarity, BMC has the same eigen values as M. One of them is s, in the upper left; the others are found in the submatrix below. This can be seen in the formula for det₁. The characteristic polynomial becomes x-s times the characteristic polynomial of the submatrix below.

Ignore the first row and column of BMC and consider the remaining n-1 dimensional matrix. Find P and Q, where Q is P inverse, to make this submatrix similar to a lower triangular matrix. This can always be done by induction. Now add an extra row of zeros above and to the left of P, and do the same for Q. Place a 1 in the upper left of the augmented versions of P and Q. Note that P*Q is still the identity matrix, and P and Q are unitary (if we are building unitary matrices).

Consider PBMCQ. BMC has s in the upper left and zeros across. Multiply by Q on the right, and the top row and left column remain the same, while the submatrix is multiplied by the submatrix of Q. Multiply by P on the left. The upper left entry is still s, and the rest of the first column is, well, who knows. The top row is still zeros, except for s in the upper left. Finally the submatrix, with P on the left and Q on the right, becomes lower triangular. Therefore the entire product, PBMCQ, is lower triangular. The result is similar to M via the invertible matrix PB, which is unitary (if P and B are unitary). That completes the proof.

In the complex numbers, u.v is defined as the sum of u_iv_i. Dot product is no longer commutative, but that isn't a showstopper. In fact, v.u is the conjugate of u.v. With this in mind, u.u is its own conjugate, and is real. Furthermore, u.u is nonzero as long as u is nonzero. Also, u.v is 0 iff v.u is 0. Thus an orthonormal matrix is well defined over C. Grams Schmid, and Schur's theorem, generalize to complex numbers, so that M is unitarily similar to a lower triangular matrix. An excursion into complex analysis is somewhat beyond the scope of this book, but it is worth at least a paragraph. If you are interested, go back up to the top of this section and run through the proof again; P can inddeed be made unitary over C.

The trace of a square matrix is the sum of its diagonal elements.

Let A and B be n×n matrices and consider the upper left entry of A*B. This is the sum of A_1,j×B_j,1, as j runs from 1 to n. The i^th entry in the diagonal is the sum of A_i,j×B_j,i. To find the trace of A*B, take the sum as i runs from 1 to n. This produces the sum of A_i,j×B_j,i, for all i and j between 1 and n. Yet this is symmetric with respect to A and B. Therefore the trace of A*B is the same as the trace of B*A.

If Q is a nonsingular matrix, consider the trace of QM/Q. This is the same as the trace of M/Q times Q, or M. The trace of a matrix is equal to the trace of any similar matrix. In other words, trace is basis invariant.

Given a matrix M, let T be the lower triangular matrix that is similar to M. You may need to expand the underlying field to do this, e.g. extend the reals up to the complex numbers. Once this is done, T can always be derived by Schur's theorem.

Recall that the determinant of T is the product of the diagonal elements. Subtract the variable s from these elements and multiply the binomials together to get the characteristic polynomial of T. The roots of this polynomial are, of course, the elements on the main diagonal. Thus the diagonal contains the eigen values, including multiplicities.

The trace of T is the sum of the diagonal elements, which happens to be the sum of the eigen values. Since eigen values are basis invariant, M has the same eigen values. M has the same trace as T, and the same eigen values, hence the trace is the sum of the eigen values.

The norm of a matrix is the product of its eigen values, including multiplicities. Again, the eigen values are basis invariant, so switch to a similar, lower triangular matrix T. The norm is now the product of the diagonal elements of T. This is also the determinant of T, which is the same as the determinant of M. So the norm is the determinant, or the product of the eigen values.

Since norm and trace can be computed from the entries of M, they belong to the base field F, even if some of the eigen values do not belong to F. If M is real, and an eigen value is 3+4i, another eigen value is 3-4i, so that their sum, and product, is once again real.

A block diagonal matrix has blocks along the main diagonal, and zeros elsewhere.

To be more precise, disjoint intervals define the blocks. If [2,5] establishes a block, then M_i,j could be nonzero when i is between 2 and 5, and j is between 2 and 5. Everything outside the specified blocks is zero. Here is a simple 4×4 block matrix, with blocks [1,2] and [3,4].

You may have noticed that every matrix is block diagonal, consisting of one block running from 1 to n. Well that's not very interesting, so let's say a block diagonal matrix has to have at least two blocks.

The trace of M is the sum of the trace of the blocks. That's pretty clear; just add up the elements along the main diagonal.

The determinant of M is the product of the determinants of the individual blocks. Build a block diagonal matrix P, and it's inverse block diagonal matrix Q, so that PMQ makes each block lower triangular. This makes the whole matrix lower triangular. Once transformed, the eigen values run down the main diagonal. These are the same eigen values of M, and the blocks of M. The product of these eigen values is the product of the eigen values grouped together by block. Therefore det(M) is the product of the determinants of each block.

Modify M all you like below the blocks; making M lower block triangular. That does not change the trace or norm. PMQ still makes each block lower triangular, as it did before, with the same eigen values. Thus the eigen values of a lower block triangular matrix are the eigen values of the individual blocks.

The span of two subspaces U and V is the smallest subspace containing both. This is the set of vectors x+y such that x ∈ U and y ∈ V. Verify that this is indeed a subspace, and it must be included in any subspace containing U and V, hence it is the span of U and V.

If U and V are disjoint (except for 0), then the span is called the sum, or the direct sum, or the direct product. Every vector in the span has a unique representation as x+y, where x comes from U and y comes from V. If this fails then x₁+y₁ = x₂+y₂, hence x₁-x₂ = y₂-y₁, and U and V intersect after all. We can also claim U and V are linearly independent. If x+y = 0 then x = -y, U contains -y, U contains y, and U and V intersect. To complete the circle, assume U and V are linearly independent. If they are not disjoint, if they share a common vector x, then write x + -x = 0, which contradicts independence.

In summary, the span is a direct sum (i.e. every vector in the span has a unique representation), iff U and V are disjoint, iff U and V are linearly independent spaces.

Some people write the direct sum using the plus operator, as in U+V. Others write it as U*V. I prefer the * notation, because the span really is a cross product of all possible vectors in both sets. Granted, the vectors are added together, as part of an abelian group, so + makes sense too; but it's still a cross product, and I lean towards U*V.

If U and V are independent, a basis for U and a basis for V combine to form a basis for U*V.

A subspace is invariant under a transformation if that subspace is mapped into itself. Don't assume the subspace is fixed by this transformation; that isn't necessarily the case. If a transformation rotates space about the z axis, The z axis is fixed, and the xy plane is invariant.

Given a linear transformation and an eigen value w, the eigen vectors with eigen value w form an invariant vector space. In fact each vector in that space remains in position; it is simply scaled by the eigen value w.

Zero is always invariant.

Show that the span and intersection of two invariant subspaces is an invariant subspace.

Subspaces are complementary if they are invariant and their direct sum produces the original space. Note that spaces are complementary with respect to a given transformation.

A transformation is nilpotent, with index p, if p is minimal, and applying the transformation p times squashes the entire vector space down to 0. If the transformation is implemented as a matrix M, M^p = 0.

If a nilpotent function M has index p, some vector z satisfies z*M^p-1 ≠ 0. This is a consequence of p being minimal.

Build a set of vectors z, zM, zM², zM³, and so on up to zM^p-1. These vectors are independent, and span a space of dimension p.

Suppose a linear combination of these vectors produces 0. Multiply through by M^p-1 on the right. Every term drops to 0 except the first term, cz. Yet this must still equal 0, hence the first coefficient is 0. Remove that term from the combination, and multiply through by M^p-2. This leaves only the second term, and its coefficient must be 0. Continue this process until all coefficients are 0. Thus the p vectors are linearly independent.

Since M moves each of these vectors onto another one, the space spanned by these vectors is invariant under M.

Set M = 0 for the trivial case, a nilpotent map with index 1. Since zM = 0, any nonzero z will serve, spanning a space of dimension 1.

The next trick is to find a complementary subspace. With M and z as described earlier, the repeated images of z span a space of dimension p. This space always has a complementary subspace relative to M, of dimension n-p. The proof is rather technical, so hang on to your hat.

Let W be a vector space of dimension n, and let M be a nilpotent transformation on W with index p. Select a vector z such that zM^p-1 is nonzero. Recall that zMⁱ, as i runs from 0 to p-1, forms a set of p independent vectors.

Let the subspace N_i be spanned by zM^j, for all j ≥ i. This is a descending chain of spaces, where N₀ has dimension p, N_i has dimension p-i, and N_p = 0. The N spaces will depend on the selection of z. That's ok; pick any z that builds a chain of length p, and on we go. Note that z is in our vector space; there is no need to extend the base field.

Let T_i be W*Mⁱ. This is another descending chain of spaces, with T₀ = W, and T_p = 0. This chain does not depend on the selection of z.

Show that T_i contains N_i. It contains (z)Mⁱ, and (zM)Mⁱ, and (zM²)Mⁱ, and so on.

The goal is to build V_i, such that V_i and N_i are disjoint subspaces, and the direct sum V_i*N_i = T_i, and V_i is invariant under M. (We already know N_i is invariant.) Here is an illustration with p = 5.

When i = p, the bottom row, V_p exists, and is equal to 0. Since M has index p, M^p maps all of W into 0, thus T_p = 0. With N_p and V_p = 0, N_p*V_p = T_p. Of course N_p and V_p are M invariant. Therefore V_p satisfies our criteria.

Take one step backwards, setting i = p-1. Now N_i is the one dimensional space spanned by y, where y = zMⁱ. Build a basis for T_i, starting with y, then let V_i be the space spanned by the basis vectors of T_i beyond y. Clearly V_i and y are linearly independent, and together they span T_i. Also, V_i and y are invariant under M; in fact they are both squashed down to 0. Thus V_i meets our criteria.

If p = 1 we are done. For p > 1, take the inductive step, working from p-1 back to 0. For notational convenience I will step back from 3 to 2. By induction there is a subspace V₃ corresponding to N₃. Let K₃ be the subspace satisfying K₃M ⊆V₃. Verify that K₃ is indeed a subspace.

If x is in V₃ then it is in T₃, which is the image of T₂ under M, hence the map is onto. As spaces, K₃M = V₃.

Since V₃ is invariant, applying M to V₃ remains inside V₃. Thus V₃ meets the definition of K₃, and V₃ lies in K₃. In other words, K₃ is an extension of V₃, and M squashes K₃ onto V₃.

Applying M to K₃ yields V₃, which is in K₃, hence K₃ is M invariant.

Next show that K₃ and N₂ span T₂. Let x be any vector in T₂. Let y = xM. Thus y is in T₃. By induction, y is a unique sum of two vectors, one from N₃ and one from V₃. Call these vectors q and r respectively. Remember that q is spanned by zM³, zM⁴, zM⁵, etc. Pull out a common factor of M, and q = sM, where s is spanned by zM², zM³, zM⁴, etc. Thus q = sM, where s is in N₂. Write xM = sM+r, or r = (x-s)M, and x-s is in K₃. An arbitrary x is spanned by N₂ and K₃.

Next, show N₂∩K₃ is contained in N₃. Intersect N₂*M and K₃*M, which is the same as N₃∩V₃, or 0. Our intersection lives in N₂, and when multiplied by M, the result is 0. Elements in N₂ that are one step away from 0 are in fact in N_p-1, i.e. a scale multiple of zM^p-1. Vectors of this form certainly belong to N₃, hence N₂∩K₃ lies in N₃.

Consider N₂∩K₃∩V₃. With the first intersection in N₃, and N₃ and V₃ disjoint, the result is 0. Since V₃ is contained in K₃, N₂∩V₃ = 0. We built V₃ to be disjoint from N₃, and it is, but it is also disjoint from N₂. N₂ gets bigger, as T₂ gets bigger, but N₂ does not collide with V₃.

Let S be the direct sum of N₂∩K₃ and V₃. With N₂ and V₃ disjoint, the direct sum is well defined. Clearly S contains V₃.

Elements of S are produced by members of V₃ and K₃, hence S is contained in K₃. In other words, V₃ ⊆S ⊆K₃.

Both K₂ and V₃ lie in K₃, hence V₂ is in K₃. Thus M*V₂ lies in V₃, which is part of V₂, hence V₂ is M invariant.

Consider N₂∩V₂. Suppose x lies in both, and write x as q+r, where q is in V₃ and r is in K₂. Remember that N₂ and V₃ are linearly independent, hence no part of x lies in V₃. Therefore x lies in K₂, which is a subset of K₃. With x in K₃, and N₂, x is in their intersection, which was used to build S. Now S and K₂ are disjoint, so x = 0. Therefore N₂ and V₂ are disjoint.

Finally we have the last criterion, N₂ and V₂ span T₂. Remember that V₂ is the direct sum of K₂ and V₃. We need to show N₂, K₂, and V₃ span T₂. We know that N₂ and K₃ span T₂ (shown earlier). Find a representation for an arbitrary vector x as p+q+r, where p is in N₂, q is in S, and r is in K₂. Review the definition of S. Part of q comes from N₂, and the other part comes from V₃. The former is obviously in our span. Since V₃ lies in V₂, the latter is also in our span. There is no trouble with p and r, hence x is spanned. Conversely, note that N₂, V₃, and K₂ are all in T₂. The span of N₂ and V₂ is precisely T₂. The space V₂ satisfies our criteria, and that completes the inductive step.

March all the way up to T₀, which equals W. The space N₀ has a complementary space V₀, such that W is their direct sum, and both subspaces are M invariant.

Build a new basis for M, starting with N₀ (i.e. z and its ongoing images), and then V₀. The new matrix is block diagonal, with N₀ in the upper left and V₀ in the lower right. In fact we know what the upper block looks like. The transformation moves each basis vector onto the next one, hence it has ones just below the main diagonal, and zeros elsewhere. Let z be the bottom basis vector in this block, [0,0,0,… 1]. Multiply by M and shift left, to [0,0,…,1,0]. Repeat this, up to the highest basis vector [1,0,0,…], which then falls off the edge and becomes 0, as you would expect from a nilpotent transformation.

With these blocks established, restrict M to V₀, the lower right block. This is still a nilpotent transformation. Perform the very same procedure, giving two new complementary subspaces. This splits the lower right block into two blocks. Thus our matrix now has three blocks. The first is unchanged, and the second looks like the first, with ones on the subdiagonal and zeros elsewhere. The third block, in the lower right, represents yet another subspace with a nilpotent transformation. Apply the process again, and again, until the entire matrix consists of these blocks.

After a change of basis, the new, similar matrix becomes block diagonal, where each block has ones on its subdiagonal and zeros elsewhere. Thus every nilpotent matrix is similar to a matrix that is zero everywhere, except for scattered ones along the subdiagonal. The intermittent zeros on the subdiagonal delimit the blocks. For instance, consider a 6×6 matrix with 2 blocks [1,2][3,6]. The first block comes from N₀, and the second from V₀, which has then been transformed into its own subdiagonal representation. Notice that 0, in position 3,2, separates the two blocks.

Let M be a nilpotent transformation on n-space. If the basis is chosen properly, the basis vectors can be partitioned into sets, so that Within each set, M moves one vector onto the next, onto the next, onto the next, and so on, until the last vector is squashed down to 0. A set of size one is a lone vector that is mapped to 0. Each set becomes a block in the block diagonal matrix. If all sets are lone vectors, all vectors are mapped to 0, and M is the zero matrix.

The index of M, as a nilpotent transformation, is the size of the largest set, or block. Thus the maximum possible index of a nilpotent transformation is n, the dimension of the space. This happens when all n vectors participate in the march to zero, and all entries in the subdiagonal of M are 1. Verify that the powers of M shift the ones down and to the left, until M^n-1 has 1 in the lower left corner, and Mⁿ is zero.

A jordan block j_r(l) is an r×r matrix with l down the main diagonal and 1's on the subdiagonal. If r = 1 then there is no subdiagonal; that's ok.

A matrix is in jordan canonical form if it is block diagonal, and each block is a jordan block.

A diagonal matrix is in jordan form; each block has size 1.

A diagonalizable matrix is similar to a diagonal matrix (by definition), and its diagonal equivalent is in jordan form.

Every nilpotent matrix m is similar to a matrix in jordan form. This was proved in the previous section. The jordan blocks all have zeros on the main diagonal, e.g. j_r(0). Thus the matrix m has zeros down its main diagonal. Being a lower triangular matrix, these are also the eigen values. This makes sense, for a single, nonzero eigen value would prevent m from being nilpotent. The corresponding eigen vector persists, scaled again and again by the eigen value.

Here is a sample matrix in jordan form, with eigen values 0, 2, 3, 5, and 7.

Let the elements of M, and the eigen values of M, generate a field F. A conjugating matrix in F now turns M into its jordan form equivalent. The proof is just a few steps away.

Let M be a singular n×n matrix that is not nilpotent, and let W be all of n space. Let W*M represent the image of W under M, which is really the span of the rows of M. Since M is singular, this is a proper subspace of W.

Consider the image of M², which is the same as mapping W through M twice. If this produces a smaller subspace, then repeat the process. Eventually we're going to run out of dimensions, so assume W*M^j+1 = W*M^j. We don't have to worry about an image of 0, because M is not a nilpotent transformation. Thus M^j produces a proper subspace between 0 and W.

Let K be the kernel of M^j, and let R be the range.

Another application of M, beyond M^j, does not change the range. Thus R is M invariant.

Since the range does not change with another application of M, the kernel does not change either. If K is the kernel of M^j, K is also the kernel of M^j+1. Thus KM is a space, that when mapped through M^j, is 0. KM lies in the kernel of M^j, and K is M invariant.

Suppose K and R intersect in x. Find the preimage y such that x = yM^j. Since x is also in the kernel, yM^2j = 0. This means y is in the kernel of M^2j, which is also the kernel of M^j. In other words, y is in K, and that means x = 0. Therefore R and K are disjoint.

Being kernal and range, the dimension of R plus the dimension of K = n. Since K and R are disjoint they span a space of dimension n. This is a subspace of W, which also has dimension n; thus the direct sum of K and R yields W.

We have produced to proper complementary spaces inside W, relative to the transformation M. When M is restricted to K the result is a nilpotent transformation with index j. When M is restricted to R the map is onto, and invertible.

After a change of basis, M is block diagonal, with the nilpotent kernel in the upper left and the invertible range in the lower right. Convert K into jordan form, then concentrate on R.

This applies when some, but not all, of the eigen values of M are 0. Convert M to lower triangular, and some, but not all, of the diagonal is 0. If the diagonal was all zero then M² would push the nonzero entries down and to the left, M³ would push them down further, and Mⁿ would be 0, thus nilpotent. If the diagonal was entirely nonzero then M would be nonsingular. So this procedure pulls out the space with eigen values of 0, and turns it into jordan form, leaving a complementary space wherein M is invertible.

Now for the finale. Each equivalence class of similar matrices is represented by a unique matrix in jordan canonical form.

There are two parts to this proof. Given an arbitrary matrix M, find a similar matrix in jordan form that can act as its representative. Then, show that different jordan matrices represent different classes. Thus each jordan matrix is a faithful representative of its class.

Let M have an eigen value l. If l = 0 then separate out the corresponding eigen space and turn it into jordan form, as described above. Once this is done, concentrate on the lower right block, where all the eigen values are nonzero. Relabel this block as M, and proceed.

Let l be any eigen value and let T be M with l subtracted from the main diagonal. 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. (This change of basis may require an extension of the base field F by the eigen value l.)

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. In the same way, R is M invariant. Turn M into a block diagonal matrix, where the upper left block operates on K and the lower right block operates on R. Once again set T = M-l.

Since the upper left block of T is nilpotent, turn it into jordan form. Write PT/P = J, where J has jordan blocks in the upper left. Add l to T and note that l commutes with P. (In fact l commutes with everything.) Thus PM/P = J+l. The jordan blocks are now marked with the eigen value l that created them. Each block has l down the diagonal and ones on the subdiagonal.

If R is nontrivial then there are other eigen values to consider. Step through them one at a time, creating jordan blocks for each eigen value. Finally M is transformed into a series of jordan blocks, a matrix in jordan form.

Next show that different jordan 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. 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 jordan matrices are not similar? Start by finding properties of a matrix that do not change under similarity. 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 in mind, 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.

Consider two jordan matrices, each with l down the main diagonal, that are similar by assumption. If two matrices are similar then they are similar after you subtract l from the main diagonal. Now the two matrices are nilpotent. The index p, wherein M^p = 0, does not change with similarity, thus both matrices have the same index p, which is the size of the largest jordan block. Both matrices have blocks j_p(0).

How many blocks of size p? Find z, as described earlier, so that the images of z span a space of dimension p, before the last image of z drops to 0. Do this on either side. This consumes one jordan block of size p from each matrix. If there is another jordan block of size p then there is another z, outside the span of the last eigen space, with index p. Build a new eigen space using this vector, then look for another independent vector of index p, and so on. The number of p dimensional eigen spaces that can be built in this manner determines the number of jordan blocks of size p.

Once these spaces are established, move on to a smaller index q. Find z such that the images of z span a space of dimension q, and z is independent of the eigen spaces of dimension p that have gone before. This establishes a jordan block of size q. Continue this process until all the jordan blocks are determined, and all via properties of the nilpotent transformation that do not change under similarity. Therefore, if two jordan matrices are similar, they must contain the same jordan blocks, of the same sizes. That completes the proof.