REDUCE

16.40 NORMFORM: Computation of matrix normal forms

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

Author: Matt Rebbeck.

16.40.1 Introduction

When are two given matrices similar? Similar matrices have the same trace, determinant, characteristic polynomial, and eigenvalues, but the matrices

     ( 0  1 )            ( 0  0 )
U =    0  0    and  V =    0  0

are the same in all four of the above but are not similar. Otherwise there could exist a nonsingular NM2 (the set of all 2 × 2 matrices) such that U = NVN1 = N0N1 = 0, which is a contradiction since U0.

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:

 - smithex  
 - smithex_int  
 - frobenius  
 - ratjordan  
 - jordansymbolic  
 - jordan

The package is loaded by load_package normform;

By default all calculations are carried out in 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 [4].

16.40.2 smithex

16.40.2.1 function

smithex(A,x) computes the Smith normal form S of the matrix A.

It returns {S,P,P1} where S,P, and P1 are such that PSP1 = A.

A is a rectangular matrix of univariate polynomials in x.

x is the variable name.

16.40.2.2 field extensions

Calculations are performed in Q. To extend this field the ARNUM package can be used. For details see section 8.

16.40.2.3 synopsis

16.40.2.4 example

load_package normform;

     (          )
A =    x  x + 1
       0  3 ∗x2

                  { ( 1   0 )  (    1    0 ) (   x  x + 1 ) }
smithex(A, x)  =          3   ,       2     ,
                      0  x        3∗ x   1      − 3  − 3

16.40.3 smithex_int

16.40.3.1 function

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

It returns {S,P,P1} where S,P, and P1 are such that PSP1 = A.

16.40.3.2 synopsis

16.40.3.3 example

load_package normform;

     (                    )
         9    − 36   30
A  = (  − 36  192   − 180 )
        30   − 180   180

smithex_int(A) =

( (  3   0   0 )  (  − 17  − 5   − 4 )  (   1  − 24   30  ))
{ (            )  (                  )  (                 )}
(    0  12   0   ,    64   19    15    ,   − 1  25   − 30  )
     0   0  60       − 50  − 15 − 12        0   − 1   1

16.40.4 frobenius

16.40.4.1 function

frobenius(A) computes the Frobenius normal form F of the matrix A.

It returns {F,P,P1} where F,P, and P1 are such that PFP1 = A.

A is a square matrix.

16.40.4.2 field extensions

Calculations are performed in Q. To extend this field the ARNUM package can be used. For details see section 8.

16.40.4.3 modular arithmetic

frobenius can be calculated in a modular base. For details see section 9.

16.40.4.4 synopsis

16.40.4.5 example

load_package normform;

     (   −x2+y2+y   −-x2+x+y2−-y )
A  =      2 y  2      2  y  2
        −x-−xy+y-+y- −-x+x+yy-−-y

frobenius(A) =

{(     x∗(x2−x−y2+y) )  (      −x2+y2+y  )  (     −-x2+y2+y- ) }
    0      2 y    2   ,   1    2 y  2     ,   1  x2+x−y2−y
    1  −-2∗x-+xy+2∗y-       0  −x-−xy+y-+y-      0  x2+−xy−y2−y

16.40.5 ratjordan

16.40.5.1 function

ratjordan(A) computes the rational Jordan normal form R of the matrix A.

It returns {R,P,P1} where R,P, and P1 are such that PRP1 = A.

A is a square matrix.

16.40.5.2 field extensions

Calculations are performed in Q. To extend this field the ARNUM package can be used. For details see section 8.

16.40.5.3 modular arithmetic

ratjordan can be calculated in a modular base. For details see section 9.

16.40.5.4 synopsis

16.40.5.5 example

load_package normform;

    (  x+ y   5 )
A =            2
         y   x

ratjordan(A) =

{ (                        ) (           ) (     − (x+y) ) }
     0  − x3 − x2 ∗ y + 5∗ y ,  1  x + y   ,  1  ---y--
     1      x2 + x+ y           0    y        0      1y

16.40.6 jordansymbolic

16.40.6.1 function

jordansymbolic(A) computes the Jordan normal form J of the matrix A.

It returns {J,L,P,P1}, where J,P, and P1 are such that PJP1 = A. L = { ll , ξ }, where ξ is a name and ll is a list of irreducible factors of p(ξ).

A is a square matrix.

16.40.6.2 field extensions

Calculations are performed in Q. To extend this field the ARNUM package can be used. For details see section 8.

16.40.6.3 modular arithmetic

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

16.40.6.4 extras

If using xr, the X interface for REDUCE, the appearance of the output can be improved by switching on looking_good;. This converts all lambda to ξ and improves the indexing, eg: lambda12 ξ12. The example (section 6.6) shows the output when this switch is on.

16.40.6.5 synopsis

16.40.6.6 example

load_package normform;
on looking_good;

    (  1   y )
A =    y2  3

jordansymbolic(A) =

{ ( ξ11  0  )  {{   3    2          }  }
     0   ξ    ,  − y  + ξ − 4 ∗ξ + 3 ,ξ  ,
          12           (                3    ) }
  ( ξ11 − 3 ξ12 − 3 )    2ξ∗1(y1−3−21)  2ξ∗11y2+∗y(y−3+11)-
      y2      y2     ,   -ξ12−-2-  -ξ12+y3−1--
                         2∗(y3−1)  2∗y2∗(y3+1)

solve(y3 + xi2 4 xi + 3,xi);

{ξ = ∘y3--+-1 + 2,ξ = ∘y3-+-1- + 2}

J = sub({xi(1,1) = sqrt(y3 + 1) + 2,xi(1,2) = sqrt(y3 + 1) + 2},
  first jordansymbolic (A));

     ( ∘ ------                   )
J =      y3 + 1+ 2    ∘ --0---
            0       −   y3 + 1+ 2

For a similar example ot this in standard REDUCE (ie: not using xr), see the normform.log file.

16.40.7 jordan

16.40.7.1 function

jordan(A) computes the Jordan normal form J of the matrix A.

It returns {J,P,P1}, where J,P, and P1 are such that PJP1 = A.

A is a square matrix.

16.40.7.2 field extensions

Calculations are performed in Q. To extend this field the ARNUM package can be used. For details see section 8.

16.40.7.3 note

In certain polynomial cases 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.

16.40.7.4 synopsis

16.40.7.5 example

load_package normform;

    (   − 9  − 21 − 15  4  2  0 )
    |  − 10   21  − 14  4  2  0 |
    ||                           ||
A = ||   − 8   16  − 11  4  2  0 ||
    |   − 6   12   − 9  3  3  0 |
    (   − 4   8    − 6  0  5  0 )
        − 2   4    − 3  0  1  3

J = first jordan(A);

    (                           )
       3  0  0  0    0      0
    ||  0  3  0  0    0      0   ||
J = ||  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

16.40.8 arnum

The package is loaded by load_package arnum;. The algebraic field Q can now be extended. For example, defpoly sqrt2**2-2; will extend it to include √ --
  2 (defined here by sqrt2). The ARNUM package was written by Eberhard Schrüfer and is described in the arnum.tex file.

16.40.8.1 example

load_package normform;
load_package arnum;
defpoly sqrt2**2-2;
(sqrt2 now changed to √2-- for looks!)

     (  4∗ √2-− 6  − 4 ∗√2-+ 7  − 3 ∗√2-+ 6 )
     (     √--         √ --         √ --    )
A  =    3∗  2√ −-6  − 3 ∗ 2√+-7  − 3 ∗ 2√ +-6
         3 ∗  2     1− 3 ∗  2     − 2 ∗ 2

                  ( (  √ --                 )
                  {      2 √0--      0
ratjordan(A )  =    (   0    2       0√ --   ) ,
                  (     0   0   − 3∗   2+ 1
                    (     √--       √ -         √-    )
                       7∗ √2-− 6   2∗3√2−1-49  −-21∗3√21+18
                    |(  3∗  2 − 6  21∗-2−18  −-21∗-2+18 |) ,
                          √--     −3∗3√12+24   3∗√321−24
                    (  3∗  2 +√1-    31        )31)
                       0       2√ +-1       1√ --  }
                    (  − 1  4 ∗  2+ 9   4 ∗  2 )
                       − 1 − 1∗ √2-+ 1     1     )
                             6

16.40.9 modular

Calculations can be performed in a modular base by switching on modular;. The base can then be set by setmod p; (p a prime). The normal form will then have entries in ZpZ.

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 chapter 9 (Polynomials and Rationals) of the REDUCE User’s Manual [5].

16.40.9.1 example

load_package normform;
on modular;
setmod 23;

     (        )
       10  18
A =    17  20

jordansymbolic(A) =

{(  18  0  )                     (  15  9 ) (  1  14 )}
    0   12   ,{{λ+ 5,λ + 11} ,λ},   22  1   ,  1  15

on balanced_mod;

jordansymbolic(A) =

{ (          )                      (        )  (        )}
    − 5   0                           − 8  9      1  − 9
     0   − 11  ,{{λ + 5,λ + 11},λ} ,  − 1  1   ,  1  − 8

Bibliography

[1]   T.M.L.Mulders and A.H.M. Levelt: The Maple normform and Normform packages. (1993)

[2]   T.M.L.Mulders: Algoritmen in De Algebra, A Seminar on Algebraic Algorithms, Nigmegen. (1993)

[3]   Roger A. Horn and Charles A. Johnson: Matrix Analysis. Cambridge University Press (1990)

[4]   Bruce W. Chat…[et al.]: Maple (Computer Program). Springer-Verlag (1991)

[5]   Anthony C. Hearn: REDUCE User’s Manual 3.6. RAND (1995)