# Thursday November 21

## Cyclic Decomposition

Let $\phi: V\to V$ be a linear transformation; then $V$ is a $k[x]$ module under $f(x) \actson v \definedas f(\phi)(v)$.

By the structure theorem, since $k[x]$ is a PID, we have an invariant factor decomposition $V = \bigoplus V_i$ where each $V_i$ is a cyclic $k[x]\dash$module.
If $q_i$ is the minimal polynomial for $\phi_i: V_i \to V_i$, then $q_{i} \divides q_{i+1}$ for all $i$.

We also have an elementary divisor decomposition where $p_i^{m_i}$ are the minimal polynomials for $\phi_i$.

> Note: one is only for the restriction to the subspaces? Check.

Recall that if $\phi$ has minimal polynomial $q(x)$.
Then if $\dim V = n$, there exists a basis of $B$ if $V$ such that $[\phi]_B$ is given by the **companion matrix** of $q(x)$.
This is the **rational canonical form**.

**Corollary:**
Let $\phi: V\to V$ be a linear transformation.
Then $V$ is a cyclic $k[x]\dash$module and $\phi$ has minimal polynomial $(x-b)^n \iff \dim V = n$ and there exists a basis such that

\begin{align*}
[\phi]_B = \left[\begin{array}{ccccccc}
b & 1 & 0   & \cdots  & 0       & 0 & 0\\
0 & b & 1   & \cdots  & 0       & 0 & 0\\
0 & 0 & b   & 1       &\cdots   & 0 & 0\\
0 & 0 & 0   & 0       & \cdots  & b & 1
\end{array}\right]
.\end{align*}

This is the **Jordan Canonical form**.

> Note that if $k$ is not algebraically closed, we can only reduce to RCF. If $k$ *is* closed, we can reduce to JCF, which is slightly nicer.

*Proof:*

Let $\delta = \phi - b \cdot\id_V$. Then

- $q(x)$ is the minimal polynomial for $\phi \iff x^n$ is the minimal polynomial for $\delta$.

- A priori, $V$ has two $k[x]$ structures -- one given by $\phi$, and one by $\delta$.

- *Exercise*: $V$ is cyclic with respect to the $\phi$ structure $\iff$ $V$ is cyclic with respect to the the $\delta$ structure.


Then the matrix $[\delta]_B$ relative to an ordered basis for $\delta$ is with only zeros on the diagonal and 1s on the super-diagonal, and $[\phi]_B$ is the same but with $b$ on the diagonal.

$\qed$

**Lemma:**
Let $\phi: V\to V$ with $V = \bigoplus_i^t V_i$ as $k[x]\dash$modules.
Then $M_i$ is a matrix of $\restrictionof{\phi}{V_i}: V_i \to V_i$ relative to some basis for $V_i \iff$the matrix of $\phi$ wrt some ordered basis is given by

\begin{align*}
\left[
\begin{array}{cccc}
M_1 &  & & \\
& M_2 & & \\
& & \ddots & \\
& & & M_t
\end{array}\right]
.\end{align*}


*Proof*:

$\implies$:
Suppose $B_i$ is a basis for $V_i$ and $[\phi]_{B_i} = M_i$. Then let $B = \union_i B_i$; then $B$ is a basis for $V$ and the matrix is of the desired form.

$\impliedby$:
Suppose that we have a basis $B$ and $[\phi]_B$ is given by a block diagonal matrix filled with blocks $M_i$.
Suppose $\dim M_i = n_i$.
If $B = \theset{v_1, v_2, \cdots, v_n}$, then take $B_1 = \theset{v_1, \cdots, v_{n_1}}$ and so on.
Then $[\phi_i]_{B_i} = M_i$ as desired.

$\qed$

*Application:*
Let $V = \bigoplus V_i$ with $q_i$ the minimal polynomials of $\phi: V_i \to V_i$ with $q_i \divides q_{i+1}$.

Then there exists a basis where $[\phi]_B$ is block diagonal with blocks $M_i$, where each $M_i$ is in rational canonical form with minimal polynomial $q_i(x)$.
If $k$ is algebraically closed, we can obtain elementary divisors $p_i(x) = (x - b_i)^{m_i}$.
Then there exists a similar basis where now each $M_i$ is a *Jordan block* with $b_i$ on the diagonals and ones on the super-diagonal.

Moreover, in each case, there is a basis such that $A = P [M_i] P\inv$ (where $M_i$ are the block matrices obtained).
When $A$ is diagonalizable, $P$ contains the eigenvectors of $A$.

**Corollary:**
Two matrices are similar $\iff$ they have the same invariant factors and elementary divisors.

*Example:*
Let $\phi: V\to V$ have invariant factors $q_1(x) = (x-1)$ and $q_2(x) = (x-1)(x-2)$.

Then $\dim V = 3$, $V = V_1 \oplus V_2$ where $\dim V_1 = 1$ and $\dim V_2 = 2$.
We thus have

\begin{align*}
[\phi]_B =
\left(\begin{array}{ccc}
1 & 0 & 0 \\
0 & 0 & 1 \\
0 & -2 & 3
\end{array}\right)
.\end{align*}

Moreover, we have

\begin{align*}
V
\cong \frac{k[x]}{(x-1)} \oplus \frac{k[x]}{(x-1)(x-2)}
\cong \frac{k[x]}{(x-1)} \oplus \frac{k[x]}{(x-1)} \oplus \frac{k[x]}{(x-2)}
,\end{align*}


so the elementary divisors are $x-1, x-1, x-2$.

> Invariant factor decompositions should correspond to rational canonical form blocks, and elementary divisors should correspond to Jordan blocks.

**Theorem:**
Let $A$ be an $n\times n$ matrix over $k$.
Then the matrix $xI_n - A \in M_n(k[x])$ is equivalent in $k[x]$ to a diagonal matrix $D$ with non-zero entries $f_1, f_2, \cdots f_t \in k[x]$ such that the $f_i$ are monic and $f_i \divides f_{i+1}$.
The non-constant polynomials among the $f_i$ are the invariant factors of $A$.

*Proof (Sketch)*:
Let $V = k^n$ and $\phi: k^n \to k^n$ correspond to $A$ under the fixed standard basis $\theset{e_i}$.
Then $V$ has a $k[x]\dash$module structure induced by $\phi$.

Let $F$ be the free $k[x]$ module with basis $\theset{u_i}_{i=1}^n$, and define the maps

\begin{align*}
\pi: F &\to k^n \\
u_i &\mapsto e_i
\end{align*}

and

\begin{align*}
\psi: F &\to F \\
u_i &\mapsto xu_i - \sum_j a_{ij} u_j
.\end{align*}

Then $\psi$ relative to the basis $\theset{u_i}$ is $xI_n - A$.

Then *(exercise)* the sequence
$$
F \mapsvia{\psi} F \mapsvia{\pi} k^n \to 0
$$
is exact, $\im \pi = k^n$, and $\im \psi = \ker \pi$.

We then have $k^n \cong F/\ker \pi = F / \im \psi$, and since $k[x]$ is a PID,

\begin{align*}
xI_n - A \sim D \definedas
\left[\begin{array}{cc}
L_r & 0 \\
0 & 0
\end{array}\right]
.\end{align*}


where $L_r$ is diagonal with $f_i$s where $f_i \divides f_{i+1}$.

However, $\det(xI_n - A) \neq 0$ because  $x I_n - A$ is a monic polynomial of degree $n$.

But $\det{xI_n - A} = \det(D)$, so this means that $L_r$ must take up the entire matrix of $D$, so there is no zero in the bottom-right corner.
So $L_r = D$, and $D$ is the matrix of $\psi$ with respect to $B_1 = \theset{v_i}$ and $B_2 = \theset{w_i}$ with $\psi(v_i) = f_i w_i$.

Thus
$$
\im \psi = \bigoplus_{i=1}^n k[x] f_i w_i.
$$

But then
\begin{align*}
V = k^n \cong F/ \im \psi
&\cong \frac{k[x] w_1 \oplus \cdots \oplus k[x] w_n} {k[x] f_1 w_1 \oplus \cdots \oplus k[x] f_n w_n} \\
&\cong \bigoplus_{i=1}^n k[x]/(f_i)
.\end{align*}

$\qed$