Jordan normal form – Graph Theory
by Arjun Jain
The last post was about the usual generalized eigenspaces approach to Jordan normal forms. Here I’ll describe another approach using the language of graph theory as in Turnbull and Aitken’s proof, in the article The Jordan Canonical Form: an Old Proof by Richard A. Brualdi.
Consider an complex matrix . The associated digraph (directed graph) has vertices (labelled ) and has an arc from vertex to if .
Now by Schur’s Theorem, every matrix A is similar to an upper triangular matrix, . Note that for upper triangular matrices, the associated digraphs have arcs only from lower to higher vertices.
In a digraph , where all s are distinct and where are all arcs of , is called a cycle.
Note that since the arcs of the digraph of a triangular matrix only follow one direction, these are acyclic graphs. The converse is not true. However, a matrix with an acyclic digraph can be made triangular by a permutation similarity. To see this, note that if we have an acyclic graph we only need to reorder the vertices so that all arcs point towards higher numbered or lower numbered vertices. So for example, if you want to exchange the vertices and , the permutation matrix operated on the right will redirect all arcs going to , to and vice verse. Operated on the left, it will redirect all arcs coming from to now come from , and vice verse.
Also, a path in is a sequence of distinct vertices such that are all arcs of . A digraph with such an arc is called a path digraph. Again, any matrix with a path digraph can be brought to the form where the path goes from the smallest vertex to the largest vertex or vice verse, by a permutation similarity.
An example of a matrix with a path digraph is . This looks like a Jordan block!
To make all the non zero super diagonal entries , we can use a diagonal similarity. So if a diagonal matrix is represented by , then for the above example the matrix that works is .
The digraph of the Jordan form of a given , say has a more complicated form. It is a collection of paths which considered pairwise, have no common vertices. Each path here is associated with a single eigenvalue, although an eigenvalue can be associated with multiple paths. As an example has the following digraph:
Now to the main point. Jordan’s theorem can be rephrased in the language of graph theory as: Every matrix is similar to a matrix , whose digraph is a collection of pairwise vertex disjoint paths where each path is associated with exactly one eigenvalue.
For the proof, we need the permutation, diagonal and combination similarities. The combination similarity applied to a matrix , adds times column of to , and times row of to row . The actual form of is the identity matrix with in the position, where . The inverse has a in place of the .
To see how a combination symmetry affects an upper triangular matrix :
If , then of course .
Theorem: An matrix is similar to a matrix which is a direct sum of Jordan blocks, where a Jordan Block is a matrix with a single eigenvalue as all its diagonal terms and ones on the super diagonal.
1. By Schur’s theorem, there exists an invertible such that , where is upper triangular. Here equal diagonal entries can be made to occur consecutively.
2. Consider the block form of , i.e. . Here is an upper triangular matrix with equal diagonal entries, say , and is an upper triangular matrix, none of whose diagonal entries are equal to . Using combination similarities, can be made 0 without altering or .
We can repeat the process in 2. again and again, till is a direct sum of constant diagonal upper triangular matrices. …
Let’s first consider an upper triangular matrix , with all diagonal entries equal to some . We now use an induction argument:
a. If n=1, , which is already a Jordan block. If n=2, . The here can be made by a diagonal symmetry, giving a Jordan block.
b. Suppose that upper triangular matrices as above can be transformed into Jordan forms. Then so can the leading upper triangular block of an upper triangular matrix. So,
, where subscripts indicate the size of the blocks, and is for a possible non zero block.
Following b., we have
Now, to complete the argument, we just need to show that the middle matrix in the above expression can be reduced to it’s Jordan form. As an example, consider the following matrix:
As the combination symmetry only affects the parts of row and column to the right and to the top of the element respectively, we can make most of the elements of the last column in the above matrix 0. For instance, if element is , then makes this 0 due to presence of a in the 4th column. This can be done for all elements in the last column except and which do not have s available in their respective rows.
We’re almost there. If both and are 0, we already have the Jordan form. If both of them are non zero, using a diagonal symmetry we can make the second last element of the last column, , here equal . Now if is , then if we do a followed by a , element becomes . We follow a similar procedure for any other pairs of non zero entries left in the general case, always eliminating the non zero entry across the smaller Jordan block. This will leave us with one non zero non diagonal entry in the last column. With a permutation similarity, this can be brought to be the second last element of the last column giving us a Jordan Form.
Thus, we have proved the existence of a Jordan form for every matrix.