NORMFORM: Computation of Matrix Normal Forms

REDUCE

20.37 NORMFORM: Computation of Matrix Normal Forms

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

smithex_int
smithex
frobenius
ratjordan
jordansymbolic
jordan.

Author: Matt Rebbeck.

20.37.1 Introduction

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

( ) ( ) 𝒰 = 0 1 and 𝒱 = 0 0 0 0 0 0

are the same in all four of the above but are not similar. Otherwise there could exist a nonsingular 𝒩∈M₂ (the set of all 2 × 2 matrices) such that 𝒰 = 𝒩𝒱𝒩⁻¹ = 𝒩0𝒩⁻¹ = 0 , which is a contradiction since 𝒰≠0 .

Two matrices can look very diﬀerent 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

By default all calculations are carried out in Q (the rational numbers). For smithex, frobenius, ratjordan, jordansymbolic, and jordan, this ﬁeld 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(𝒜,x) computes the Smith normal form 𝒮 of the matrix 𝒜.

It returns {𝒮,𝒫,𝒫⁻¹} where 𝒮,𝒫, and 𝒫⁻¹ are such that 𝒫𝒮𝒫⁻¹ = 𝒜.

𝒜 is a rectangular matrix of univariate polynomials in x.

x is the variable name.

Field extensions

Calculations are performed in Q. To extend this ﬁeld the ARNUM package can be used. For details see subsection 20.37.8.

Synopsis:

The Smith normal form 𝒮 of an n by m matrix 𝒜 with univariate polynomial entries in x over a ﬁeld F is computed. That is, the polynomials are then regarded as elements of the Euclidean domain F(x).
The Smith normal form is a diagonal matrix 𝒮 where:
- rank(𝒜) = number of nonzero rows (columns) of 𝒮.
- 𝒮(i,i) is a monic polynomial for 0 < i ≤ rank(𝒜).
- 𝒮(i,i) divides 𝒮(i + 1,i + 1) for 0 < i < rank(𝒜).
- 𝒮(i,i) is the greatest common divisor of all i by i minors of 𝒜.
Hence, if we have the case that n = m, as well as rank(𝒜) = n, then
$∏n det(𝒜) 𝒮 (i,i) = lcoeﬀ-(det(𝒜-),x). i=1$
The Smith normal form is obtained by doing elementary row and column operations. This includes interchanging rows (columns), multiplying through a row (column) by −1, and adding integral multiples of one row (column) to another.
Although the rank and determinant can be easily obtained from 𝒮, this is not an eﬃcient method for computing these quantities except that this may yield a partial factorization of det(𝒜) without doing any explicit factorizations.

Example:

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

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

20.37.3 smithex_int

Function

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

It returns {𝒮,𝒫,𝒫⁻¹} where 𝒮, 𝒫, and 𝒫⁻¹ are such that 𝒫𝒮𝒫⁻¹ = 𝒜.

Synopsis

The Smith normal form 𝒮 of an n by m matrix 𝒜 with integer entries is computed.
The Smith normal form is a diagonal matrix 𝒮 where:
- rank(𝒜) = number of nonzero rows (columns) of 𝒮.
- sign(𝒮(i,i)) = 1 for 0 < i ≤ rank(𝒜).
- 𝒮(i,i) divides 𝒮(i + 1,i + 1) for 0 < i < rank(𝒜).
- 𝒮(i,i) is the greatest common divisor of all i by i minors of 𝒜.
Hence, if we have the case that n = m, as well as rank(𝒜) = n, then
$∏n |det(𝒜)| = 𝒮 (i,i). i=1$
The Smith normal form is obtained by doing elementary row and column operations. This includes interchanging rows (columns), multiplying through a row (column) by −1, and adding integral multiples of one row (column) to another.

Example

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

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

20.37.4 frobenius

Function

frobenius(𝒜) computes the Frobenius normal form ℱ of the matrix 𝒜.

It returns {ℱ,𝒫,𝒫⁻¹} where ℱ, 𝒫, and 𝒫⁻¹ are such that 𝒫ℱ𝒫⁻¹ = 𝒜.

𝒜 is a square matrix.

Field extensions

Calculations are performed in Q. To extend this ﬁeld 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

ℱ has the following structure: $( ) 𝒞p1 | 𝒞p2 | ℱ = || . || ( .. ) 𝒞pk$
where the 𝒞(p_i)’s are companion matrices associated with polynomials p₁,p₂,…,p_k, with the property that p_i divides p_i+1 for i = 1…k−1. All unmarked entries are zero.
The Frobenius normal form deﬁned in this way is unique (ie: if we require that p_i divides p_i+1 as above).

Example

( ) −-x2+y2+y −x2+x+y2−y- 𝒜 = −x2−xy+y2+y −x2+yx+y2−y -----y----- ----y------

$frobenius (𝒜 ) =$

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

20.37.5 ratjordan

Function

ratjordan(𝒜) computes the rational Jordan normal form ℛ of the matrix 𝒜.

It returns {ℛ,𝒫,𝒫⁻¹} where ℛ, 𝒫, and 𝒫⁻¹ are such that 𝒫ℛ𝒫⁻¹ = 𝒜.

𝒜 is a square matrix.

Field extensions

Calculations are performed in Q. To extend this ﬁeld 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

ℛ has the following structure: $( ) | r11 | | r12 | || ... || ℛ = || r || || 21 || ( r22 ) ...$

The r_ij’s have the following shape:
$( 𝒞(p) ℐ ) | 𝒞 (p) ℐ | || . . || rij = || .. .. || ( 𝒞 (p ) ℐ ) 𝒞(p)$

where there are eij times 𝒞(p) blocks along the diagonal and 𝒞(p) is the companion matrix associated with the irreducible polynomial p. All unmarked entries are zero.

Example

( ) 𝒜 = x + y 5 y x2

$ratjordan (𝒜 ) =$

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

20.37.6 jordansymbolic

Function

jordansymbolic(𝒜) computes the Jordan normal form 𝒥 of the matrix 𝒜.

It returns {𝒥,ℒ,𝒫,𝒫⁻¹}, where 𝒥 , 𝒫, and 𝒫⁻¹ are such that 𝒫𝒥𝒫⁻¹ = 𝒜. ℒ = {ll,ξ}, where ξ is a name and ll is a list of irreducible factors of p(ξ).

𝒜 is a square matrix.

Field extensions

Calculations are performed in Q. To extend this ﬁeld 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

A Jordan block ȷ_k(λ) is a k by k upper triangular matrix of the form: $( λ 1 ) | λ 1 | || . . || ȷk(λ) = || .. .. || ( λ 1) λ$
There are k − 1 terms “+1” in the superdiagonal; the scalar λ appears k times on the main diagonal. All other matrix entries are zero, and ȷ₁(λ) = (λ).
A Jordan matrix 𝒥 ∈ M_n (the set of all n by n matrices) is a direct sum of jordan blocks $( ) ȷn1(λ1) || ȷn2(λ2) || 𝒥 = | .. | ,n1 + n2 + ⋅⋅⋅+ nk = n ( . ) ȷnk(λk)$
in which the orders n_i may not be distinct and the values λ_i need not be distinct.
Here λ is a zero of the characteristic polynomial p of 𝒜. If p does not split completely, symbolic names are chosen for the missing zeroes of p. If, by some means, one knows such missing zeroes, they can be substituted for the symbolic names. For this, jordansymbolic actually returns {𝒥,ℒ,𝒫,𝒫⁻¹}. 𝒥 is the Jordan normal form of 𝒜 (using symbolic names if necessary). ℒ = {ll,ξ}, where ξ is a name and ll is a list of irreducible factors of p(ξ). If symbolic names are used then ξ_ij is a zero of ll_i. 𝒫 and 𝒫⁻¹ are as above.

Example

( ) 𝒜 = 12 y y 3

$jordansymbolic (𝒜 ) =$

{ ( ) ξ11 0 { { 3 2 } } 0 ξ12 , − y + ξ − 4 ∗ξ + 3 ,ξ ,

( ) ( -ξ11−2-- -ξ11+y3−1-) } ξ11 − 3 ξ12 − 3 , 2∗(y3−1) 2∗y2∗(y3+1) y2 y2 -ξ12−32-- -ξ122+y33−1-- 2∗(y −1) 2∗y ∗(y +1)

solve(-y^3+xi^2-4*xi+3,xi);

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

J = sub({xi(1,1)=sqrt(y^3+1)+2, xi(1,2)=-sqrt(y^3+1)+2}, first jordansymbolic (A))

( ) ∘y3-+-1-+ 2 0 𝒥 = ∘ --3--- 0 − y + 1+ 2

20.37.7 jordan

Function

jordan(𝒜) computes the Jordan normal form 𝒥 of the matrix 𝒜.

It returns {𝒥,𝒫,𝒫⁻¹}, where 𝒥 , 𝒫, and 𝒫⁻¹ are such that 𝒫𝒥𝒫⁻¹ = 𝒜.

𝒜 is a square matrix.

Field extensions

Calculations are performed in Q. To extend this ﬁeld 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

The Jordan normal form 𝒥 with entries in an algebraic extension of Q is computed.
A Jordan block ȷ_k(λ) is a k by k upper triangular matrix of the form: $( ) λ 1 || λ 1 || ȷk(λ) = || ... ... || |( λ 1|) λ$
There are k − 1 terms “+1” in the superdiagonal; the scalar λ appears k times on the main diagonal. All other matrix entries are zero, and ȷ₁(λ) = (λ).
A Jordan matrix 𝒥 ∈ M_n (the set of all n by n matrices) is a direct sum of jordan blocks. $( ) ȷn1(λ1) | ȷn2(λ2) | 𝒥 = || . || ,n1 + n2 + ⋅⋅⋅+ nk = n ( .. ) ȷnk(λk)$
in which the orders n_i may not be distinct and the values λ_i need not be distinct.
Here λ is a zero of the characteristic polynomial p of 𝒜. The zeroes of the characteristic polynomial are computed exactly, if possible. Otherwise they are approximated by ﬂoating point numbers.

Example

( ) − 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

J = first jordan(A);

( ) 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

20.37.8 Algebraic extensions: Using the ARNUM package

The algebraic ﬁeld Q can now be extended. For example, defpoly sqrt2**2-2; will extend it to include √ --
2 (deﬁned 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 --
√ 2 for looks!)

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

$( ( √ -- ) { 2 √0-- 0 ratjordan (𝒜 ) = ( 0 2 0 -- ) , ( 0 0 − 3∗ √ 2+ 1$

( √-- 2∗√2−49 −21∗√2+18) | 7∗ √2-− 6 3√1 3√1- | |( 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∗1 2√-+ 9 4∗ 2 ) − 1 − 6 ∗ 2 + 1 1

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 Z∕pZ.

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;

( ) 𝒜 = 10 18 17 20

$jordansymbolic (𝒜 ) =$

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

on balanced_mod;

$jordansymbolic (𝒜) =$

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

PrevTail

Front