JCF algorithm - LA with Sage


Jordan Canonical Form; an algorithmic approach

Ajit Kumar at ICT, Mumbai

Sang-Gu Lee at SKKU, Korea

       

In this worksheet, we look at steps to compute a Jordan Canonical form of a matrix. Let $A$ be an $n\times n$ matrix. Note that if $A$ does not have enough eigenvectors, it may not be diagonalizable. In this case, we want to transform $A$ into its Jordan Canonical form. For more information on the Jordan Canonical Form, users are encouraged to consult any standard Linear Algebra textbook. Let $\lambda$ be an eigenvalue of $A$ of multiplicity $r$. Suppose $v\neq 0$ be an eigenvector corresponding to an eigenvalue $\lambda$, then $$ (A-\lambda I) v=0.$$ If the above equation has fewer than $r$, linearly independent solutions, then we would not have enough eigenvectors to diagonalize $A$. In this case, generalized eigenvectors are useful. A vector $v$ is said to be a generalized eigenvector with respect to the eigenvalue $\lambda$ if $$(A-\lambda I)^kv=0$$ for some positive integer $k$.

Example: Find generalized eigenvectors of $A=\left(\begin{array}{rrr} 1 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & -1 & 1 \end{array}\right)$.

Compute the characteristic polynomial, eigenvalues and their corresponding eigenvectors of $A$.







Check if $(A-\lambda I) x_1 = 0$.




Solve $(A-\lambda I) x_2 = x_1$ to obtain $x_2$.




Check if $(A-\lambda I)^2 x_2 = 0$.




Since $(A-\lambda I)^2x_2=0$, $x_2=(0,1,0)$ is a generalized eigvenvector of $A$ of index 2 corresponding to $\lambda=1$.

       

Solve $(A-\lambda I) x_3 = x_2$ to obtain $x_3$.




Check if $(A-\lambda I) x_3 = 0$.




Check if $(A-\lambda I)^2 x_3 = 0$.




Check if $(A-\lambda I)^3 x_3 = 0$.




Since $(A-\lambda I) x_3 \neq 0, (A-\lambda I)^2x_3\neq 0$,and  $(A-\lambda I)^3x_3=0$, $x_3=(1,0,0)$ is a generalized eigvenvector of $A$ of index 3 corresponding to $\lambda=1$.

       

Let $\lambda$ be an eigevnvalue of $A$ of multiplicity $r$.

The basic idea is to find $r$ generalized eigenvectors corresponding to $\lambda$. Finding the Jordan form is now a matter of sorting these generalized eigenvectors into an appropriate order.

To find the Jordan form, carry out the following procedure for each eigenvalue of $A$.

 

Procedure:

1. First, solve $(A-\lambda I)v=0$ for each eigenvalue $\lambda$ of $A$. Let $r_1$ be the number of linearly independent solutions of $(A-\lambda I)v=0$. If $r_1=r$, then we are in good shape; otherwise

2. Solve $(A-\lambda I)^2v=0$.  Let $r_2$ be the number of linearly independent solutions of $(A-\lambda I)^2v=0$. If $r_2=r$, then we are in good shape; otherwise

3. Solve $(A-\lambda I)^3v=0$. Let $r_3$ be the number of linearly independent solutions of $(A-\lambda I)^3v=0$. If $r_3=r$, then we are in good shape. We continue this process until we get $r_N=r$ for some $N$.

 

The number $N$ is the size of the largest Jordan block associated to $\lambda$, and $r_1$ is the total number of Jordan blocks associated
to $\lambda$.


4. Next we define, $s_1=r_1$, $s_2=r_2-r_1, s_3=r_3-r_2$, $\ldots$, $s_N=r_N-r_{N-1}=r-r_{N-1}.$

$s_k$ is the number of Jordan blocks of size at least $k\times k$ associated to $\lambda$.

5. Next define, $m_1=s_1-s_2$, $m_2=s_2-s_3, m_3=s_3-s_4$, $\ldots$, $m_{N-1}=s_{N-1}-r_{N}$ and $m_N=s_N$.

Then $m_k$ is the number of $k\times k$ Jordan blocks associated to $\lambda$.


Once we have done this for all the eigenvalues of $A$, we will be able to get the Jordan Canonical form.




Example: Find a Jordan Canonical form of $A=\left(\begin{array}{rrrrrrrrrrr} 3 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 3 & 2 & 1 & 1 & 0 & -3 & 1 \\ 0 & 0 & 0 & 0 & -1 & 2 & 0 & 0 & 1 & -1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 3 & 0 & -6 & 5 & -1 \\ 0 & 0 & 0 & 0 & 0 & 2 & 1 & 4 & 1 & -3 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -2 & 5 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -2 & 0 & 5 \end{array}\right)$













$A$ has two eigenvalues, $\lambda=5$ of multiplicity 2 and $\lambda=3$ of multiplicilty 9.




The above computaions in Sage show that there are two eigenvectors w.r.t. $\lambda=5$ and there are only three eigenvectors w.r.t. eigenvalue $\lambda=3$.

Let us deal with Jordan blocks corresponding  to $\lambda=3$.

Since the multiplicity of $\lambda=3$   is 9, we have $r=9$.




Since ${\rm rank} (A-3I)=8$, there are three linearly independent solutions of $(A-3I)v=0$. That is, $r_1=3$







Since ${\rm rank}(A-3I)^2=5$, there are six linearly independent solutions of $(A-3I)^2v=0$. That is, $r_2=6$







Since ${\rm rank} (A-3I)^3=3$, there are eight linearly independent solutions of $(A-3I)^2v=0$. That is, $r_3=8$







Since ${\rm rank} (A-3I)^4=2$, there are nine linearly independent solutions of $(A-3I)^4v=0$. That is, $r_4=9=r$. We stop at this stage.




Now let us find $s_1,s_2,s_3,s_4$ and $m_1,m_2,m_3,m_4$.

Thus there is a $2 \times 2$,  a $3 \times 3$ and  a $4 \times 4$  Jordan block corresponding to $\lambda=3$.

That is, we have

$$\left(\begin{array}{rrrr} 3 & 1 & 0 & 0  \\ 0 & 3 & 1 & 0  \\ 0 & 0 & 3 & 1\\ 0 & 0 & 0 & 3 \end{array}\right), \quad\left(\begin{array}{rrr} 3 & 1 & 0   \\ 0 & 3 & 1   \\ 0 & 0 & 3 \end{array}\right),\quad  \left(\begin{array}{rr} 3 & 1   \\ 0 & 3   \end{array}\right)$$

Now consider the second eigenvalue $\lambda=5$

Since there are two linearly indedepnt eigenvectors corresponding to eigenvalue $\lambda=5$, there are two $1\times 1$ Jordan block with respect to $\lambda=5$.

Thus the Jordan canonical form of $A$ looks like

$$J=\left(\begin{array}{rrrr|rrr|rr|r|r} 3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 0 & 0 & 0 & 0 & 3 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 3 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 3 & 0 & 0 & 0 & 0 \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 3 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 3 & 0 & 0 \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 5 & 0 \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 5 \end{array}\right)$$

Finding the transition matrix $P$ such that $P^{-1}AP=J$.

Since there is a  Jordan block of order $4\times 4$, we want a vector $v_1$ such that $(A-3I)^4v_1=0$ and $(A-3I)^3v_1\neq 0$.

Since there is a  Jordan block of order $3\times 3$, we want a vector $v_5$ such that $(A-3I)^3v_5=0$ and $(A-3I)^2v_5\neq 0$.

Since there is a  Jordan block of order $2\times 2$, we want a vector $v_8$ such that $(A-3I)^2v_8=0$ and $(A-3I)v_8\neq 0$.

Example: Find the Jordan canonical Form of

 $$\left(\begin{array}{rrrrrr} 0 & 0 & 0 & 0 & -1 & -1 \\ 0 & -8 & 4 & -3 & 1 & -3 \\ -3 & 13 & -8 & 6 & 2 & 9 \\ -2 & 14 & -7 & 4 & 2 & 10 \\ 1 & -18 & 11 & -11 & 2 & -6 \\ -1 & 19 & -11 & 10 & -2 & 7 \end{array}\right)$$










Hence $A$ has two eigenvalues: 2 with multiplicity 1 and -1 with multiplicity 5.

We solve $(A+I)x=0$.







Thus $A+I$ has 2 linearly independent vectors. That is $r_1=2$.

Now we solve $(A+I)^2x=0$




Clearly $(A+I)^2$ has 4 lineraly independent eigenvectors. That is, $r_2=4$.

Now we find $(A+I)^3$




Clearly $(A+I)^2$ has five linearly independet eigenvectors. That is, $r_3=5$ which is the multiplicity of the eigenvalue -1.

We find $s_1 = r_1 = 2, s_2 = r_2 − r_1 = 2$ and $s_3 = r_3 − r_2 = 1$. Also $m_3 = s_3 = 1, m_2 = s_2-s_3 = 1$
and $m_1 = s_1 − s_2 = 0$. Hence, associated to $\lambda=$ −1, there is a 2 by 2 and a
3 by 3 Jordan block. As the other eigenvalue $\lambda=2$ has multiplicity 1, then
there’s just a 1 by 1 Jordan block associated to $\lambda=2$. This means $A$ has follwoing jordan blocks:

$$\left(\begin{array}{rrr} -1 & 1 & 0 \\ 0 & -1 & 1 \\ 0 & 0 & -1 \end{array}\right), \quad \left(\begin{array}{rr} -1 & 1 \\ 0 & -1 \end{array}\right),\quad [2]$$













Let us find $P$ such that $P^{-1}AP=J$.

The Jordan blocks have sizes $N_1 = 3$ and $N_2 = 2$. We start by
finding a vector $v_1$ with $(A + I)^3v_1 = 0$ but $(A + I)^2v_1\neq 0$.

Now looking at the RREFs of $(A+I)^2 $ and $(A+I)^2$, it is not difficult to see that we can take

$v_1=(1,0,0,0,0,0)$.




Next we choose $v_4$ such that $(A+I)^2v_4=0$ and $(A+I)v_4\neq 0$. Again using the RREF of $(A+I)$ and $(A+I)^2$, we see that

$v_4=(1,1,2,0,0,0)$.




We take $v_6$ as the eivenvector corresponding to eigenvalue 2.










Example: Let us find a Jordan canonical form (JCF) and the trasition matrix of the JCF of

$$\left(\begin{array}{rrrrrr} 1 & 1 & 2 & -1 & 1 & 1 \\ -6 & 3 & 7 & -3 & 0 & 3 \\ -2 & 0 & 5 & -1 & 0 & 1 \\ -10 & 0 & 10 & -2 & 1 & 5 \\ 2 & 0 & -2 & 1 & 3 & -1 \\ -6 & 2 & 6 & -3 & 3 & 6 \end{array}\right)$$













First off, we consider the eigenvalue $\lambda=3$ and obtain generalized eigenvectors  associated to this. Hence $r=5$




$E_1(3)$ has dimension 2 with basis $\{(1, 0, 0, 0, 0, 2), (0, 0, 0, 1, 0, 1)\} =\{t_1,u_1\}$. Thus $r_1=2$.




$E_2(3)$ has dimension 4 with basis $\{(1, 0, 0, 0, 0, 2), (0, 0, 0, 1, 0, 1),(0,0,0,1,0,1),(0,0,0,0,1,0)\}$. Thus $r_2=4$.




$E_3(3)$ has dimension 5, which is the algebraic multiplicity of $\lambda=3$. Thus $r_3=5=r$.

$E_3(3)$ has a basis

$$\{(1, 0, 0, 0, 0, 2), (0,1, 0, 0, 0, 0),(0,0,1,0,0,-2),(0,0,0,1,0,1),(0,0,0,01,0)\}$$




Hence, associated to $\lambda=3$ , there is a $2\times 2$ and a $3\times 3$ Jordan block. As the other eigenvalue $\lambda=1$  has multiplicity 1, then
there’s just a $1\times 1$ Jordan block associated to $\lambda=1$ .

 

This means $A$ has the following Jordan blocks:

$$\left(\begin{array}{rrr} 3 & 1 & 0 \\ 0 & 3 & 1 \\ 0 & 0 & 3 \end{array}\right), \quad \left(\begin{array}{rr} 3 & 1 \\ 0 & 3 \end{array}\right),\quad [1]$$




Calculation of a Jordan Basis:

We want to choose $v_3 \in E_3(3)$ such that $v_3$ is not in $E_2(3)$. The calculations earlier suggest that we can take $v_3=(0,0,1,0,0,-2)$.

Then we can define $v_2=(A-3I)v_3$.







Next, we select $w_2$ such that $\{v_2,w_2,t_1,t_2\}$ is linearly independent. We can define

$w_2=(0,0,0,0,1,0)$. Then we define $w_1=(A-3I)w_2$.







Since the second eigenvalue $\lambda=1$ is of multiplocity 1 with eigenvector $(1, 10, 4, 22, -4, 8)$, we define

$x_1=(1, 10, 4, 22, -4, 8)$.




Now the transition matrix is defined as $P=[v_1 ~ v_2~ v_3 ~ w_1 ~ w_2~ x_1]$.







Let us find that the JCF of $A$ with the built-in Sage function.




Example: Find a JCF and a transition matrix of $A=\left(\begin{array}{rrrrrr} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & -1 & 1 \\ -1 & -1 & 1 & 1 & -1 & -1 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{array}\right)$.







A has only only one eigenvalue 1 with algebraic multiplicity 6. In particular $r=6$.







Thus $E_1(1)$ has dimesnion 3. That is, we have $r_1=3$. $E_1(1)$ has a basis

$$\{(1, 0, 0, 1, 0, 0),(0, 1, 0, 0, -1, 0),(0, 0, 1, 0, 0, 0)\}=\{s_1,t_1,u_1\}$$

 



Thus $E_2(1)$ has dimesnion 5. That is we have $r_2=5$. $E_2(1)$ has a basis

$$\{(1, ,0, 0, 0, 0, 0),(0, 1, 0, 0, 0, 0),(0, 0, 1, 0, 0, 0),(0, 0, 0, 1, 0, 0),(0, 0, 0, 0, 1, 0)\}$$




Thus $E_3(1)$ has dimesnion 6 which is equal to the multiplicity of 1. That is, we have $r_2=6=r$. $E_3(1)$ has

$\{e_1,e_2,e_3,e_4,e_5,e_6\}$ as a basis.




We choose $v_3 \in E_3(1)$ which is not in $E_2(1)$. This suggests that we can define

$v_3=(0, 0, 0, 0, 0,1)$, and then $v_2=(A-I)v_3$.




Now we must choose $w_2$ in $E_2(1)$ so that $\{v_2,w_2, s_1, t_1, u_1\}$ is linearly independent.




We must choose x1 to be a vector in $E_1(1)$ such that ${v_1,w_1, x_1}$ is linearly independent.










Let us find that the JCF of $A$ with the built-in Sage function.




Introduction  to JCF: 

  • http://matrix.skku.ac.kr/JCF/index.htm
  • Command for finding JCF:

  • http://matrix.skku.ac.kr/JCF/JordanCanonicalForm-SKKU.html
  • Matrix Calculator 2:

  • http://matrix.skku.ac.kr/2014-Album/MC-2.html
  •  

     

    Jordan Canonical Form an algorithmic approach

    Ajit Kumar at ICT, Mumbai

    Sang-Gu Lee at SKKU, Korea

           

    Back to the Index Page