REDUCE

20.37 NORMFORM: Computation of
Matrix Normal Forms

This package contains routines for computing the following normal forms of matrices:

Author: Matt Rebbeck.

20.37.1 Introduction

\( \newcommand {\rank }{\mathop {\mathrm {rank}}} \newcommand {\f }[1]{\texttt {#1}} \)When are two given matrices similar? Similar matrices have the same trace, determinant, characteristic polynomial, and eigenvalues, but the matrices \[ \mathcal {U} = \begin {pmatrix} 0 & 1 \\ 0 & 0 \end {pmatrix} \quad \text { and } \quad \mathcal {V} = \begin {pmatrix} 0 & 0 \\ 0 & 0 \end {pmatrix} \] are the same in all four of the above but are not similar. Otherwise there could exist a nonsingular \(\mathcal { N} {\in } M_{2}\) (the set of all \(2 \times 2\) matrices) such that \(\mathcal {U} = \mathcal {N} \mathcal {V} \mathcal {N}^{-1} = \mathcal {N} \, \mathit {0} \, \mathcal {N}^{-1} = \mathit {0}\), which is a contradiction since \(\mathcal {U} \neq \mathit {0}\).

Two matrices can look very different but still be similar. One approach to determining whether two given matrices are similar is to compute the normal form of them. If both matrices reduce to the same normal form they must be similar.

NORMFORM is a package for computing the following normal forms of matrices:

By default all calculations are carried out in \(\mathbf {Q}\) (the rational numbers). For smithex, frobenius, ratjordan, jordansymbolic, and jordan, this field can be extended. Details are given in the respective sections.

The frobenius, ratjordan, and jordansymbolic normal forms can also be computed in a modular base. Again, details are given in the respective sections.

The algorithms for each routine are contained in the source code.

NORMFORM has been converted from the normform and Normform packages written by T. M. L. Mulders and A. H. M. Levelt. These have been implemented in Maple [CGG\(^{+}\)91].

20.37.2 Smith normal form

Function


smithex(\(\mathcal {A},\, x\)) computes the Smith normal form \(\mathcal { S}\) of the matrix \(\mathcal { A}\).

It returns {\(\mathcal { S}, \mathcal { P}, \mathcal { P}^{-1}\)} where \(\mathcal { S}, \mathcal { P}\), and \(\mathcal { P}^{-1}\) are such that \(\mathcal { P S P}^{-1} = \mathcal { A}\).

\(\mathcal { A}\) is a rectangular matrix of univariate polynomials in \(x\).

\(x\) is the variable name.

Field extensions


Calculations are performed in \(\mathbf {Q}\). To extend this field the ARNUM package can be used. For details see subsection 20.37.8.

Synopsis:

     

Example:

      \[ \mathcal {A} = \begin {pmatrix} x & x+1 \\ 0 & 3*x^2 \end {pmatrix} \] \[ \mathtt {smithex}(\mathcal {A}, x) = \left \{ \begin {pmatrix} 1 & 0 \\ 0 & x^3 \end {pmatrix}, \begin {pmatrix} 1 & 0 \\ 3*x^2 & 1 \end {pmatrix}, \begin {pmatrix} x & x+1 \\ -3 & -3 \end {pmatrix} \right \} \]

20.37.3 smithex_int

Function


Given an \(n\) by \(m\) rectangular matrix \(\mathcal {A}\) that contains only integer entries, smithex_int(\(\mathcal {A}\)) computes the Smith normal form \(\mathcal {S}\) of \(\mathcal {A}\).

It returns \(\{\mathcal {S}, \mathcal {P}, \mathcal { P}^{-1}\}\) where \(\mathcal {S}\), \(\mathcal {P}\), and \(\mathcal { P}^{-1}\) are such that \(\mathcal {P S P}^{-1} = \mathcal {A}\).

Synopsis

     

Example

      \[ \mathcal {A} = \begin {pmatrix} 9 & -36 & 30 \\ -36 & 192 & -180 \\ 30 & -180 & 180 \end {pmatrix} \] \begin {multline*} \text {\texttt {smithex\_int}}(\mathcal {A}) = \\ \left \{ \begin {pmatrix} 3 & 0 & 0 \\ 0 & 12 & 0 \\ 0 & 0 & 60 \end {pmatrix}, \begin {pmatrix} -17 & -5 & -4 \\ 64 & 19 & 15 \\ -50 & -15 & -12 \end {pmatrix}, \begin {pmatrix} 1 & -24 & 30 \\ -1 & 25 & -30 \\ 0 & -1 & 1 \end {pmatrix} \right \} \end {multline*}

20.37.4 frobenius

Function


\(\mathtt {frobenius}(\mathcal {A})\) computes the Frobenius normal form \(\mathcal {F}\) of the matrix \(\mathcal {A}\).

It returns \(\{\mathcal {F}, \mathcal {P}, \mathcal {P}^{-1}\}\) where \(\mathcal {F}\), \(\mathcal {P}\), and \(\mathcal {P}^{-1}\) are such that \(\mathcal {P F P}^{-1} = \mathcal {A}\).

\(\mathcal {A}\) is a square matrix.

Field extensions


Calculations are performed in \(\mathbf {Q}\). To extend this field the ARNUM package can be used. For details see subsection 20.37.8

Modular arithmetic


frobenius can be calculated in a modular base. For details see subsection 20.37.9.

Synopsis

     

Example

      \[ \mathcal {A} = \begin {pmatrix} \frac {-x^2+y^2+y}{y} & \frac {-x^2+x+y^2-y}{y} \\[1mm] \frac {-x^2-x+y^2+y}{y} & \frac {-x^2+x+y^2-y} {y} \end {pmatrix} \] \( \f {frobenius}(\mathcal {A}) = \) \[ \left \{ \begin {pmatrix} 0 & \frac {x*(x^2-x-y^2+y)}{y} \\[1mm] 1 & \frac {-2*x^2+x+2*y^2}{y} \end {pmatrix}, \begin {pmatrix} 1 & \frac {-x^2+y^2+y}{y} \\[1mm] 0 & \frac {-x^2-x+y^2+y}{y} \end {pmatrix}, \begin {pmatrix} 1 & \frac {-x^2+y^2+y}{x^2+x-y^2-y} \\[1mm] 0 & \frac {-y}{x^2+x-y^2-y} \end {pmatrix} \right \} \]

20.37.5 ratjordan

Function


ratjordan(\(\mathcal {A}\)) computes the rational Jordan normal form \(\mathcal {R}\) of the matrix \(\mathcal {A}\).

It returns \(\{\mathcal {R}, \mathcal {P}, \mathcal {P}^{-1}\}\) where \(\mathcal {R}\), \(\mathcal {P}\), and \(\mathcal {P}^{-1}\) are such that \(\mathcal {P R P}^{-1} = \mathcal {A}\).

\(\mathcal {A}\) is a square matrix.

Field extensions


Calculations are performed in \(\mathbf {Q}\). To extend this field the ARNUM package can be used. For details see subsection 20.37.8.

Modular arithmetic


ratjordan can be calculated in a modular base. For details see subsection 20.37.9.

Synopsis

     

Example

      \[ \mathcal {A} = \begin {pmatrix} x+y & 5 \\ y & x^2 \end {pmatrix} \] \( \f {ratjordan}(\mathcal {A}) = \) \[ \left \{ \begin {pmatrix} 0 & -x^3-x^2*y+5*y \\[1mm] 1 & x^2+x+y \end {pmatrix}, \begin {pmatrix} 1 & x+y \\[1mm] 0 & y \end {pmatrix}, \begin {pmatrix} 1 & \frac {-(x+y)}{y} \\[1mm] 0 & \frac {1}{y} \end {pmatrix} \right \} \]

20.37.6 jordansymbolic

Function


jordansymbolic\((\mathcal {A})\) computes the Jordan normal form \(\mathcal {J}\) of the matrix \(\mathcal {A}\).

It returns \(\{\mathcal {J}, \mathcal {L}, \mathcal {P}, \mathcal {P}^{-1}\}\), where \(\mathcal {J}\), \(\mathcal {P}\), and \(\mathcal {P}^{-1}\) are such that \(\mathcal {P J P}^ {-1} = \mathcal {A}\). \(\mathcal {L} = \{ ll , \xi \}\), where \(\xi \) is a name and \(ll\) is a list of irreducible factors of \(p(\xi )\).

\(\mathcal {A}\) is a square matrix.

Field extensions


Calculations are performed in \(\mathbf {Q}\). To extend this field the ARNUM package can be used. For details see subsection 20.37.8.

Modular arithmetic


jordansymbolic can be calculated in a modular base. For details see subsection 20.37.9.

Synopsis

     

Example

      \[ \mathcal {A} = \begin {pmatrix} 1 & y \\ y^2 & 3 \end {pmatrix} \] \( \f {jordansymbolic}(\mathcal {A}) = \) \[ \left \{ \begin {pmatrix} \xi _{11} & 0 \\ 0 & \xi _{12} \end {pmatrix} , \left \{ \left \{ -y^3+\xi ^2-4*\xi +3 \right \}, \xi \right \}, \right . \] \[ \hspace {0.1in} \left . \begin {pmatrix} \xi _{11} -3 & \xi _{12} -3 \\[1mm] y^2 & y^2 \end {pmatrix}, \begin {pmatrix} \frac {\xi _{11} -2} {2*(y^3-1)} & \frac {\xi _{11} + y^3 -1}{2*y^2*(y^3+1)} \\[1mm] \frac {\xi _{12} -2}{2*(y^3-1)} & \frac {\xi _{12}+y^3-1}{2*y^2*(y^3+1)} \end {pmatrix} \right \} \] solve(-y^3+xi^2-4*xi+3,xi);\[ \{ \xi = \sqrt {y^3+1} + 2,\, \xi = -\sqrt {y^3+1}+2 \} \\ \]J = sub({xi(1,1)=sqrt(y^3+1)+2,
         xi(1,2)=-sqrt(y^3+1)+2},
        first jordansymbolic (A))\[ \mathcal {J} = \begin {pmatrix} \sqrt {y^3+1} + 2 & 0 \\ 0 & -\sqrt {y^3+1} + 2 \end {pmatrix} \]

20.37.7 jordan

Function


jordan(\(\mathcal {A}\)) computes the Jordan normal form \(\mathcal {J}\) of the matrix \(\mathcal {A}\).

It returns \(\{\mathcal {J}, \mathcal {P}, \mathcal {P}^{-1}\}\), where \(\mathcal {J}\), \(\mathcal {P}\), and \(\mathcal {P}^{-1}\) are such that \(\mathcal {P J P}^ {-1} = \mathcal {A}\).

\(\mathcal {A}\) is a square matrix.

Field extensions


Calculations are performed in \(\mathbf {Q}\). To extend this field the ARNUM package can be used. For details see subsection 20.37.8.

Note


In certain polynomial cases the switch fullroots is turned on to compute the zeroes. This can lead to the calculation taking a long time, as well as the output being very large. In this case a message
*****
WARNING: fullroots turned on. May take a while.
will be printed. It may be better to kill the calculation and compute jordansymbolic instead.

Synopsis

     

Example

      \[ \mathcal {A} = \begin {pmatrix} -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 {pmatrix} \] J = first jordan(A);\[ \mathcal {J} = \begin {pmatrix} 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 {pmatrix} \]

20.37.8 Algebraic extensions: Using the ARNUM package

The algebraic field \(\mathbf {Q}\) can now be extended. E.g., defpoly sqrt2**2-2; will extend it to include \(\sqrt {2}\) (defined here by sqrt2). The ARNUM package was written by Eberhard Schrüfer and is described in section 9.12.5.

20.37.8.1 Example

defpoly sqrt2**2-2;
(sqrt2 now changed to \(\sqrt {2}\) for looks!) \[ \mathcal {A} = \begin {pmatrix} 4*{\sqrt {2}}-6 & -4*{\sqrt {2}}+7 & -3*{\sqrt {2}}+6 \\ 3*{\sqrt {2}}-6 & -3*{\sqrt {2}}+7 & -3*{\sqrt {2}}+6 \\ 3*{\sqrt {2}} & 1-3*{\sqrt {2}} & -2*{\sqrt {2}} \end {pmatrix} \] \( \displaystyle \f {ratjordan}(\mathcal {A}) = \left \{ \begin {pmatrix} {\sqrt {2}} & 0 & 0 \\ 0 & {\sqrt {2}} & 0 \\ 0 & 0 & -3*{\sqrt {2}}+1 \end {pmatrix}, \right . \) \[ \hspace {0.1in} \left . \begin {pmatrix} 7*{\sqrt {2}}-6 & \frac {2*{\sqrt {2}}-49}{31} & \frac {-21*{\sqrt {2}}+18}{31} \\[1mm] 3*{\sqrt {2}}-6 & \frac {21*{\sqrt {2}}-18}{31} & \frac {-21*{\sqrt {2}}+18}{31} \\[1mm] 3*{\sqrt {2}}+1 & \frac {-3*{\sqrt {2}}+24}{31} & \frac {3*{\sqrt {2}}-24}{31} \end {pmatrix}, \right . \] \[ \hspace {0.1in} \left . \begin {pmatrix} 0 & {\sqrt {2}}+1 & 1 \\ -1 & 4*{\sqrt {2}}+9 & 4*{\sqrt {2}} \\ -1 & -\frac {1}{6}*{\sqrt {2}} +1 & 1 \end {pmatrix} \right \} \]

20.37.9 Modular arithmetic

Calculations can be performed in a modular base by setting the switch modular to on. The base can then be set by setmod p; (p a prime). The normal form will then have entries in \(\mathbf {Z}/\)p\(\mathbf {Z}\).

By also switching on balanced_mod the output will be shown using a symmetric modular representation.

Information on this modular manipulation can be found in section 9.12.3.

20.37.9.1 Example

on modular;
setmod 23;\[ \mathcal {A} = \begin {pmatrix} 10 & 18 \\ 17 & 20 \end {pmatrix} \]\( \f {jordansymbolic}(\mathcal {A}) = \)\[ \left \{ \begin {pmatrix} 18 & 0 \\ 0 & 12 \end {pmatrix}, \left \{ \left \{ \lambda + 5, \lambda + 11 \right \}, \lambda \right \}, \begin {pmatrix} 15 & 9 \\ 22 & 1 \end {pmatrix}, \begin {pmatrix} 1 & 14 \\ 1 & 15 \end {pmatrix} \right \} \]on balanced_mod;

\( \f {jordansymbolic}(\mathcal {A}) = \) \[ \left \{ \begin {pmatrix} -5 & 0 \\ 0 & -11 \end {pmatrix}, \left \{ \left \{ \lambda + 5, \lambda + 11 \right \}, \lambda \right \}, \begin {pmatrix} -8 & 9 \\ -1 & 1 \end {pmatrix}, \begin {pmatrix} 1 & -9 \\ 1 & -8 \end {pmatrix} \right \} \]


Hosted by Download REDUCE Powered by MathJax