Up | Next | Prev | PrevTail | Tail |
This package contains routines for computing the following normal forms of matrices:
smithex_int
smithex
frobenius
ratjordan
jordansymbolic
jordan.
\( \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
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
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].
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.
Calculations are performed in \(\mathbf {Q}\). To extend this field the ARNUM package can
be used. For details see subsection 20.40.8.
The Smith normal form \(\mathcal {S}\) of an n by m matrix \(\mathcal {A}\) with univariate polynomial entries in \(x\) over a field \(\mathbf {F}\) is computed. That is, the polynomials are then regarded as elements of the Euclidean domain \(\mathbf {F}(x)\).
The Smith normal form is a diagonal matrix \(\mathcal {S}\) where:
\(\rank (\mathcal {A})\) = number of nonzero rows (columns) of \(\mathcal {S}\).
\(\mathcal {S}(i,i)\) is a monic polynomial for \(0 < i \leq \rank (\mathcal {A})\).
\(\mathcal {S}(i,i)\) divides \(\mathcal {S}(i+1,i+1)\) for \(0 < i < \rank (\mathcal {A})\).
\(\mathcal { S}(i,i)\) is the greatest common divisor of all \(i\) by \(i\) minors of \(\mathcal {A}\).
Hence, if we have the case that \(n = m\), as well as \(\rank (\mathcal {A}) = n\), then
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 \(\mathcal {S}\), this is not an efficient method for computing these quantities except that this may yield a partial factorization of \(\det (\mathcal {A})\) without doing any explicit factorizations.
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}\).
The Smith normal form \(\mathcal { S}\) of an \(n\) by \(m\) matrix \(\mathcal { A}\) with integer entries is computed.
The Smith normal form is a diagonal matrix \(\mathcal { S}\) where:
\(\rank (\mathcal {A})\) = number of nonzero rows (columns) of \(\mathcal {S}\).
\(\mathop {\mathrm {sign}}(\mathcal {S}(i,i)) = 1\) for \(0 < i \leq \rank (\mathcal {A})\).
\(\mathcal {S}(i,i)\) divides \(\mathcal {S}(i+1,i+1)\) for \(0< i < \rank (\mathcal {A})\).
\(\mathcal {S}(i,i)\) is the greatest common divisor of all \(i\) by \(i\) minors of \(\mathcal {A}\).
Hence, if we have the case that \(n = m\), as well as rank(\(\mathcal {A}\)) \(= n\), then
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.
\(\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.
Calculations are performed in \(\mathbf {Q}\). To extend this field the ARNUM package can
be used. For details see subsection 20.40.8
frobenius
can be calculated in a modular base. For details see subsection
20.40.9.
\(\mathcal {F}\) has the following structure:
The Frobenius normal form defined in this way is unique (ie: if we require that \(p_{i}\) divides \(p_{i+1}\) as above).
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.
Calculations are performed in \(\mathbf {Q}\). To extend this field the ARNUM package can
be used. For details see subsection 20.40.8.
ratjordan
can be calculated in a modular base. For details see subsection
20.40.9.
\(\mathcal {R}\) has the following structure:
The \(r_{ij}\)’s have the following shape:
where there are e\(ij\) times \(\mathcal {C}(p)\) blocks along the diagonal and \(\mathcal {C}(p)\) is the companion matrix associated with the irreducible polynomial \(p\). All unmarked entries are zero.
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.
Calculations are performed in \(\mathbf {Q}\). To extend this field the ARNUM package can
be used. For details see subsection 20.40.8.
jordansymbolic can be calculated in a modular base. For details see
subsection 20.40.9.
A Jordan block \({\jmath }_{k}(\lambda )\) is a \(k\) by \(k\) upper triangular matrix of the form:
A Jordan matrix \(\mathcal {J} \in M_{n}\) (the set of all \(n\) by \(n\) matrices) is a direct sum of jordan blocks
Here \(\lambda \) is a zero of the characteristic polynomial \(p\) of \(\mathcal {A}\). 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
\(\{ \mathcal {J,L,P,P}^{-1} \}\). \(\mathcal {J}\) is the Jordan normal form of \(\mathcal {A}\) (using symbolic names if necessary).
\(\mathcal {L} = \{ \mathit {ll}, \xi \}\), where \(\xi \) is a name and \(\mathit {ll}\) is a list of irreducible factors of \(p(\xi )\). If symbolic
names are used then \({\xi }_{ij}\) is a zero of \(ll_{i}\). \(\mathcal {P}\) and \(\mathcal {P}^{-1}\) are as above.
solve(-y^3+xi^2-4*xi+3,xi);
J = sub({xi(1,1)=sqrt(y^3+1)+2,
xi(1,2)=-sqrt(y^3+1)+2},
first jordansymbolic (A))
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.
Calculations are performed in \(\mathbf {Q}\). To extend this field the ARNUM package can
be used. For details see subsection 20.40.8.
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.
The Jordan normal form \(\mathcal {J}\) with entries in an algebraic extension of \(\mathbf {Q}\) is computed.
A Jordan block \({\jmath }_{k}(\lambda )\) is a \(k\) by \(k\) upper triangular matrix of the form:
A Jordan matrix \(\mathcal {J} \in M_{n}\) (the set of all \(n\) by \(n\) matrices) is a direct sum of jordan blocks.
Here \(\lambda \) is a zero of the characteristic polynomial \(p\) of \(\mathcal {A}\). The zeroes of the characteristic polynomial are computed exactly, if possible. Otherwise they are approximated by floating point numbers.
J = first
jordan(A);
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.
defpoly sqrt2**2-2;
(sqrt2 now changed to \(\sqrt {2}\) for looks!)
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.
on modular;
setmod 23;
on balanced_mod;
\( \f {jordansymbolic}(\mathcal {A}) = \)
Up | Next | Prev | PrevTail | Front |