\documentclass[12pt,chris]{article}
%\pagestyle{linedtop}
\setlength{\oddsidemargin}{0pt}
\setlength{\marginparsep}{11pt}
\setlength{\marginparwidth}{72pt}
\setlength{\textwidth}{433pt}
\input{header}
\usepackage{amssymb}
\begin{document}
\include{readme-1}
\pagenumbering{arabic}
\section{A brief description of {\tt cmat}}
{\tt cmat} is an exact arithmetic calculator program, written in C and designed to run on computers which support UNIX, or 386/486 PC's. {\tt cmat} performs many of the standard arithmetical operations that can be carried out exactly, without approximations, on matrices and polynomials whose coefficients are either rational numbers, complex rational numbers, or elements of $\BZ_p$, the finite field of $p$ elements, where $p$ is a prime less than $2^{16}=65536$.
\medskip
There are three calculator programs within {\tt cmat} and these can be accessed directly:
\begin{center}
{\tt cmatr}, {\tt cmatcr} and {\tt cmatm}\ (UNIX).
\end{center}
\begin{center}
{\tt cmatr.exe}, {\tt cmatcr.exe} and {\tt cmatm.exe}\ (MSDOS).
\end{center}
{\tt cmatr} works over the field {\BQ} of rational numbers, {\tt cmatcr} over the field $\BQ(i)$ of complex rational numbers -- numbers of the form $a+ib$, where $a$ and $b$ are rationals, while {\tt cmatm} works over $\BZ_p$.
\medskip
The programs use multiple precision arithmetic routines based on those in
\cite[pages 342--357, 175--185]{Flanders}.
\medskip
The program allows for the creation and storage of up to
$M0$ objects of the following type ($M0$ is usually set to 30).
\be
\item
rational numbers: $R[0],\ldots,R[M0-1]$;
\item
matrices with rational coefficients: $RM[0],\ldots,RM[M0-1]$;
\item
polynomials with rational coefficients: $P\!R[0],\ldots,P\!R[M0-1]$;
\item
matrices with polynomial rational coefficients:
$P\!RM[0],\ldots,P\!RM[M0-1]$;
\item
complex rational numbers: $C\!R[0],\ldots,C\!R[M0-1]$;
\item
matrices with complex rational coefficients:
$C\!RM[0],\ldots,C\!RM[M0-1]$;
\item
polynomials with complex rational coefficients:
$PC\!R[0],\ldots,PC\!R[M0-1]$;
\item
matrices with polynomial complex rational coefficients:
$PC\!RM[0],\ldots,PC\!RM[M0-1]$;
\item
matrices with mod $p$ coefficients: $mM[0],\ldots,mM[M0-1]$;
\item
polynomials with mod $p$ coefficients: $Pm[0],\ldots,Pm[M0-1]$;
\item
matrices with polynomial mod $p$ coefficients:
$PmM[0],\ldots,PmM[M0-1]$;
\ee
These arrays always contain the appropriate zero object until replaced by either an object entered by the user, or one resulting from a calculation.
\medskip
Storage limitations and execution times of algorithms are much less when
calculating with matrices over $\BZ_p$.
\section{Routines available}
\begin{itemize}
\item
The familiar arithmetical operations of addition, subtraction, multiplication,
inverse, ratio and exponentiation, are available for rationals, complex
rationals and elements of $\BZ_p$. Complex conjugation of complex
numbers is also available. The m--th root of a rational number can be computed
to a given number of decimal places.
\item
For polynomials, there are the usual operations of addition, subtraction,
multiplication, scalar multiplication, exponentiation, derivative, evaluation,
quotient, remainder, greatest common divisor, expressing the greatest common
divisor as a linear combination of the polynomials involved.
The resultant of two polynomials over $\BZ[x]$ and the discriminant of a
polynomial over $\BZ[x]$ can be calculated.
\item
There is modular exponentiation for polynomials in $\BZ_p[x]\PMOD{P[j]}$.
The squarefree decomposition of a polynomial can be found. Polynomials over
$\BQ, \BQ(i)$ or $\BZ_p$ can be factorized into irreducibles.
The Berlekamp matrix of a squarefree polynomial $f\in\BZ_p[x]$ is
available.
This is the transpose of the usual Berlekamp matrix that is described in
\cite[pages 420--429]{Knuth} and is the $n\times n$ matrix $Q=[q_{ij}]$ over
$\BZ_p$ defined by the congruence
\[
x^{pj}\equiv \sum_{i=0}^{n-1}q_{ij}x^i\PMOD{f},\ 0\leq j\leq n-1,
\]
where $n=\deg{f}$.
An irreducible polynomial of given degree over $\BZ_p[x]$ can be constructed.
The cyclotomic polynomial $\Phi_n(x)$ can be calculated over $\BZ[x]$ and
$\BZ_p[x]$.
\item
For matrices, there are the usual operations of addition, subtraction,
multiplication, scalar multiplication, exponentiation, Kronecker product,
direct sum of two matrices, evaluation of a matrix polynomial.
\item
The standard elementary row and column operations can be performed on all types
of matrices.
\item
The entries of a stored matrix can be changed, either individually, or by row
or column. A single row or column can be deleted.
\item
A single row or column vector can be selected from a stored matrix.
More generally, a submatrix of a stored matrix can be formed by selecting a
subfamily of rows or columns, respectively.
\item
Two matrices can be joined by rows or columns. The partitioned matrix $[A|I]$
can be formed from $A$. A matrix can be unwrapped into a column vector
(a process useful for finding the minimum polynomial of a matrix).
\item
The matrix $A-\lambda I$ can be formed from $A$ and $\lambda$; this is important
when finding a basis for the eigenspace of $A$ corresponding to the eigenvalue
$\lambda$.
\item
Special matrices such as band matrices, the identity matrix, the elementary
Jordan matrix and the companion matrix of a polynomial, can be created.
\item
Files of matrices (rational, floating point, complex rational or mod p),
prepared by the user, can be read into the {\tt cmat} program. The floating
point numbers can only be used in the rational program and are converted
internally to rational numbers in lowest terms.
\item
Matrices whose $(i,\,j)$th element has real and imaginary parts given by simple arithmetical expressions such as
${\tt i}\string ^2+3$*{\tt j} for the numerators and denominators, may be
created wholly within {\tt cmat}.
\item
The inverse, adjoint, determinant, characteristic polynomial and minimum
polynomial of a matrix of scalars can be found. The adjoint and determinant
can also be found for matrices with polynomial elements. Also $P^{-1}AP$
can be calculated.
and minimum polynomial of a matrix of scalars, $P^{-1}AP$. The Cholesky decomposition of a positive definite matrix is found: $A=L^tDL$, where $L$ is upper unit triangular and $D$ is a diagonal matrix. The output has the diagonal elements of $D$ on its diagonal and its above diagonal elements are those of $L$.
The inverse of a matrix $M$ of integers mod m can be found, when m is
a positive integer relatively prime to $\det{M}$.
\item
The reduced row--echelon form of a matrix can be found. Also systems
of linear equations can be solved.
\item
Bases can be found for the null--space $N(A)$ and column--space $C(A)$ of a
matrix $A$.
Both bases are associated with the reduced row--echelon form $B$ of the given
matrix $A$: if the non--zero rows of $B$ have leading entries $1$ in columns
$c_1,\ldots,c_r$, then $X$ in $N(A)$ is found by expressing the unknowns
$x_{c_1},\ldots,x_{c_r}$ in terms of the remaining unknowns
$x_{c_{r+1}},\ldots,x_{c_n}$, which are taken to be arbitrary. This
results in expressing $X$ as a linear combination
\[
X=x_{c_{r+1}}X_1+\cdots x_{c_n}X_{n-r}
\]
and $X_1,\ldots,X_{n-r}$ form the basis for $N(A)$ that is selected by
{\tt cmat}.
The column vectors of $A$ in columns $c_1,\ldots,c_r$ form a basis for $C(A)$
that is selected by {\tt cmat}. This basis is known as the {\em left--to--right
basis} for the column--space.
%The nomenclature is chosen because proceeding from left to right along the columns of $A$, we find
%\be
%\item[(i)] $A_{c_1}$ is the first non--zero column of $A$;
%\item[(ii)] for $1<k\leq r,\,A_{c_k}$ is the first column after $A_{c_{k-1}}$
% which is not a linear combination of $A_{c_1},\ldots,A_{c_{k-1}}$;
%\item[(iii)] finally all subsequent columns after $A_{c_r}$ are linear
% combinations of $A_{c_1},\ldots,A_{c_r}$.
%\ee
The left--to--right basis is especially useful for extending a given linearly
independent family of column vectors $X_1,\ldots,X_s$ in a vector space $V$, to
a basis for $V$, where a spanning family $Y_1,\ldots,Y_t$ is given. For
\[
V=\langle X_1,\ldots,X_s,\,Y_1,\ldots,Y_t\rangle
\]
and applying the left--to--right algorithm to the spanning family will
select $X_1,\ldots,X_s$, together with a subfamily of $Y_1,\ldots,Y_t$ as a
basis for $V$. This procedure is very useful in one of the algorithms for
finding the Jordan canonical form or more generally, the rational canonical
form of a square matrix. (See\cite{Matthews2}.)
\item
The dot product and length of vectors with rational or complex rational entries
can be calculated. The Gram--Schmidt process is also available.
The cross--product of two vectors with rational components can be found. There
is also a generalisation to the cross--product of the rows of an $(n-1)\times
n$ matrix of rationals.
\item
The Smith canonical form of a matrix $B$ with polynomial elements can be found.
When applied to the matrix $B=xI-A$, where $A$ is a matrix of scalars, this
gives the similarity invariants of $A$; in particular, we obtain the minimum
polynomial of $A$ as the invariant of highest degree.
Polynomial matrices $P$ and $Q$, whose determinants are constant polynomials,
are also found such that $P\!BQ$ is in Smith canonical form.
\item
All data currently stored in the above arrays can be printed either on the
screen or on a line printer. If desired, matrices of rational and complex
rational coefficients can be printed to a file or the screen, to a nominated
number of decimal places.
\end{itemize}
\section{Calculating with {\tt cmat}}
\begin{itemize}
\item The user can successively descend deeper into the program by selecting
various displayed screen options. To ascend through the various levels, type
{\tt q} when this is an option.
When leaving the program, the user is given the option of saving data for
re--use in future sessions.
\item
The menus are somewhat tersely organized and are listed at the end of this
guide. The menus are interpreted as follows:
To enter a rational number and store the number as $RM[0]$ say, one selects the appropriate menu (number R14 at the end of this guide) and types {\tt n 0}.
{\bf NOTE: Use CONTROL-H, not the backspace key, to backspace over characters.}
\item
Integers are entered as usual, while non--integer rationals are entered with a
slash as integer/positive integer: e.g. {\tt -71/2}, while complex numbers
with non--zero imaginary part must end with an $i$: e.g. {\tt 1/2i} represents
$(1/2)i$. No brackets are to be used when entering numbers. Rational numbers are
outputted in 'lowest terms', with positive denominator.
\item
Some latitude is allowed as regards spacing. For example,
{\tt 1-i, 1- i, 1 - i} represent the same complex rational. However
{\tt 1 -i} represents the two numbers {\tt 1} and {\tt -i}.
\item
Matrices are entered row by row, the end of a row being marked by a carriage
return. Spaces separate entries of a row.
\item
To discontinue entering a polynomial or matrix from the keyboard, type {\tt q}
or any non--alphanumeric character when entering a coefficient. A default
polynomial or matrix is then stored.
\item
To perform calculations with stored data, one has to select the appropriate
menu. For example, having entered matrices $RM[0]$ and $RM[1]$, the product
$RM[0] * RM[1]$ is sent to $RM[2]$ (or $RM[0]$ or $RM[1]$) by selecting the
multiplication option {\tt t} from menu R7, reproduced below, typing
{\tt t 0 1 2} :
\medskip\centering
\begin{tabular}{|cccccccc|}\hline
\multicolumn{7}{|c}{\tt Rational Matrix Arithmetic} &{\tt R7}\\\hline
{\tt a}&{\tt j}&{\tt k}&{\tt l}&{\tt :}&{\tt RM[j] + RM[k]}&{\tt ->} &
{\tt RM[l]}\\
{\tt t}&{\tt j}&{\tt k}&{\tt l}&{\tt :}&{\tt RM[j] * RM[k]}&{\tt ->} &
{\tt RM[l]}\\
{\tt s}&{\tt j}&{\tt k}&{\tt l}&{\tt :}&{\tt RM[j] - RM[k]}&{\tt ->} &
{\tt RM[l]}\\
{\tt m}&{\tt j}&{\tt k}& &{\tt :}& {\tt -RM[j]} &{\tt ->} &
{\tt RM[k]}\\
{\tt f}&{\tt j}&{\tt k}&{\tt l}&{\tt :}& {\tt R[j](RM[k])} &{\tt ->} &
{\tt RM[l]}\\
{\tt *}&{\tt j}&{\tt k}& &{\tt :}& {\tt (RM[j])*} &{\tt ->} &
{\tt RM[k]}\\
{\tt e}&{\tt n}&{\tt j}&{\tt k}&{\tt :}&{\tt RM[j]\string ^n} &{\tt ->} &
{\tt RM[k]}\\
{\tt z}&{\tt j}&{\tt k}&{\tt l}&{\tt :}&{\tt RM[j] - R[k]I}&{\tt ->} &
{\tt RM[l]}\\
{\tt p}& & & &{\tt :}&{\tt print numbers and matrices}& &\\
{\tt x}& & & &{\tt :}&{\tt to enter data}& &\\
{\tt q}& & & &{\tt :}&{\tt to exit}& &\\\hline
\end{tabular}
\end{itemize}
\begin{itemize}
\item
To calculate the $10$th power of $RM[0]$, select the exponentiation option
{\tt e} from the above menu, typing {\tt e 10 0 3} to send the output to
$RM[3]$.
\item
The situation is somewhat simpler with modular arithmetic calculations. Here
no numbers are stored and non--negative numbers less than the relevant
modulus are entered directly, instead of being stored. For example to multiply
the matrix $mM[0]$ by $5\PMOD 7$ and to store the result as $mM[1]$, select
menu $m7$ below and type
\begin{center}
{\tt f 5 0 1 7}.
\end{center}
\item
It is important to remember that when using the modular
arithmetic section of {\tt cmat}, operations should be carried out only on
stored objects having the same modulus.
\item
To terminate input prematurely after entering the first letter of a menu option,
type {\tt q} followed by {\bf RETURN}.
\item
To input a file of $r\,(<=M0-j)$ prepared matrices of the same type (rational,
floating point, complex rational or modular) into array positions
$j,\ldots,j+r-1$ , the first line of the file should contain the number $r$;
the next line consists of the row and column number of the first matrix,
followed by the respective rows of the matrix.
For example, the following file represents two rational matrices, the first
being $3\times 3$, the second being $2\times 2$:
\end{itemize}
\begin{verbatim}
/* rational matrix file */
2
3 3
2/3 5 -7/8
1/2 12 -5
7 6 4
2 2
1 0
0 1
\end{verbatim}
\section{Comments on algorithms used in {\tt cmat}}
\begin{itemize}
\item The tricks of P. Henrici mentioned in \cite[pages 200--201]{Buchberger}
are used to speed up addition and multiplication of rationals.
\item
The Gauss--Jordan method is used to find the reduced
row--echelon form and to solve system of linear equations over all three fields.
\item The adjoint, inverse, determinant and characteristic polynomial of a
matrix of rationals or complex rationals are found by the
Faddeeva--Leverrier method. See the book \cite[pages 177--181]{Faddeeva}.
The method is also valid for matrices over $\BZ_p$ or $\BZ_p[x]$ if $p>n$, the size of the matrix.
In fact, for matrices over $\BZ_p$, we use instead a modification of an algorithm due to Frobenius (see \cite[pages 168--175]{McWorter}) to find the characteristic polynomial. Also over $\BZ_p$, the Gauss--Jordan algorithm is used to find the inverse and determinant of a matrix. The adjoint is found using the fact that adj\,$A=0$ if rank\,$A\leq n-2$, rank\,(adj\,$A)=1$ if rank\,$A=n-1$ and adj\,$A=(\det{A})\cdot A^{-1}$ otherwise.
\item
The inverse of an integer matrix mod m is found by using the adjoint matrix
and multiplying mod m by the inverse of determinant mod m.
\item The minimum polynomial of an $n\times n$ matrix $A$ is found by finding
the least $m\geq 1$ such that $A^m$ is expressible as a linear
combination of $I_n,\ldots,A^{m-1}$. This is done by unwrapping the matrices
$I_n,\ldots,A_r$ into column vectors for $1\leq r\leq m$ and solving the
equation
\[
x_0I+\cdots+x_{r-1}A^{r-1}=A^r
\]
as a system of $n^2$ equations in $r$ unknowns. The system will be inconsistent
for $1\leq r< m$, but will have a unique solution when $r=m$, giving the
minimum polynomial $m_A=x^m-x_{m-1}x^{m-1}-\cdots-x_0$.
\item The Smith canonical form is found by the algorithm in \cite[pages 111--113]{Hartley}. Faster algorithms exist (see \cite{Luneburg}).
\item
Factorization of polynomials in $\BZ_p[x]$ is accomplished using a
method of finding a non--trivial factor due to P. Camion (see \cite{Camion}).
This is used in conjunction with the Berlekamp matrix of a polynomial. For
information on this matrix see \cite[pages 420--429]{Knuth}. (Our
Berlekamp matrix is the transpose of Knuth's.)
\item
Factorization of a polynomial in $\BZ[x]$ is accomplished using an
algorithm outlined in \cite{Musser}. The algorithm uses the degree--set testing procedure which sometimes uncovers irreducibility before more complicated tests
are employed.
The Hensel--Zassenhaus quadratic and linear liftings are used to obtain a
factorization of $f(x)$ modulo a high power of a prime.
The degree--set test also has the effect of reducing the number of test
divisions needed to determine possible factors over $\BZ[x]$ after the
liftings are completed.
\item
Factorization of a polynomial in $\BQ(i)[x]$ is accomplished using an
algorithm outlined in \cite{Trager}.
\item A squarefree decomposition algorithm for polynomials due to D.Y.Y. Yun
and described in \cite[pages 631--632]{Knuth} is used.
\item Irreducible polynomials of given degree (mod $p$) are constructed using
a probabilistic algorithm from \cite[pages 145--149]{Luneburg}.
\item The algorithm used for calculating the resultant of two polynomials
with integer coefficients is outlined in the article by R. Loos in
\cite[page 130]{Buchberger}.
\item The cyclotomic polynomial $\Phi_n(x)$ is calculated using an algorithm
from \cite[pages 354--356]{Luneburg}, which in turn is based on an account in
\cite[pages 58--63]{Luneburg1}. Factoring $\Phi_{p^n-1}(x)$ over $\BZ_p[x]$
gives the $\phi(p^n-1)/n$ monic primitive polynomials of degree $n$ over
$\BZ_p$.
\item The m--th root of a rational number is calculated using the algorithm
from \cite{Matthews1}.
\end{itemize}
\medskip
Any suggestions for improvement, as well as uncovering of bugs, should be
communicated to
\noindent
Dr. K. R. Matthews,
\noindent
Room 424, Mathematics Building,
\noindent
University of Queensland,
\noindent
St. Lucia, Brisbane, 4072.
\noindent
tel. (07) 3365\,3267.
\noindent
email address: krm@maths.uq.edu.au
\noindent
http://www.maths.uq.edu.au/\verb+~+krm/
\begin{thebibliography}{99}
\bibitem{Buchberger} B. Buchberger, G.E. Collins and R. Loos (Editors).
{\em Computer Algebra, Symbolic and Algebraic Computation.}
1972, Springer--Verlag Wien, New York.
\bibitem{Camion} P. Camion.
{\em A Deterministic Algorithm for Factorizing Polynomials of $F_q[x]$.}
Annals of Discrete Mathematics 17 (1983) 149--157.
\bibitem{Faddeeva} V.N. Faddeeva.
{\em Computational Methods in Linear Algebra.} 1959, Dover, New York.
\bibitem{Flanders}H. Flanders.
{\em Scientific Pascal.}
1984, Reston Publishing Company, Reston, Virginia.
\bibitem{Hartley} B. Hartley and T.O. Hawkes.
{\em Rings, Modules and Linear Algebra.}
1970, Chapman and Hall, London.
\bibitem{Knuth} D.E. Knuth.
{\em The Art of Computer Programming, Volume 2.}
Second Edition 1981, Addison--Wesley Publishing Company, Reading, Massachusetts.
\bibitem{Luneburg1} H. L\"{u}neburg.
{\em Galoisfelder, Kreisteilungsk\"{o}rper und Schieberegisterfolgen.}
1979, B.I. Wissenschaftsverlag, Mannheim/Wien/Z\"{u}rich.
\bibitem{Luneburg} H. L\"{u}neburg.
{\em On the Rational Normal Form of Endomorphisms.}
1987, B.I. Wissenschaftsverlag, Mannheim/Wien/Z\"{u}rich.
J.A.C.M. 22 (1975) 291--308.
\bibitem{Matthews1} K.R. Matthews.
{\em Computing mth roots.}
College Mathematics Journal 19 (1988) 174--176.
\bibitem{Matthews2} K.R. Matthews.
{\em A Rational Canonical Form Algorithm.}
Mathematica Bohemica 117 (1992) 315--324.
\bibitem{McWorter} W.A. McWorter, Jr.
{\em An Algorithm for the Characteristic Polynomial.}
\bibitem{Musser} D.R. Musser.
{\em Multivariate Polynomial Factorization.}
Mathematics Magazine 56 (1983) 168--175.
\bibitem{Trager} B.M. Trager.
{\em Algebraic Factoring and Rational Function Integration.}
Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation,
219--226.
\end{thebibliography}
\end{document}