Quelle edim.tex Sprache: Latech

% generated by GAPDoc2LaTeX from XML source (Frank Luebeck)
\documentclass[a4paper,11pt]{report}

\usepackage[top=37mm,bottom=37mm,left=27mm,right=27mm]{geometry}
\sloppy
\pagestyle{myheadings}
\usepackage{amssymb}
\usepackage[latin1]{inputenc}
\usepackage{makeidx}
\makeindex
\usepackage{color}
\definecolor{FireBrick}{rgb}{0.5812,0.0074,0.0083}
\definecolor{RoyalBlue}{rgb}{0.0236,0.0894,0.6179}
\definecolor{RoyalGreen}{rgb}{0.0236,0.6179,0.0894}
\definecolor{RoyalRed}{rgb}{0.6179,0.0236,0.0894}
\definecolor{LightBlue}{rgb}{0.8544,0.9511,1.0000}
\definecolor{Black}{rgb}{0.0,0.0,0.0}

\definecolor{linkColor}{rgb}{0.0,0.0,0.554}
\definecolor{citeColor}{rgb}{0.0,0.0,0.554}
\definecolor{fileColor}{rgb}{0.0,0.0,0.554}
\definecolor{urlColor}{rgb}{0.0,0.0,0.554}
\definecolor{promptColor}{rgb}{0.0,0.0,0.589}
\definecolor{brkpromptColor}{rgb}{0.589,0.0,0.0}
\definecolor{gapinputColor}{rgb}{0.589,0.0,0.0}
\definecolor{gapoutputColor}{rgb}{0.0,0.0,0.0}

%%  for a long time these were red and blue by default,
%%  now black, but keep variables to overwrite
\definecolor{FuncColor}{rgb}{0.0,0.0,0.0}
%% strange name because of pdflatex bug:
\definecolor{Chapter }{rgb}{0.0,0.0,0.0}
\definecolor{DarkOlive}{rgb}{0.1047,0.2412,0.0064}

\usepackage{fancyvrb}

\usepackage{mathptmx,helvet}
\usepackage[T1]{fontenc}
\usepackage{textcomp}

\usepackage[
            pdftex=true,
            bookmarks=true,
            a4paper=true,
            pdftitle={Written with GAPDoc},
            pdfcreator={LaTeX with hyperref package / GAPDoc},
            colorlinks=true,
            backref=page,
            breaklinks=true,
            linkcolor=linkColor,
            citecolor=citeColor,
            filecolor=fileColor,
            urlcolor=urlColor,
            pdfpagemode={UseNone},
           ]{hyperref}

\newcommand{\maintitlesize}{\fontsize{50}{55}\selectfont}

% write page numbers to a .pnr log file for online help
\newwrite\pagenrlog
\immediate\openout\pagenrlog =\jobname.pnr
\immediate\write\pagenrlog{PAGENRS := [}
\newcommand{\logpage}[1]{\protect\write\pagenrlog{#1, \thepage,}}
%% were never documented, give conflicts with some additional packages

\newcommand{\GAP}{\textsf{GAP}}

%% nicer description environments, allows long labels
\usepackage{enumitem}
\setdescription{style=nextline}

%% depth of toc
\setcounter{tocdepth}{1}

%% command for ColorPrompt style examples
\newcommand{\gapprompt}[1]{\color{promptColor}{\bfseries #1}}
\newcommand{\gapbrkprompt}[1]{\color{brkpromptColor}{\bfseries #1}}
\newcommand{\gapinput}[1]{\color{gapinputColor}{#1}}

\begin{document}

\logpage{[ 0, 0, 0 ]}
\begin{titlepage}
\mbox{}\vfill

\begin{center}{\maintitlesize \textbf{\textsf{EDIM}\mbox{}}}\\
\vfill

\hypersetup{pdftitle=\textsf{EDIM}}
\markright{\scriptsize \mbox{}\hfill \textsf{EDIM} \hfill\mbox{}}
{\Huge \textbf{Elementary Divisors and Integer Matrices\mbox{}}}\\
\vfill

{\Huge  Version 1.3.8 \mbox{}}\\[1cm]
{February 2024\mbox{}}\\[1cm]
\mbox{}\\[2cm]
{\Large \textbf{Frank L{\"u}beck    \mbox{}}}\\
\hypersetup{pdfauthor=Frank L{\"u}beck    }
\end{center}\vfill

\mbox{}\\
{\mbox{}\\
\small \noindent \textbf{Frank L{\"u}beck    }  Email: \href{mailto://Frank.Luebeck@Math.RWTH-Aachen.De} {\texttt{Frank.Luebeck@Math.RWTH-Aachen.De}}\\
  Homepage: \href{https://www.math.rwth-aachen.de/~Frank.Luebeck} {\texttt{https://www.math.rwth-aachen.de/\texttt{\symbol{126}}Frank.Luebeck}}\\
  Address: \begin{minipage}[t]{8cm}\noindent
Lehrstuhl D f{\"u}r Mathematik RWTH Aachen Pontdriesch 14/16 52062 Aachen
Germany \end{minipage}
}\\
\end{titlepage}

\newpage\setcounter{page}{2}
{\small
\section*{Copyright}
\logpage{[ 0, 0, 1 ]}
\index{License} {\copyright} 2000-2024 by Frank L{\"u}beck

\textsf{EDIM} is free software; you can redistribute it and/or modify it under the terms of
the \href{https://www.fsf.org/licenses/gpl.html} {GNU General Public License} as published by the Free Software Foundation; either version 2 of the License,
or (at your option) any later version. \mbox{}}\\[1cm]
\newpage

\def\contentsname{Contents\logpage{[ 0, 0, 2 ]}}

\tableofcontents
\newpage


\chapter{\textcolor{Chapter }{The \textsf{EDIM}-Package}}\label{Chap-EDIM}
\logpage{[ 1, 0, 0 ]}
\hyperdef{L}{X7AA826067CC8C395}{}
{
  \index{\textsf{EDIM}} \emph{(Elementary Divisors and Integer Matrices, by Frank L{\"u}beck)}

This chapter describes the functions defined in the \textsf{GAP}4 package \textsf{EDIM}. The main functions implement variants of an algorithm for computing for a
given prime $p$ the $p$-parts of the elementary divisors of an integer matrix. These algorithms use a $p$-adic method and are described by the author in \cite{L98} (see \texttt{ElementaryDivisorsPPartRk} (\ref{ElementaryDivisorsPPartRk})).

These functions were already applied to integer matrices of dimension greater
than $11000$ (which had many non-trivial elementary divisors which were products of small
primes).

Furthermore there are functions for finding the biggest elementary divisor of
an invertible integer matrix and the inverse of a rational invertible matrix
(see \texttt{ExponentSquareIntMatFullRank} (\ref{ExponentSquareIntMatFullRank}) and \texttt{InverseRatMat} (\ref{InverseRatMat})). These algorithms use $p$-adic approximations, explained in \ref{Sect-InvRatMatAlg}.

Finally we distribute implementations of some other algorithms for finding
elementary divisors or normal forms of integer matrices: A $p$-modular algorithm by Havas and Sterling from \cite{HS79} (see \texttt{ElementaryDivisorsPPartHavasSterling} (\ref{ElementaryDivisorsPPartHavasSterling})) and LLL-based algorithms for extended greatest common divisors of integers
(see \texttt{GcdexIntLLL} (\ref{GcdexIntLLL})) and for Hermite normal forms of integer matrices with (very nice)
transforming matrices (see \texttt{HermiteIntMatLLL} (\ref{HermiteIntMatLLL})).

Please, send me an e-mail (\href{mailto://Frank.Luebeck@Math.RWTH-Aachen.De} {\texttt{Frank.Luebeck@Math.RWTH-Aachen.De}}) if you have any questions, remarks, suggestions, etc. concerning this
mini-package. Also, I would like to hear about applications of this package.

Frank L{\"u}beck
\section{\textcolor{Chapter }{Installation of the \textsf{EDIM} package}}\label{Sect-Install}
\logpage{[ 1, 1, 0 ]}
\hyperdef{L}{X84D3F5E77E3BF046}{}
{
  To install this package first unpack it inside some GAP root directory in the
subdirectory \texttt{pkg} (see  (\textbf{Reference: Installing a GAP Package})). Then the \textsf{EDIM} package can already be loaded and used. But we strongly recommend to compile a
kernel function as well during installation, otherwise the function \texttt{ElementaryDivisorsPPartRkExpSmall} (\ref{ElementaryDivisorsPPartRkExpSmall}) will not be available.

To install the kernel function go to the directory \texttt{pkg/EDIM-...} to which the package was extracted and call

\texttt{/bin/sh ./configure [path]}

where \texttt{path} is a path to the main \textsf{GAP} root directory (if not given, the default \texttt{../..} is assumed).  Afterwards call \texttt{make} to compile a binary file.

If you have installed several GAP kernels repeat these two steps for each of
them.  You can run a test of the installation by typing \texttt{make test}.

\subsection{\textcolor{Chapter }{InfoEDIM}}
\logpage{[ 1, 1, 1 ]}\nobreak
\hyperdef{L}{X7AF83FEC7CD0311C}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{InfoEDIM\index{InfoEDIM@\texttt{InfoEDIM}}
\label{InfoEDIM}
}\hfill{\scriptsize (info class)}}\\

This is an \texttt{Info} class for the \textsf{EDIM}-package. By \texttt{SetInfoLevel(InfoEDIM, 1);} you can switch on the printing of some information during the computations of
certain \textsf{EDIM}-functions. }

}


\section{\textcolor{Chapter }{$p$-Parts of Elementary Divisors}}\label{Sect-PPElDiv}
\logpage{[ 1, 2, 0 ]}
\hyperdef{L}{X818BE04687230849}{}
{
  Here we explain the main functions of the package.

\subsection{\textcolor{Chapter }{ElementaryDivisorsPPartRk}}
\logpage{[ 1, 2, 1 ]}\nobreak
\hyperdef{L}{X813B0D73868CD751}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ElementaryDivisorsPPartRk({\mdseries\slshape A, p[, rk]})\index{ElementaryDivisorsPPartRk@\texttt{ElementaryDivisorsPPartRk}}
\label{ElementaryDivisorsPPartRk}
}\hfill{\scriptsize (function)}}\\
\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ElementaryDivisorsPPartRkI({\mdseries\slshape A, p, rk})\index{ElementaryDivisorsPPartRkI@\texttt{ElementaryDivisorsPPartRkI}}
\label{ElementaryDivisorsPPartRkI}
}\hfill{\scriptsize (function)}}\\
\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ElementaryDivisorsPPartRkII({\mdseries\slshape A, p, rk})\index{ElementaryDivisorsPPartRkII@\texttt{ElementaryDivisorsPPartRkII}}
\label{ElementaryDivisorsPPartRkII}
}\hfill{\scriptsize (function)}}\\
\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ElementaryDivisorsPPartRkExp({\mdseries\slshape A, p, rk, exp})\index{ElementaryDivisorsPPartRkExp@\texttt{ElementaryDivisorsPPartRkExp}}
\label{ElementaryDivisorsPPartRkExp}
}\hfill{\scriptsize (function)}}\\
\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ElementaryDivisorsPPartRkExpSmall({\mdseries\slshape A, p, rk, exp, il})\index{ElementaryDivisorsPPartRkExpSmall@\texttt{ElementaryDivisorsPPartRkExpSmall}}
\label{ElementaryDivisorsPPartRkExpSmall}
}\hfill{\scriptsize (function)}}\\

These functions return a list $[m_1, m_2, \ldots, m_r]$ where $m_i$ is the number of nonzero elementary divisors of \mbox{\texttt{\mdseries\slshape A}} divisible by $\mbox{\texttt{\mdseries\slshape p}}^i$ (see \texttt{ElementaryDivisorsMat} (\textbf{Reference: ElementaryDivisorsMat}) for a definition of the elementary divisors).

The algorithms for these functions are described in \cite{L98}.

\mbox{\texttt{\mdseries\slshape A}} must be a matrix with integer entries, \mbox{\texttt{\mdseries\slshape p}} a prime, and \mbox{\texttt{\mdseries\slshape rk}} the rank of \mbox{\texttt{\mdseries\slshape A}} (as rational matrix). In the first version of the command \mbox{\texttt{\mdseries\slshape rk}} is computed, if it is not given.

The first version of the command delegates its job to the fourth version by
trying growing values for \mbox{\texttt{\mdseries\slshape exp}}, see below.

The second and third versions implement the main algorithm described in \cite{L98} and a variation. Here \texttt{ElementaryDivisorsPPartRkII} has a bit more overhead, but can be advantageous because the intermediate
entries during the computation can be much smaller.

In the fourth form \mbox{\texttt{\mdseries\slshape exp}} must be an upper bound for the highest power of \mbox{\texttt{\mdseries\slshape p}} appearing in an elementary divisor of \mbox{\texttt{\mdseries\slshape A}}. This information allows reduction of matrix entries modulo $\mbox{\texttt{\mdseries\slshape p}}^{{\mbox{\texttt{\mdseries\slshape exp+1}}}}$ during the computation.

If \mbox{\texttt{\mdseries\slshape exp}} is too small or the given \mbox{\texttt{\mdseries\slshape rk}} is too large the function returns \texttt{fail}.

If $\mbox{\texttt{\mdseries\slshape p}}^{\mbox{\texttt{\mdseries\slshape exp}}}$ is small enough we use internally a kernel function which can also be used
directly in the fifth form of the command. There \mbox{\texttt{\mdseries\slshape il}} can be $0$ or $1$ where in the second case some information is printed during the computation.

More precisely, \texttt{ElementaryDivisorsPPartRkExpSmall} is applicable when $\mbox{\texttt{\mdseries\slshape p}}^{{\mbox{\texttt{\mdseries\slshape exp}}+1}} < 2^{{b-4}}$ and $(\mbox{\texttt{\mdseries\slshape p}}^{{\mbox{\texttt{\mdseries\slshape exp}}+1}} - 1)(p-1) < 2^b$ where $b=32$ in a 32-bit version of \textsf{GAP} and $b=64$ in a 64-bit version of \textsf{GAP}.

This last form of the function was already succesfully applied to dense
matrices of rank up to $11000$.

Note that you have to compile a file (see \ref{Sect-Install}) while installing this package, if you want to have this kernel function
available.

\begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
  !gapprompt@gap>| !gapinput@ReadPackage("edim",  "tst/mat");|
  Reading 242x242 integer matrix 'mat' with elementary divisors 'eldiv'.
  true
  !gapprompt@gap>| !gapinput@ElementaryDivisorsPPartRkI(mat, 2, 242); time; # mat has full rank|
  [ 94, 78, 69, 57, 23, 23, 9, 2, 2, 0 ]
  490
  !gapprompt@gap>| !gapinput@ElementaryDivisorsPPartRkExpSmall(mat, 2, 242, 10, 0); time;|
  [ 94, 78, 69, 57, 23, 23, 9, 2, 2, 0 ]
  10
\end{Verbatim}
}



\subsection{\textcolor{Chapter }{ElementaryDivisorsPPartHavasSterling}}
\logpage{[ 1, 2, 2 ]}\nobreak
\hyperdef{L}{X82EC4724865F4DF9}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ElementaryDivisorsPPartHavasSterling({\mdseries\slshape A, p, d})\index{ElementaryDivisorsPPartHavasSterling@\texttt{Elementary}\-\texttt{Divisors}\-\texttt{P}\-\texttt{Part}\-\texttt{Havas}\-\texttt{Sterling}}
\label{ElementaryDivisorsPPartHavasSterling}
}\hfill{\scriptsize (function)}}\\

For an integer matrix \mbox{\texttt{\mdseries\slshape A}} and a prime \mbox{\texttt{\mdseries\slshape p}} this function returns a list $[m_1, m_2, \ldots, m_r]$ where $m_i$ is the number of nonzero elementary divisors of \mbox{\texttt{\mdseries\slshape A}} divisible by $\mbox{\texttt{\mdseries\slshape p}}^i$.

An upper bound \mbox{\texttt{\mdseries\slshape d}} for the highest power of \mbox{\texttt{\mdseries\slshape p}} appearing in an elementary divisor of \mbox{\texttt{\mdseries\slshape A}} must be given. Smaller \mbox{\texttt{\mdseries\slshape d}} improve the performance of the algorithm considerably.

This is an implementation of the modular algorithm described in \cite{HS79}.

We added a slight improvement: we divide the considered submatrices by the \mbox{\texttt{\mdseries\slshape p}}-part of the greatest common divisor of all entries (and lower the \mbox{\texttt{\mdseries\slshape d}} appropriately). This reduces the size of the entries and often shortens the
pivot search.

\begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
  !gapprompt@gap>| !gapinput@ReadPackage("edim",  "tst/mat");|
  Reading 242x242 integer matrix 'mat' with elementary divisors 'eldiv'.
  true
  !gapprompt@gap>| !gapinput@ElementaryDivisorsPPartHavasSterling(mat, 2, 10); time;|
  [ 94, 78, 69, 57, 23, 23, 9, 2, 2 ]
  1260
\end{Verbatim}
}

}


\section{\textcolor{Chapter }{Inverse of Rational Matrices}}\label{Sect-InvRatMat}
\logpage{[ 1, 3, 0 ]}
\hyperdef{L}{X80FF39C07E03D7EF}{}
{


\subsection{\textcolor{Chapter }{InverseRatMat}}
\logpage{[ 1, 3, 1 ]}\nobreak
\hyperdef{L}{X7A9656D47C4D2D16}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{InverseRatMat({\mdseries\slshape A[, p]})\index{InverseRatMat@\texttt{InverseRatMat}}
\label{InverseRatMat}
}\hfill{\scriptsize (function)}}\\

This function returns the inverse of an invertible matrix over the rational
numbers.

It first computes the inverse modulo some prime \mbox{\texttt{\mdseries\slshape p}}, computes from this a \mbox{\texttt{\mdseries\slshape p}}-adic approximation to the inverse and finally constructs the rational entries
from their \mbox{\texttt{\mdseries\slshape p}}-adic approximations. See section \ref{Sect-InvRatMatAlg} for more details.

This seems to be better than \textsf{GAP}'s standard Gau{\ss} algorithm (\texttt{A\texttt{\symbol{94}}-1}) already for small matrices. (Try, e.g., \texttt{RandomMat(20,20,[-10000..10000])} or \texttt{RandomMat(100,100)}.)

The optional argument \mbox{\texttt{\mdseries\slshape p}} should be a prime such that \mbox{\texttt{\mdseries\slshape A}} modulo \mbox{\texttt{\mdseries\slshape p}} is invertible (default is $\mbox{\texttt{\mdseries\slshape p}}=251$). If \mbox{\texttt{\mdseries\slshape A}} is not invertible modulo \mbox{\texttt{\mdseries\slshape p}} then \mbox{\texttt{\mdseries\slshape p}} is automatically replaced by the next prime.

}



\subsection{\textcolor{Chapter }{RationalSolutionIntMat}}
\logpage{[ 1, 3, 2 ]}\nobreak
\hyperdef{L}{X8302B31E86B3AFDB}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{RationalSolutionIntMat({\mdseries\slshape A, v[, p[, invA]]})\index{RationalSolutionIntMat@\texttt{RationalSolutionIntMat}}
\label{RationalSolutionIntMat}
}\hfill{\scriptsize (function)}}\\

This function returns the solution $x$ of the system of linear equations $x \mbox{\texttt{\mdseries\slshape A}} = \mbox{\texttt{\mdseries\slshape v}}$.

Here, \mbox{\texttt{\mdseries\slshape A}} must be a matrix with integer entries which is invertible over the rationals
and \mbox{\texttt{\mdseries\slshape v}} must be a vector with integer entries of the appropriate length.

The optional arguments are a prime \mbox{\texttt{\mdseries\slshape p}} such that $\mbox{\texttt{\mdseries\slshape A}} \pmod{p}$ is invertible (if not given, $p = 251$ is assumed) and the inverse \mbox{\texttt{\mdseries\slshape invA}} of $\mbox{\texttt{\mdseries\slshape A}} \pmod{p}$.

The solution is computed via $p$-adic approximation as explained in \ref{Sect-InvRatMatAlg}.

}



\subsection{\textcolor{Chapter }{ExponentSquareIntMatFullRank}}
\logpage{[ 1, 3, 3 ]}\nobreak
\hyperdef{L}{X86DA61D978D2D889}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ExponentSquareIntMatFullRank({\mdseries\slshape A[, p[, nr]]})\index{ExponentSquareIntMatFullRank@\texttt{ExponentSquareIntMatFullRank}}
\label{ExponentSquareIntMatFullRank}
}\hfill{\scriptsize (function)}}\\

This function returns the biggest elementary divisor of a square integer
matrix \mbox{\texttt{\mdseries\slshape A}} of full rank.

For such a matrix \mbox{\texttt{\mdseries\slshape A}} the least common multiple of the denominators of all entries of the inverse
matrix $\mbox{\texttt{\mdseries\slshape A}}^{-1}$ is exactly the biggest elementary divisor of \mbox{\texttt{\mdseries\slshape A}}.

This function is implemented by a slight modification of \texttt{InverseRatMat} (\ref{InverseRatMat}). The third argument \mbox{\texttt{\mdseries\slshape nr}} tells the function to return the least common multiple of the first \mbox{\texttt{\mdseries\slshape nr}} rows of the rational inverse matrix only. Very often the function will already
return the biggest elementary divisor with $\mbox{\texttt{\mdseries\slshape nr}}=2$ or $3$ (and the command without this argument would spend most time in checking, that
this is correct).

The optional argument \mbox{\texttt{\mdseries\slshape p}} should be a prime such that \mbox{\texttt{\mdseries\slshape A}} modulo \mbox{\texttt{\mdseries\slshape p}} is invertible (default is $\mbox{\texttt{\mdseries\slshape p}}=251$). If \mbox{\texttt{\mdseries\slshape A}} is not invertible modulo \mbox{\texttt{\mdseries\slshape p}} then \mbox{\texttt{\mdseries\slshape p}} is automatically replaced by the next prime.

\begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
  !gapprompt@gap>| !gapinput@ReadPackage("edim",  "tst/mat");|
  Reading 242x242 integer matrix 'mat' with elementary divisors 'eldiv'.
  true
  !gapprompt@gap>| !gapinput@inv := InverseRatMat(mat);; time;                      |
  840
  !gapprompt@gap>| !gapinput@ExponentSquareIntMatFullRank(mat, 101, 3); # same as without the `3'|
  115200
\end{Verbatim}
}

}


\section{\textcolor{Chapter }{All Elementary Divisors Using p-adic Method}}\label{Sect-ElDivPad}
\logpage{[ 1, 4, 0 ]}
\hyperdef{L}{X7A6548FA7C837D27}{}
{
  In the following two functions we put things together. In particular we handle
the prime parts of the elementary divisors efficiently for primes appearing
with low powers in the highest elementary divisor respectively determinant
divisor.

\subsection{\textcolor{Chapter }{ElementaryDivisorsSquareIntMatFullRank}}
\logpage{[ 1, 4, 1 ]}\nobreak
\hyperdef{L}{X7B6A3B8486872B0C}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ElementaryDivisorsSquareIntMatFullRank({\mdseries\slshape A})\index{ElementaryDivisorsSquareIntMatFullRank@\texttt{Elementary}\-\texttt{Divisors}\-\texttt{Square}\-\texttt{Int}\-\texttt{Mat}\-\texttt{Full}\-\texttt{Rank}}
\label{ElementaryDivisorsSquareIntMatFullRank}
}\hfill{\scriptsize (function)}}\\

This function returns a list of nonzero elementary divisors of an integer
matrix \mbox{\texttt{\mdseries\slshape A}}.

Here we start with computing the biggest elementary divisor via \texttt{ExponentSquareIntMatFullRank} (\ref{ExponentSquareIntMatFullRank}). If it runs into a problem because \mbox{\texttt{\mdseries\slshape A}} is singular modulo a choosen prime (it starts by default with 251) then the
prime is automatically replaced by the next one.

The rest is done using \texttt{ElementaryDivisorsPPartRkExp} (\ref{ElementaryDivisorsPPartRkExp}) and \texttt{RankMod} (\ref{RankMod}).

The function fails if the biggest elementary divisor cannot be completely
factored and the non-factored part is not a divisor of the biggest elementary
divisor only.

Note that this function may for many matrices not be the best choice for
computing all elementary divisors. You may first try the standard \textsf{GAP} library routines for Smith normal form instead of this function. Nevertheless
remember \texttt{ElementaryDivisorsSquareIntMatFullRank} for hard and big examples. It is particularly good when the largest elementary
divisor is a very small factor of the determinant.
\begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
  !gapprompt@gap>| !gapinput@Collected(ElementaryDivisorsSquareIntMatFullRank(mat));      |
  [ [ 1, 49 ], [ 3, 99 ], [ 6, 7 ], [ 30, 9 ], [ 60, 9 ], [ 120, 2 ],
    [ 360, 10 ], [ 720, 22 ], [ 3600, 12 ], [ 14400, 14 ],
    [ 28800, 7 ], [ 115200, 2 ] ]
  !gapprompt@gap>| !gapinput@time;|
  860
  !gapprompt@gap>| !gapinput@last2 = Collected(DiagonalOfMat(NormalFormIntMat(mat, 1).normal));|
  true
  !gapprompt@gap>| !gapinput@time;|
  5170
\end{Verbatim}
}



\subsection{\textcolor{Chapter }{ElementaryDivisorsIntMatDeterminant}}
\logpage{[ 1, 4, 2 ]}\nobreak
\hyperdef{L}{X821E30477A5DCE68}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ElementaryDivisorsIntMatDeterminant({\mdseries\slshape A, det[, rk]})\index{ElementaryDivisorsIntMatDeterminant@\texttt{ElementaryDivisorsIntMatDeterminant}}
\label{ElementaryDivisorsIntMatDeterminant}
}\hfill{\scriptsize (function)}}\\

This function returns a list of nonzero elementary divisors of an integer
matrix \mbox{\texttt{\mdseries\slshape A}}.

Here \mbox{\texttt{\mdseries\slshape det}} must be an integer which is a multiple of the biggest determinant divisor of \mbox{\texttt{\mdseries\slshape A}}. If the matrix does not have full rank then its rank \mbox{\texttt{\mdseries\slshape rk}} must be given, too.

The argument \mbox{\texttt{\mdseries\slshape det}} can be given in the form of \texttt{Collected(FactorsInt(\mbox{\texttt{\mdseries\slshape det}}))}.

This function handles prime divisors of \mbox{\texttt{\mdseries\slshape det}} with multiplicity smaller than 4 specially, for the other prime divisors $p$ it delegates to \texttt{ElementaryDivisorsPPartRkExp} (\ref{ElementaryDivisorsPPartRkExp}) where the \mbox{\texttt{\mdseries\slshape exp}} argument is the multiplicity of the $p$ in \mbox{\texttt{\mdseries\slshape det}}. (Note that this is not very good when $p$ has actually a much smaller multiplicity in the largest elementary divisor.)

\begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
  !gapprompt@gap>| !gapinput@ReadPackage("edim",  "tst/mat");|
  Reading 242x242 integer matrix 'mat' with elementary divisors 'eldiv'.
  true
  !gapprompt@gap>| !gapinput@# not so good:|
  !gapprompt@gap>| !gapinput@ElementaryDivisorsIntMatDeterminant(mat,Product(eldiv)) = |
  !gapprompt@>| !gapinput@Concatenation([1..49]*0+1, eldiv); time;|
  true
  5490
\end{Verbatim}
}

}


\section{\textcolor{Chapter }{Gcd and Normal Forms Using LLL}}\label{Sect-NFIntMatLLL}
\logpage{[ 1, 5, 0 ]}
\hyperdef{L}{X788047737FA04422}{}
{
  The \textsf{EDIM}-mini package also contains implementations of an extended Gcd-algorithm for
integers and a Hermite and Smith normal form algorithm for integer matrices
using LLL-techiques. They are well described in the paper \cite{HMM98} by Havas, Majewski and Matthews.

They are particularly useful if one wants to have the normal forms together
with transforming matrices. These transforming matrices have spectacularly
nice (i.e., ``small'') entries in cases of input matrices which are non-square or not of full rank
(otherwise the transformation to the Hermite normal form is unique).

In detail:

\subsection{\textcolor{Chapter }{GcdexIntLLL}}
\logpage{[ 1, 5, 1 ]}\nobreak
\hyperdef{L}{X799B1A5285D00859}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{GcdexIntLLL({\mdseries\slshape n1, n2, ...})\index{GcdexIntLLL@\texttt{GcdexIntLLL}}
\label{GcdexIntLLL}
}\hfill{\scriptsize (function)}}\\

This function returns for integers $\mbox{\texttt{\mdseries\slshape n1}}, \mbox{\texttt{\mdseries\slshape n2}}, \ldots$ a list $[g, [c_1, c_2, \ldots]]$, where $g = c_1\mbox{\texttt{\mdseries\slshape n1}} + c_2\mbox{\texttt{\mdseries\slshape n2}} + \ldots$ is the greatest common divisor of the \mbox{\texttt{\mdseries\slshape ni}}. Here all the $c_i$ are usually very small.
\begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
  !gapprompt@gap>| !gapinput@GcdexIntLLL( 517, 244, -304, -872, -286, 854, 866, 224, -765, -38);|
  [ 1, [ 0, 0, 0, 0, 1, 0, 1, 1, 1, 1 ] ]
\end{Verbatim}
}



\subsection{\textcolor{Chapter }{HermiteIntMatLLL}}
\logpage{[ 1, 5, 2 ]}\nobreak
\hyperdef{L}{X7C6AE6777B72F9D2}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{HermiteIntMatLLL({\mdseries\slshape A})\index{HermiteIntMatLLL@\texttt{HermiteIntMatLLL}}
\label{HermiteIntMatLLL}
}\hfill{\scriptsize (function)}}\\

This returns the Hermite normal form of an integer matrix \mbox{\texttt{\mdseries\slshape A}} and uses the LLL-algorithm to avoid entry explosion. }



\subsection{\textcolor{Chapter }{HermiteIntMatLLLTrans}}
\logpage{[ 1, 5, 3 ]}\nobreak
\hyperdef{L}{X862962B7878A284F}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{HermiteIntMatLLLTrans({\mdseries\slshape A})\index{HermiteIntMatLLLTrans@\texttt{HermiteIntMatLLLTrans}}
\label{HermiteIntMatLLLTrans}
}\hfill{\scriptsize (function)}}\\

This function returns a pair of matrices $[H, L]$ where $H = L \mbox{\texttt{\mdseries\slshape A}}$ is the Hermite normal form of an integer matrix \mbox{\texttt{\mdseries\slshape A}}. The transforming matrix $L$ can have surprisingly small entries.
\begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
  !gapprompt@gap>| !gapinput@ReadPackage("edim",  "tst/mat2");|
  Reading 34x34 integer matrix 'mat2' with elementary divisors 'eldiv2'.
  true
  !gapprompt@gap>| !gapinput@tr := HermiteIntMatLLLTrans(mat2);; Maximum(List(Flat(tr[2]), AbsInt));|
  606
  !gapprompt@gap>| !gapinput@tr[2]*mat2 = tr[1];                                                |
  true
\end{Verbatim}
}



\subsection{\textcolor{Chapter }{SmithIntMatLLL}}
\logpage{[ 1, 5, 4 ]}\nobreak
\hyperdef{L}{X8626F15179C09798}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{SmithIntMatLLL({\mdseries\slshape A})\index{SmithIntMatLLL@\texttt{SmithIntMatLLL}}
\label{SmithIntMatLLL}
}\hfill{\scriptsize (function)}}\\

This function returns the Smith normal form of an integer matrix \mbox{\texttt{\mdseries\slshape A}} using the LLL-algorithm to avoid entry explosion. }



\subsection{\textcolor{Chapter }{SmithIntMatLLLTrans}}
\logpage{[ 1, 5, 5 ]}\nobreak
\hyperdef{L}{X86094B1B7C87EBF6}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{SmithIntMatLLLTrans({\mdseries\slshape A})\index{SmithIntMatLLLTrans@\texttt{SmithIntMatLLLTrans}}
\label{SmithIntMatLLLTrans}
}\hfill{\scriptsize (function)}}\\

This function returns $[S, L, R]$ where $S = L \mbox{\texttt{\mdseries\slshape A}} R$ is the Smith normal form of an integer matrix \mbox{\texttt{\mdseries\slshape A}}.

We apply the algorithm for Hermite normal form several times to get the Smith
normal form, that is not in the paper \cite{HMM98}. The transforming matrices need not be as nice as for the Hermite normal
form.

\begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
  !gapprompt@gap>| !gapinput@ReadPackage("edim",  "tst/mat2");|
  Reading 34x34 integer matrix 'mat2' with elementary divisors 'eldiv2'.
  true
  !gapprompt@gap>| !gapinput@tr := SmithIntMatLLLTrans(mat2);;|
  !gapprompt@gap>| !gapinput@tr[2] * mat2 * tr[3] = tr[1];    |
  true
\end{Verbatim}
}

}


\section{\textcolor{Chapter }{Utility Functions from the \textsf{EDIM}-package}}\label{Sect-Util}
\logpage{[ 1, 6, 0 ]}
\hyperdef{L}{X832582857EB36B23}{}
{


\subsection{\textcolor{Chapter }{RatNumberFromModular}}
\logpage{[ 1, 6, 1 ]}\nobreak
\hyperdef{L}{X7EC844F97C469C03}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{RatNumberFromModular({\mdseries\slshape n, k, l, x})\index{RatNumberFromModular@\texttt{RatNumberFromModular}}
\label{RatNumberFromModular}
}\hfill{\scriptsize (function)}}\\

This function returns $r/s = \mbox{\texttt{\mdseries\slshape x}} \pmod{\mbox{\texttt{\mdseries\slshape n}}}$, if it exists. More precisely:

\mbox{\texttt{\mdseries\slshape n}}, \mbox{\texttt{\mdseries\slshape k}}, \mbox{\texttt{\mdseries\slshape l}} must be positive integers with $2\mbox{\texttt{\mdseries\slshape k}}\mbox{\texttt{\mdseries\slshape l}} \leq \mbox{\texttt{\mdseries\slshape n}}$ and \mbox{\texttt{\mdseries\slshape x}} an integer with $-\mbox{\texttt{\mdseries\slshape n}}/2 < \mbox{\texttt{\mdseries\slshape x}} \leq \mbox{\texttt{\mdseries\slshape n}}/2$. If it exists this function returns a rational number $r/s$ with $0 < s < \mbox{\texttt{\mdseries\slshape l}}$, $\gcd(s, \mbox{\texttt{\mdseries\slshape n}}) = 1$, $-\mbox{\texttt{\mdseries\slshape k}} < r < \mbox{\texttt{\mdseries\slshape k}}$ and $r/s$ congruent to $\mbox{\texttt{\mdseries\slshape x}} \pmod{\mbox{\texttt{\mdseries\slshape n}}}$ (i.e., $\mbox{\texttt{\mdseries\slshape n}} \mid r - s \mbox{\texttt{\mdseries\slshape x}}$). Such an $r/s$ is unique. The function returns \texttt{fail} if such a number does not exist.

}



\subsection{\textcolor{Chapter }{InverseIntMatMod}}
\logpage{[ 1, 6, 2 ]}\nobreak
\hyperdef{L}{X78518E1D81435762}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{InverseIntMatMod({\mdseries\slshape A, p})\index{InverseIntMatMod@\texttt{InverseIntMatMod}}
\label{InverseIntMatMod}
}\hfill{\scriptsize (function)}}\\

This function returns an inverse matrix modulo a prime \mbox{\texttt{\mdseries\slshape p}} or \texttt{fail}. More precisely:

\mbox{\texttt{\mdseries\slshape A}} must be an integer matrix and \mbox{\texttt{\mdseries\slshape p}} a prime such that \mbox{\texttt{\mdseries\slshape A}} is invertible modulo \mbox{\texttt{\mdseries\slshape p}}. This function returns an integer matrix \mbox{\texttt{\mdseries\slshape inv}} with entries in the range $]-\mbox{\texttt{\mdseries\slshape p}}/2 \ldots \mbox{\texttt{\mdseries\slshape p}}/2]$ such that \mbox{\texttt{\mdseries\slshape inv}}\mbox{\texttt{\mdseries\slshape A}} reduced modulo p is the identity matrix.

It returns \texttt{fail} if the inverse modulo \mbox{\texttt{\mdseries\slshape p}} does not exist. This function is particularly fast for primes smaller 256. }



\subsection{\textcolor{Chapter }{HadamardBoundIntMat}}
\logpage{[ 1, 6, 3 ]}\nobreak
\hyperdef{L}{X7CDF3D2081207080}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{HadamardBoundIntMat({\mdseries\slshape A})\index{HadamardBoundIntMat@\texttt{HadamardBoundIntMat}}
\label{HadamardBoundIntMat}
}\hfill{\scriptsize (function)}}\\

The Hadamard bound for a square integer matrix \mbox{\texttt{\mdseries\slshape A}} is the product of Euclidean norms of the nonzero rows (or columns) of \mbox{\texttt{\mdseries\slshape A}}. It is an upper bound for the absolute value of the determinant of \mbox{\texttt{\mdseries\slshape A}}. }



\subsection{\textcolor{Chapter }{CheapFactorsInt}}
\logpage{[ 1, 6, 4 ]}\nobreak
\hyperdef{L}{X7BAB977C7EB05067}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{CheapFactorsInt({\mdseries\slshape n[, nr]})\index{CheapFactorsInt@\texttt{CheapFactorsInt}}
\label{CheapFactorsInt}
}\hfill{\scriptsize (function)}}\\

This function returns a list of factors of an integer \mbox{\texttt{\mdseries\slshape n}}, including ``small'' prime factors - here the optional argument \mbox{\texttt{\mdseries\slshape nr}} is the number of iterations for `FactorsRho' (default is 2000).

This is only a slight modification of the library function \texttt{FactorsInt} (\textbf{Reference: FactorsInt}) which avoids an error message when the number is not completely factored.

}



\subsection{\textcolor{Chapter }{RankMod}}
\logpage{[ 1, 6, 5 ]}\nobreak
\hyperdef{L}{X8312EDA78209B4EA}{}
{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{RankMod({\mdseries\slshape A, p})\index{RankMod@\texttt{RankMod}}
\label{RankMod}
}\hfill{\scriptsize (function)}}\\

This function returns the rank of an integer matrix \mbox{\texttt{\mdseries\slshape A}} modulo \mbox{\texttt{\mdseries\slshape p}}. Here \mbox{\texttt{\mdseries\slshape p}} must not necessarily be a prime. If it is not and this function returns an
integer, then this is the rank of \mbox{\texttt{\mdseries\slshape A}} for all prime divisors of \mbox{\texttt{\mdseries\slshape p}}.

If during the computation a factorisation of \mbox{\texttt{\mdseries\slshape p}} is found (because some pivot entry has nontrivial greatest common divisor with \mbox{\texttt{\mdseries\slshape p}}) then the function is recursively applied to the found factors \texttt{f{\textunderscore}i} of \mbox{\texttt{\mdseries\slshape p}}. The result is then given in the form \texttt{[[f{\textunderscore}1, rk{\textunderscore}1], [f{\textunderscore}2,
rk{\textunderscore}2], ...]}.

The idea to make this function useful for non primes was to use it with large
factors of the biggest elementary divisor of \mbox{\texttt{\mdseries\slshape A}} whose prime factorization cannot be found easily.

\begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example]
  !gapprompt@gap>| !gapinput@ReadPackage("edim",  "tst/mat");|
  Reading 242x242 integer matrix 'mat' with elementary divisors 'eldiv'.
  true
  !gapprompt@gap>| !gapinput@RankMod(mat, 5);|
  155
  !gapprompt@gap>| !gapinput@RankMod(mat, (2*79*4001));|
  [ [ 2, 148 ], [ 79, 242 ], [ 4001, 242 ] ]
\end{Verbatim}
}

}


\section{\textcolor{Chapter }{InverseRatMat - the Algorithm}}\label{Sect-InvRatMatAlg}
\logpage{[ 1, 7, 0 ]}
\hyperdef{L}{X83FD1AAB7EB2E934}{}
{
  The idea is to recover a rational matrix from an $l$-adic approximation for some prime $l$. This description came out of discussions with J{\"u}rgen M{\"u}ller. I thank
John Cannon for pointing out that the basic idea already appeared in the paper \cite{D82} of Dixon.

Let $A$ be an invertible matrix over the rational numbers. By multiplying with a
constant we may assume that its entries are in fact integers.

(1) We first describe how to find an $l$-adic approximation of $A^{-1}$. Find a prime $l$ such that $A$ is invertible modulo $l$ and let $B$ be the integer matrix with entries in the range $\left]-l/2,l/2\right]$ such that $BA$ is congruent to the identity matrix modulo $l$. (This can be computed fast by usual Gau{\ss} elimination.)

Now let $v \in {\ensuremath{\mathbb Z}}^r$ be a row vector. Define two sequences $v_i$ and $x_i$ of row vectors in ${\ensuremath{\mathbb Z}}^r$ by: $x_0 := 0 \in {\ensuremath{\mathbb Z}}^r$, $v_0 := -v$ and for $i > 0$ set $x_i$ to the vector congruent to $-v_{i-1} B$ modulo $l$ having entries in the range $\left]-l/2, l/2\right]$. Then all entries of $x_i A + v_{i-1}$ are divisible by $l$ and we set $v_i := (1/l) \cdot (x_i A + v_{i-1})$.

Induction shows that for $y_i := \sum_{k=1}^{i} l^{k-1} x_k$ we have $y_i A = v + l^i v_i$ for all $i \geq 0$. Hence the sequence $y_i$, $i \geq 0$, gives an $l$-adic approximation to the vector $y \in {\ensuremath{\mathbb Q}}^r$ with $y A = v$.

(2) The second point is to show how we can get the vector $y$ from a sufficiently good approximation $y_i$. Note that the sequence of $y_i$ becomes constant for $i \geq i_0$ if all entries of $y$ are integers of absolute value smaller than $l^{i_0} / 2$ because of our choice of representatives of residue classes modulo $l$ in the interval $\left]-l/2, l/2\right]$.

More generally consider $a / b \in {\ensuremath{\mathbb Q}}$ with $b > 0$ and $a, b$ coprime. Then there is for each $n \in {\ensuremath{\mathbb N}}$ which is coprime to $b$ a unique $c \in {\ensuremath{\mathbb Z}}$ with $-n / 2 < c \leq n / 2$ and $a \equiv c b \pmod{n}$. This $c$ can be computed via the extended Euclidean algorithm applied to $b$ and $n$.

Now let $n, \alpha, \beta \in {\ensuremath{\mathbb N}}$ with $2 \alpha \beta \leq n$. Then the map $\{a/b \in {\ensuremath{\mathbb Q}} \mid -\alpha \leq a \leq \alpha, 1 \leq b <
\beta \} \rightarrow \left]-n/2, n/2\right]$, $a/b \mapsto c$ (defined as above) is injective (since for $a/b$, $a'/b'$ in the above set we have $a b' - a' b \equiv 0 \pmod{n}$ if and only if $a b' - a' b = 0$).

In practice we can use for any $c \in \left]-n/2, n/2\right]$ a certain extended Euclidean algorithm applied to $n$ and $c$ to decide if $c$ is in the image of the above map and to find the corresponding $a/b$ if it exists.

(3) To put things together we apply (2) to the entries of the vectors $y_i$ constructed in (1), choosing $n = l^i$, $\alpha = \sqrt{n}/2$ and $\beta = \sqrt{n}$. If we have found this way a candidate for $y$ we can easily check if it is correct by computing $y A$. If $\mu$ is the maximal absolute value of all numerators and denominators of the
entries of $y$ it is clear from (2) that we will find $y$ from $y_i$ if $l^i > 2 \mu^2$.

(4) If we take as $v$ in (1) to(3) all standard unit vectors we clearly get the rows of $A^{-1}$. But we can do it better. Namely we can take as $v$ the standard unit vectors multiplied by the least common multiple $\epsilon$ of the denominators of the already computed entries of $A^{-1}$. In many examples this $\epsilon$ actually equals $\epsilon_r$ after the computation of the first or first few rows. Therefore we will often
find quickly the next row of $A^{-1}$ already in (1), because we find a $v_i = 0$ such that the sequence of $y_i$ becomes constant ($=y$).

\subsection{\textcolor{Chapter }{Rank of Integer Matrix}}\label{Ssect-rankintmat}
\logpage{[ 1, 7, 1 ]}
\hyperdef{L}{X791ED7D97F87FDFD}{}
{
  The following strategy has shown to be useful in proving that some very big
integer matrix is not invertible.

\begin{itemize}
\item Check the rank modulo some small primes, say with \texttt{RankMod} (\ref{RankMod}).
\item If the rank seems less than the number of rows choose a prime $p$, a collection of lines which is linearly independent modulo $p$, and another line linearly dependend on these. Guess that this last line is
also linearly dependend on the chosen collection over the rational numbers
(maybe check modulo several small primes).
\item Find columns of the collection of lines which give an invertible matrix modulo
some prime.
\item Then use \texttt{RationalSolutionIntMat} (\ref{RationalSolutionIntMat}) with the invertible submatrix and corresponding entries of the linearly
dependend row to prove this.
\end{itemize}
Guessing the rank of a matrix from the rank modulo several primes, chosing a
maximal set of lines which are linearly independent modulo some primes, and
using \texttt{RationalSolutionIntMat} (\ref{RationalSolutionIntMat}) with the remaining lines, one may also find the exact rank of a huge integer
matrix.

}

}

}

\def\bibname{References\logpage{[ "Bib", 0, 0 ]}
\hyperdef{L}{X7A6F98FD85F02BFE}{}
}

\bibliographystyle{alpha}
\bibliography{edim}

\addcontentsline{toc}{chapter}{References}

\def\indexname{Index\logpage{[ "Ind", 0, 0 ]}
\hyperdef{L}{X83A0356F839C696F}{}
}

\cleardoublepage
\phantomsection
\addcontentsline{toc}{chapter}{Index}

\printindex

\newpage
\immediate\write\pagenrlog{["End"], \arabic{page}];}
\immediate\closeout\pagenrlog
\end{document}

quality100%

¤ Dauer der Verarbeitung: 0.20 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.