Finding Jordan Normal Form of Matrices

[Sudharaka]

Hi everyone, :)

I have very limited knowledge on linear algebra and things like Jordan Normal form of matrices. However I am currently doing an Advanced Linear Algebra course which is compulsory and I am trying hard to understand the content which is quite difficult for me. One of the things that we have to study recently is about Jordan Normal form. Can anybody explain what's the easiest procedure to find the Jordan Normal form of a given matrix. I am talking about general matrices of any dimension not particular cases like \(2\times 2\) or \(3\times 3\) matrices.

For example we were given to find the Jordan Normal form for,

\[A=\begin{pmatrix}1&1&1&\cdots&1\\0&1&1&\cdots&1\\0&0&1&\cdots&1\\.&.&.&\cdots &.\\0&0&0&\cdots&1\end{pmatrix}\]

Thanks very much. :)

 

[I like Serena]

Hi everyone, :)

I have very limited knowledge on linear algebra and things like Jordan Normal form of matrices. However I am currently doing an Advanced Linear Algebra course which is compulsory and I am trying hard to understand the content which is quite difficult for me. One of the things that we have to study recently is about Jordan Normal form. Can anybody explain what's the easiest procedure to find the Jordan Normal form of a given matrix. I am talking about general matrices of any dimension not particular cases like \(2\times 2\) or \(3\times 3\) matrices.

For example we were given to find the Jordan Normal form for,

\[A=\begin{pmatrix}1&1&1&\cdots&1\\0&1&1&\cdots&1\\0&0&1&\cdots&1\\.&.&.&\cdots &.\\0&0&0&\cdots&1\end{pmatrix}\]

Thanks very much. :)

Hi Sudharaka!

The standard method is to determine the eigenvalues.
Those go to the main diagonal.
After that you need to find the eigenvectors.
The process of doing so tells you how large the blocks are.

When you have an upper triangular matrix, it becomes easy to find the eigenvalues.
Calculating det(A-tI)=0 gives immediate results.
In particular the eigenvalues are simply the entries on the main diagonal.
In your case they are all 1.

Next question: how many independent eigenvectors are there?
Or put otherwise, what is the dimension of the kernel of (A-tI)?
You can find it by solving (A-tI) = 0.

In your case, using the normal method of solving a set of equations, you can find that the only solution is (1,0,0,0,...). In other words, the dimension of the kernel is 1.
This means there is only 1 Jordan block.
So the Jordan Normal form is:
\begin{pmatrix}
1&1&0&\cdots&0\\
0&1&1&\cdots&0\\
0&0&1&\cdots&0\\
.&.&.&\cdots &.\\
0&0&0&\cdots&1
\end{pmatrix}

 

[Sudharaka]

Hi Sudharaka!

The standard method is to determine the eigenvalues.
Those go to the main diagonal.
After that you need to find the eigenvectors.
The process of doing so tells you how large the blocks are.

When you have an upper triangular matrix, it becomes easy to find the eigenvalues.
Calculating det(A-tI)=0 gives immediate results.
In particular the eigenvalues are simply the entries on the main diagonal.
In your case they are all 1.

Next question: how many independent eigenvectors are there?
Or put otherwise, what is the dimension of the kernel of (A-tI)?
You can find it by solving (A-tI) = 0.

In your case, using the normal method of solving a set of equations, you can find that the only solution is (1,0,0,0,...). In other words, the dimension of the kernel is 1.
This means there is only 1 Jordan block.
So the Jordan Normal form is:
\begin{pmatrix}
1&1&0&\cdots&0\\
0&1&1&\cdots&0\\
0&0&1&\cdots&0\\
.&.&.&\cdots &.\\
0&0&0&\cdots&1
\end{pmatrix}

Hi I like Serena, :)

Thanks so much for the answer. It's not about the answer to this question that matters to me, but I am trying to grasp how to find the Jordan Normal form of a general matrix. So we'll carry on the discussion until I am good with Jordan Normal form. :p

Let me summarize the procedure of finding the Jordan normal form of a matrix. We shall take the matrix,

\[A=\begin{pmatrix}1&-3&4\\4&-7&8\\6&-7&7\end{pmatrix}\]

The eigenvalues of this matrix are \(\lambda=-1,\,-1,\,3\) and the corresponding eigenvectors are, \((1,\,2,\,1)\) and \(1,\,2,\,2\). Since there are two linearly independent eigenvectors we know that there are two Jordan cells.

\[J_{1}(-1)=\begin{pmatrix}-1&1\\0&-1\end{pmatrix}\]

\[J_{2}(3)=\begin{pmatrix}3\end{pmatrix}\]

So I can write the Jordan normal form in two ways,

\[J=\begin{pmatrix}3&0&0\\0&-1&1\\0&0&-1\end{pmatrix}\]

or

\[J=\begin{pmatrix}-1&1&0\\0&-1&0\\0&0&3\end{pmatrix}\]

Correct me if I am wrong. :)

 

[Petrus]

Hi I like Serena, :)

Thanks so much for the answer. It's not about the answer to this question that matters to me, but I am trying to grasp how to find the Jordan Normal form of a general matrix. So we'll carry on the discussion until I am good with Jordan Normal form. :p

Let me summarize the procedure of finding the Jordan normal form of a matrix. We shall take the matrix,

\[A=\begin{pmatrix}1&-3&4\\4&-7&8\\6&-7&7\end{pmatrix}\]

The eigenvalues of this matrix are \(\lambda=-1,\,-1,\,3\) and the corresponding eigenvectors are, \((1,\,2,\,1)\) and \(1,\,2,\,2\). Since there are two linearly independent eigenvectors we know that there are two Jordan cells.

\[J_{1}(-1)=\begin{pmatrix}-1&1\\0&-1\end{pmatrix}\]

\[J_{2}(3)=\begin{pmatrix}3\end{pmatrix}\]

So I can write the Jordan normal form in two ways,

\[J=\begin{pmatrix}3&0&0\\0&-1&1\\0&0&-1\end{pmatrix}\]

or

\[J=\begin{pmatrix}-1&1&0\\0&-1&0\\0&0&3\end{pmatrix}\]

Correct me if I am wrong. :)

hello,
Actually I have not started with Jordan normal form (with My book) but for some reason I remember some from My lecture if I am correct that the highest eigenvalue should be first and Then comes lower. (Maybe someone can confirmed this)

Regards,
\(\displaystyle |\pi\rangle\)

 

[I like Serena]

Hi I like Serena, :)

Thanks so much for the answer. It's not about the answer to this question that matters to me, but I am trying to grasp how to find the Jordan Normal form of a general matrix. So we'll carry on the discussion until I am good with Jordan Normal form. :p

Let me summarize the procedure of finding the Jordan normal form of a matrix. We shall take the matrix,

\[A=\begin{pmatrix}1&-3&4\\4&-7&8\\6&-7&7\end{pmatrix}\]

The eigenvalues of this matrix are \(\lambda=-1,\,-1,\,3\) and the corresponding eigenvectors are, \((1,\,2,\,1)\) and \(1,\,2,\,2\). Since there are two linearly independent eigenvectors we know that there are two Jordan cells.

\[J_{1}(-1)=\begin{pmatrix}-1&1\\0&-1\end{pmatrix}\]

\[J_{2}(3)=\begin{pmatrix}3\end{pmatrix}\]

So I can write the Jordan normal form in two ways,

\[J=\begin{pmatrix}3&0&0\\0&-1&1\\0&0&-1\end{pmatrix}\]

or

\[J=\begin{pmatrix}-1&1&0\\0&-1&0\\0&0&3\end{pmatrix}\]

Correct me if I am wrong.

Nothing to correct. You've got it. ;)
I didn't check the calculations though.

hello,
Actually I have not started with Jordan normal form (with My book) but for some reason I remember some from My lecture if I am correct that the highest eigenvalue should be first and Then comes lower. (Maybe someone can confirmed this)

Regards,
\(\displaystyle |\pi\rangle\)

In the Jordan Normal form nothing is said about ordering.
We're free to pick any ordering we'd like.
I do prefer some ordering though.

 

[Sudharaka]

hello,
Actually I have not started with Jordan normal form (with My book) but for some reason I remember some from My lecture if I am correct that the highest eigenvalue should be first and Then comes lower. (Maybe someone can confirmed this)

Regards,
\(\displaystyle |\pi\rangle\)

No, from my recent knowledge about Jordan form, acquired through reading mainly the Wikipedia article, the Jordan form doesn't need to be unique(unless one agrees on some ordering convention of blocks) or in other words there's no ordering of Jordan blocks according to eigenvalues. Here's how Wikipedia puts it,

In spite of its name, the normal form for a given \(M\) is not entirely unique, as it is a block diagonal matrix formed of Jordan blocks, the order of which is not fixed; it is conventional to group blocks for the same eigenvalue together, but no ordering is imposed among the eigenvalues, nor among the blocks for a given eigenvalue, although the latter could for instance be ordered by weakly decreasing size.

Nothing to correct. You've got it. ;)
I didn't check the calculations though.

In the Jordan Normal form nothing is said about ordering.
We're free to pick any ordering we'd like.
I do prefer some ordering though.

Thanks very much for the confirmation. :)

 

[I like Serena]

Thanks very much for the confirmation. :)

It becomes more challenging when you have more than 1 jordan block for the same eigenvalue.
Then you have to figure out how large the blocks are.
Then we're talking about pretty big matrices though.

 

[Sudharaka]

It becomes more challenging when you have more than 1 jordan block for the same eigenvalue.
Then you have to figure out how large the blocks are.
Then we're talking about pretty big matrices though.

Okay, I am assuming that you are talking about the case where some eigenvalues corresponds to several eigenvectors such that the number of eigenvectors exceeds the number of distinct eigenvalues. Am I correct? :)

 

[I like Serena]

Okay, I am assuming that you are talking about the case where some eigenvalues corresponds to several eigenvectors such that the number of eigenvectors exceeds the number of distinct eigenvalues. Am I correct? :)

Yes.
Suppose you have an eigenvalue with algebraic multiplicity 5 (appears 5 times on the main diagonal) and with 2 independent eigenvectors.
Then there is more than 1 possibility how to divide the Jordan blocks and you would need to find the right one (or rather "a" right one).

 

[Sudharaka]

Yes.
Suppose you have an eigenvalue with algebraic multiplicity 5 (appears 5 times on the main diagonal) and with 2 independent eigenvectors.
Then there is more than 1 possibility how to divide the Jordan blocks and you would need to find the right one (or rather "a" right one).

And what is the general (and the most convenient) procedure to find the right one? :)

One of the ways to do this, I guess, is to find out the sizes of the Jordan blocks by using the formula given at the end of >>this<< section. Am I correct? :)

 

[I like Serena]

And what is the general (and the most convenient) procedure to find the right one? :)

One of the ways to do this, I guess, is to find out the sizes of the Jordan blocks by using the formula given at the end of >>this<< section. Am I correct? :)

Yes. Exactly. That article gives a procedure to find the generalized eigenvectors that span each root space.

In the example of 5 equal eigenvalues with 2 independent eigenvectors, you don't have to find all generalized eigenvectors though.
It suffices to find 1 corresponding to each eigenvector.
That's enough to decide how large the Jordan blocks are.

 

[Deveno]

Ideally, we would hope that we could find an eigenbasis for a linear transformation $T:V \to V$, that is, a basis for $V$ such that every basis vector is an eigenvector. However, this is not always possible, because the dimension of an eigenspace:

$E_{\lambda} = \{v \in V: Tv = \lambda v\}$

might be less than the algebraic multiplicity of an eigenvalue. For example, the matrix:

$A = \begin{bmatrix}1&1\\0&1 \end{bmatrix}$

has characteristic polynomial $(x - 1)^2$ so its only eigenvalue (1) has algebraic multiplicity 2 (it is a double root), but we see that:

$A(x,y) = (x+y,y)$

So if $A(x,y) = (x,y)$ we have to have $y = 0$, meaning the eigenspace corresponding to 1 only has dimension 1, instead of 2 (and is generated by the egienvector $(1,0)$).

So...given this sorry state of affairs, how should we pick a "next-best choice" to extend our set of one eigenvector to a full basis?

One way is to note that: $E_1 = \text{ker}(A - I)$. Since this kernel is bigger than merely {0}, but is not all of $\Bbb R^2$ we ought to pick a non-zero vector $v$ such that:

$v \not\in \text{ker}(A - I)$

But if $v = (A - I)u$, then $(A - I)v = (A-I)^2u = 0$ (since $A^2 - I = 0$ by Cayley-Hamilton).

In other words, our second vector is an element of:

$\text{ker}(A - I)^2$, but not $\text{ker}(A - I)$.

Such a vector is called a "generalized eigenvector" belonging to 1.

The nifty thing is that this approach works with each eigenvalue of a general linear transformation (of a finite-dimensional vector space). The reason being is that generalized eigenvectors belonging to a certain eigenvalue $\lambda$ don't belong to any other eigenvalue (repeatedly applying $T - \lambda I$ keeps "shrinking" the vector space). This can be used in calculating the Jordan form.

For example:

consider

$A = \begin{bmatrix}1&2&-1\\0&2&0\\1&-2&3 \end{bmatrix}$

which has characteristic polynomial:

$\det(xI - A) = \begin{vmatrix}x-1&-2&1\\0&x-2&0\\-1&2&x-3 \end{vmatrix}$

$= (x - 2)\begin{vmatrix}x-1&1\\-1&x-3 \end{vmatrix} = (x - 2)[(x-1)(x-3) - (1)(-1)]$

$= (x - 2)(x^2 - 4x + 3 + 1) = (x - 2)^3$.

So our only eigenvalue is 2. Solving:

$A - 2I = 0$ yields:

$\begin{bmatrix}-1&2&-1\\0&0&0\\1&-1&1 \end{bmatrix}\begin{bmatrix}x\\y\\z \end{bmatrix} = \begin{bmatrix}0\\0\\0 \end{bmatrix}$

which results in the single equation:

$x - 2y + z = 0$, so a general solution is:

$(s,t,2t-s) = s(1,0,-1) + t(0,1,2)$ thus we have two linearly independent eigenvectors: (1,0,-1) and (0,1,2) (other choices are possible, just so you know).

Now we have that $(A - 2I)(x,y,z) = (-x+2y-z,0,z-2y+z)$, and applying $A-I$ one more time, we find $(A - 2I)^2(x,y,z) = 0$ for any choice of x,y, and z. So all we need to do is find any vector not in the span of our two eigenvectors. In this case, that means ANY vector that is not an eigenvector. Clearly (1,0,0) will do. Since $(A-2I)(1,0,0) = (-1,0,1)$, let's replace the eigenvector (1,0,-1) with its negative (this doesn't affect our eigenspace).

Now we have the basis {(-1,0,1),(1,0,0),(0,1,2)}. If we take our change of basis matrix to be:

$P = \begin{bmatrix}-1&1&0\\0&0&1\\1&0&2 \end{bmatrix}$

with inverse:

$P^{-1} = \begin{bmatrix}0&-2&1\\1&-2&1\\0&1&0 \end{bmatrix}$

we have:

$P^{-1}AP = \begin{bmatrix}2&1&0\\0&2&0\\0&0&2 \end{bmatrix}$

which is the desired Jordan form.