\chapter[NORMFORM: matrix normal forms]%
{NORMFORM: Computation of matrix normal forms}
\label{NORMFORM}
\typeout{{NORMFORM: Computation of matrix normal forms}}
{\footnotesize
\begin{center}
Matt Rebbeck \\
Konrad--Zuse--Zentrum f\"ur Informationstechnik Berlin \\
Takustra\"se 7 \\
D--14195 Berlin--Dahlem, Germany \\[0.05in]
\end{center}
}
\ttindex{NORMFORM}
This package contains routines for computing the following
normal forms of matrices:
\begin{itemize}
\item smithex\_int
\item smithex
\item frobenius
\item ratjordan
\item jordansymbolic
\item jordan.
\end{itemize}
By default all calculations are carried out in ${\cal Q}$ (the rational
numbers). For {\tt smithex}, {\tt frobenius}, {\tt ratjordan},
{\tt jordansymbolic}, and {\tt jordan}, this field can be extended to
an algebraic number field using ARNUM (chapter~\ref{ARNUM}).
The {\tt frobenius}, {\tt ratjordan}, and {\tt jordansymbolic} normal
forms can also be computed in a modular base.
\section{Smithex}
\ttindex{smithex}
{\tt Smithex}(${\cal A},\, x$) computes the Smith normal form ${\cal S}$
of the matrix ${\cal A}$.
It returns \{${\cal S}, {\cal P}, {\cal P}^{-1}$\} where ${\cal S},
{\cal P}$, and ${\cal P}^{-1}$ are such that
${\cal P S P}^{-1} = {\cal A}$.
${\cal A}$ is a rectangular matrix of univariate polynomials in $x$
where $x$ is the variable name.
{\tt load\_package normform;}
\begin{displaymath}
{\cal A} = \left( \begin{array}{cc} x & x+1 \\ 0 & 3*x^2 \end{array}
\right)
\end{displaymath}
\begin{displaymath}
\hspace{-0.5in}
\begin{array}{ccc}
{\tt smithex}({\cal A},\, x) & = &
\left\{ \left( \begin{array}{cc} 1 & 0 \\
0 & x^3 \end{array} \right), \left( \begin{array}{cc} 1 & 0 \\ 3*x^2
& 1 \end{array} \right), \left( \begin{array}{cc} x & x+1 \\ -3 & -3
\end{array} \right) \right\} \end{array}
\end{displaymath}
\section{Smithex\_int}
\ttindex{smithex\_int}
Given an $n$ by $m$ rectangular matrix ${\cal A}$ that contains
{\it only} integer entries, {\tt smithex\_int}(${\cal A}$) computes the
Smith normal form ${\cal S}$ of ${\cal A}$.
It returns \{${\cal S}, {\cal P}, {\cal P}^{-1}$\} where ${\cal S},
{\cal P}$, and ${\cal P}^{-1}$ are such that ${\cal P S P}^{-1} =
{\cal A}$.
{\tt load\_package normform;}
\begin{displaymath}
{\cal A} = \left( \begin{array}{ccc} 9 & -36 & 30 \\ -36 & 192 & -180 \\
30 & -180 & 180 \end{array}
\right)
\end{displaymath}
{\tt smithex\_int}(${\cal A}$) =
\begin{center}
\begin{displaymath}
\left\{ \left( \begin{array}{ccc} 3 & 0 & 0 \\ 0 & 12 & 0 \\ 0 & 0 & 60
\end{array} \right), \left( \begin{array}{ccc} -17 & -5 & -4 \\ 64 & 19
& 15 \\ -50 & -15 & -12 \end{array} \right), \left( \begin{array}{ccc}
1 & -24 & 30 \\ -1 & 25 & -30 \\ 0 & -1 & 1 \end{array} \right) \right\}
\end{displaymath}
\end{center}
\section{Frobenius}
\ttindex{frobenius}
{\tt Frobenius}(${\cal A}$) computes the Frobenius normal form
${\cal F}$ of the matrix ${\cal A}$.
It returns \{${\cal F}, {\cal P}, {\cal P}^{-1}$\} where ${\cal F},
{\cal P}$, and ${\cal P}^{-1}$ are such that ${\cal P F P}^{-1} =
{\cal A}$.
${\cal A}$ is a square matrix.
{\tt load\_package normform;}
\begin{displaymath}
{\cal A} = \left( \begin{array}{cc} \frac{-x^2+y^2+y}{y} &
\frac{-x^2+x+y^2-y}{y} \\ \frac{-x^2-x+y^2+y}{y} & \frac{-x^2+x+y^2-y}
{y} \end{array} \right)
\end{displaymath}
{\tt frobenius}(${\cal A}$) =
\begin{center}
\begin{displaymath}
\left\{ \left( \begin{array}{cc} 0 & \frac{x*(x^2-x-y^2+y)}{y} \\ 1 &
\frac{-2*x^2+x+2*y^2}{y} \end{array} \right), \left( \begin{array}{cc}
1 & \frac{-x^2+y^2+y}{y} \\ 0 & \frac{-x^2-x+y^2+y}{y} \end{array}
\right), \left( \begin{array}{cc} 1 & \frac{-x^2+y^2+y}{x^2+x-y^2-y} \\
0 & \frac{-y}{x^2+x-y^2-y} \end{array} \right) \right\}
\end{displaymath}
\end{center}
\section{Ratjordan}
\ttindex{ratjordan}
{\tt Ratjordan}(${\cal A}$) computes the rational Jordan normal form
${\cal R}$ of the matrix ${\cal A}$.
It returns \{${\cal R}, {\cal P}, {\cal P}^{-1}$\} where ${\cal R},
{\cal P}$, and ${\cal P}^{-1}$ are such that ${\cal P R P}^{-1} =
{\cal A}$.
${\cal A}$ is a square matrix.
{\tt load\_package normform;}
\begin{displaymath}
{\cal A} = \left( \begin{array}{cc} x+y & 5 \\ y & x^2 \end{array}
\right)
\end{displaymath}
{\tt ratjordan}(${\cal A}$) =
\begin{center}
\begin{displaymath}
\left\{ \left( \begin{array}{cc} 0 & -x^3-x^2*y+5*y \\ 1 &
x^2+x+y \end{array} \right), \left( \begin{array}{cc}
1 & x+y \\ 0 & y \end{array} \right), \left( \begin{array}{cc} 1 &
\frac{-(x+y)}{y} \\ 0 & \hspace{0.2in} \frac{1}{y} \end{array} \right)
\right\}
\end{displaymath}
\end{center}
\section{Jordansymbolic}
\ttindex{jordansymbolic}
{\tt Jordansymbolic}(${\cal A}$) \hspace{0in} computes the Jordan
normal form ${\cal J}$of the matrix ${\cal A}$.
It returns \{${\cal J}, {\cal L}, {\cal P}, {\cal P}^{-1}$\}, where
${\cal J}, {\cal P}$, and ${\cal P}^{-1}$ are such that ${\cal P J P}^
{-1} = {\cal A}$. ${\cal L}$ = \{~{\it ll},~$\xi$~\}, where $\xi$ is
a name and {\it ll} is a list of irreducible factors of ${\it p}(\xi)$.
${\cal A}$ is a square matrix.
{\tt load\_package normform;}\\
\begin{displaymath}
{\cal A} = \left( \begin{array}{cc} 1 & y \\ y^2 & 3 \end{array}
\right)
\end{displaymath}
{\tt jordansymbolic}(${\cal A}$) =
\begin{eqnarray}
& & \left\{ \left( \begin{array}{cc} \xi_{11} & 0 \\ 0 & \xi_{12}
\end{array} \right) ,
\left\{ \left\{ -y^3+\xi^2-4*\xi+3 \right\}, \xi \right\}, \right.
\nonumber \\ & & \hspace{0.1in} \left. \left( \begin{array}{cc}
\xi_{11} -3 & \xi_{12} -3 \\ y^2 & y^2
\end{array} \right), \left( \begin{array}{cc} \frac{\xi_{11} -2}
{2*(y^3-1)} & \frac{\xi_{11} + y^3 -1}{2*y^2*(y^3+1)} \\
\frac{\xi_{12} -2}{2*(y^3-1)} & \frac{\xi_{12}+y^3-1}{2*y^2*(y^3+1)}
\end{array} \right) \right\} \nonumber
\end{eqnarray}
\vspace{0.2in}
\begin{flushleft}
\begin{math}
{\tt solve(-y^3+xi^2-4*xi+3,xi)}${\tt ;}$
\end{math}
\end{flushleft}
\vspace{0.1in}
\begin{center}
\begin{math}
\{ \xi = \sqrt{y^3+1} + 2,\, \xi = -\sqrt{y^3+1}+2 \}
\end{math}
\end{center}
\vspace{0.1in}
\begin{math}
{\tt {\cal J} = sub}{\tt (}{\tt \{ xi(1,1)=sqrt(y^3+1)+2,\, xi(1,2) =
-sqrt(y^3+1)+2\},}
\end{math}
\\ \hspace*{0.29in} {\tt first jordansymbolic (${\cal A}$));}
\vspace{0.2in}
\begin{displaymath}
{\cal J} = \left( \begin{array}{cc} \sqrt{y^3+1} + 2 & 0 \\ 0 &
-\sqrt{y^3+1} + 2 \end{array} \right)
\end{displaymath}
\section{Jordan}
\ttindex{jordan}
{\tt Jordan}(${\cal A}$) computes the Jordan normal form
${\cal J}$ of the matrix ${\cal A}$.
It returns \{${\cal J}, {\cal P}, {\cal P}^{-1}$\}, where
${\cal J}, {\cal P}$, and ${\cal P}^{-1}$ are such that ${\cal P J P}^
{-1} = {\cal A}$.
${\cal A}$ is a square matrix.
{\tt load\_package normform;}
\begin{displaymath}
{\cal A} = \left( \begin{array}{cccccc} -9 & -21 & -15 & 4 & 2 & 0 \\
-10 & 21 & -14 & 4 & 2 & 0 \\ -8 & 16 & -11 & 4 & 2 & 0 \\ -6 & 12 & -9
& 3 & 3 & 0 \\ -4 & 8 & -6 & 0 & 5 & 0 \\ -2 & 4 & -3 & 0 & 1 & 3
\end{array} \right)
\end{displaymath}
\begin{flushleft}
{\tt ${\cal J}$ = first jordan$({\cal A})$;}
\end{flushleft}
\begin{displaymath}
{\cal J} = \left( \begin{array}{cccccc} 3 & 0 & 0 & 0 & 0 & 0 \\ 0 & 3
& 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & i+2 & 0 \\ 0 & 0 & 0 & 0 & 0 & -i+2
\end{array} \right)
\end{displaymath}