1% generated by GAPDoc2LaTeX from XML source (Frank Luebeck) 2\documentclass[a4paper,11pt]{report} 3 4\usepackage[top=37mm,bottom=37mm,left=27mm,right=27mm]{geometry} 5\sloppy 6\pagestyle{myheadings} 7\usepackage{amssymb} 8\usepackage[latin1]{inputenc} 9\usepackage{makeidx} 10\makeindex 11\usepackage{color} 12\definecolor{FireBrick}{rgb}{0.5812,0.0074,0.0083} 13\definecolor{RoyalBlue}{rgb}{0.0236,0.0894,0.6179} 14\definecolor{RoyalGreen}{rgb}{0.0236,0.6179,0.0894} 15\definecolor{RoyalRed}{rgb}{0.6179,0.0236,0.0894} 16\definecolor{LightBlue}{rgb}{0.8544,0.9511,1.0000} 17\definecolor{Black}{rgb}{0.0,0.0,0.0} 18 19\definecolor{linkColor}{rgb}{0.0,0.0,0.554} 20\definecolor{citeColor}{rgb}{0.0,0.0,0.554} 21\definecolor{fileColor}{rgb}{0.0,0.0,0.554} 22\definecolor{urlColor}{rgb}{0.0,0.0,0.554} 23\definecolor{promptColor}{rgb}{0.0,0.0,0.589} 24\definecolor{brkpromptColor}{rgb}{0.589,0.0,0.0} 25\definecolor{gapinputColor}{rgb}{0.589,0.0,0.0} 26\definecolor{gapoutputColor}{rgb}{0.0,0.0,0.0} 27 28%% for a long time these were red and blue by default, 29%% now black, but keep variables to overwrite 30\definecolor{FuncColor}{rgb}{0.0,0.0,0.0} 31%% strange name because of pdflatex bug: 32\definecolor{Chapter }{rgb}{0.0,0.0,0.0} 33\definecolor{DarkOlive}{rgb}{0.1047,0.2412,0.0064} 34 35 36\usepackage{fancyvrb} 37 38\usepackage{mathptmx,helvet} 39\usepackage[T1]{fontenc} 40\usepackage{textcomp} 41 42 43\usepackage[ 44 pdftex=true, 45 bookmarks=true, 46 a4paper=true, 47 pdftitle={Written with GAPDoc}, 48 pdfcreator={LaTeX with hyperref package / GAPDoc}, 49 colorlinks=true, 50 backref=page, 51 breaklinks=true, 52 linkcolor=linkColor, 53 citecolor=citeColor, 54 filecolor=fileColor, 55 urlcolor=urlColor, 56 pdfpagemode={UseNone}, 57 ]{hyperref} 58 59\newcommand{\maintitlesize}{\fontsize{50}{55}\selectfont} 60 61% write page numbers to a .pnr log file for online help 62\newwrite\pagenrlog 63\immediate\openout\pagenrlog =\jobname.pnr 64\immediate\write\pagenrlog{PAGENRS := [} 65\newcommand{\logpage}[1]{\protect\write\pagenrlog{#1, \thepage,}} 66%% were never documented, give conflicts with some additional packages 67 68\newcommand{\GAP}{\textsf{GAP}} 69 70%% nicer description environments, allows long labels 71\usepackage{enumitem} 72\setdescription{style=nextline} 73 74%% depth of toc 75\setcounter{tocdepth}{1} 76 77 78 79 80 81%% command for ColorPrompt style examples 82\newcommand{\gapprompt}[1]{\color{promptColor}{\bfseries #1}} 83\newcommand{\gapbrkprompt}[1]{\color{brkpromptColor}{\bfseries #1}} 84\newcommand{\gapinput}[1]{\color{gapinputColor}{#1}} 85 86 87\begin{document} 88 89\logpage{[ 0, 0, 0 ]} 90\begin{titlepage} 91\mbox{}\vfill 92 93\begin{center}{\maintitlesize \textbf{\textsf{EDIM}\mbox{}}}\\ 94\vfill 95 96\hypersetup{pdftitle=\textsf{EDIM}} 97\markright{\scriptsize \mbox{}\hfill \textsf{EDIM} \hfill\mbox{}} 98{\Huge \textbf{Elementary Divisors and Integer Matrices\mbox{}}}\\ 99\vfill 100 101{\Huge Version 1.3.5 \mbox{}}\\[1cm] 102{August 2019\mbox{}}\\[1cm] 103\mbox{}\\[2cm] 104{\Large \textbf{Frank L{\"u}beck \mbox{}}}\\ 105\hypersetup{pdfauthor=Frank L{\"u}beck } 106\end{center}\vfill 107 108\mbox{}\\ 109{\mbox{}\\ 110\small \noindent \textbf{Frank L{\"u}beck } Email: \href{mailto://Frank.Luebeck@Math.RWTH-Aachen.De} {\texttt{Frank.Luebeck@Math.RWTH-Aachen.De}}\\ 111 Homepage: \href{http://www.math.rwth-aachen.de/~Frank.Luebeck} {\texttt{http://www.math.rwth-aachen.de/\texttt{\symbol{126}}Frank.Luebeck}}\\ 112 Address: \begin{minipage}[t]{8cm}\noindent 113 Lehrstuhl D f{\"u}r Mathematik RWTH Aachen Pontdriesch 14/16 52062 Aachen 114Germany \end{minipage} 115}\\ 116\end{titlepage} 117 118\newpage\setcounter{page}{2} 119{\small 120\section*{Copyright} 121\logpage{[ 0, 0, 1 ]} 122 \index{License} {\copyright} 2000-2018 by Frank L{\"u}beck 123 124 \textsf{EDIM} is free software; you can redistribute it and/or modify it under the terms of 125the \href{http://www.fsf.org/licenses/gpl.html} {GNU General Public License} as published by the Free Software Foundation; either version 2 of the License, 126or (at your option) any later version. \mbox{}}\\[1cm] 127\newpage 128 129\def\contentsname{Contents\logpage{[ 0, 0, 2 ]}} 130 131\tableofcontents 132\newpage 133 134 135\chapter{\textcolor{Chapter }{The \textsf{EDIM}-Package}}\label{Chap-EDIM} 136\logpage{[ 1, 0, 0 ]} 137\hyperdef{L}{X7AA826067CC8C395}{} 138{ 139 \index{\textsf{EDIM}} \emph{(Elementary Divisors and Integer Matrices, by Frank L{\"u}beck)} 140 141 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 142given 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})). 143 144 These functions were already applied to integer matrices of dimension greater 145than $11000$ (which had many non-trivial elementary divisors which were products of small 146primes). 147 148 Furthermore there are functions for finding the biggest elementary divisor of 149an invertible integer matrix and the inverse of a rational invertible matrix 150(see \texttt{ExponentSquareIntMatFullRank} (\ref{ExponentSquareIntMatFullRank}) and \texttt{InverseRatMat} (\ref{InverseRatMat})). These algorithms use $p$-adic approximations, explained in \ref{Sect-InvRatMatAlg}. 151 152 Finally we distribute implementations of some other algorithms for finding 153elementary 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 154(see \texttt{GcdexIntLLL} (\ref{GcdexIntLLL})) and for Hermite normal forms of integer matrices with (very nice) 155transforming matrices (see \texttt{HermiteIntMatLLL} (\ref{HermiteIntMatLLL})). 156 157 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 158mini-package. Also, I would like to hear about applications of this package. 159 160 Frank L{\"u}beck 161\section{\textcolor{Chapter }{Installation of the \textsf{EDIM} package}}\label{Sect-Install} 162\logpage{[ 1, 1, 0 ]} 163\hyperdef{L}{X84D3F5E77E3BF046}{} 164{ 165 To install this package first unpack it inside some GAP root directory in the 166subdirectory \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 167kernel function as well during installation, otherwise the function \texttt{ElementaryDivisorsPPartRkExpSmall} (\ref{ElementaryDivisorsPPartRkExpSmall}) will not be available. 168 169 To install the kernel function go to the directory \texttt{pkg/EDIM-...} to which the package was extracted and call 170 171 \texttt{/bin/sh ./configure [path]} 172 173 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. 174 175 If you have installed several GAP kernels repeat these two steps for each of 176them. You can run a test of the installation by typing \texttt{make test}. 177 178\subsection{\textcolor{Chapter }{InfoEDIM}} 179\logpage{[ 1, 1, 1 ]}\nobreak 180\hyperdef{L}{X7AF83FEC7CD0311C}{} 181{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{InfoEDIM\index{InfoEDIM@\texttt{InfoEDIM}} 182\label{InfoEDIM} 183}\hfill{\scriptsize (info class)}}\\ 184 185 186 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 187certain \textsf{EDIM}-functions. } 188 189 } 190 191 192\section{\textcolor{Chapter }{$p$-Parts of Elementary Divisors}}\label{Sect-PPElDiv} 193\logpage{[ 1, 2, 0 ]} 194\hyperdef{L}{X818BE04687230849}{} 195{ 196 Here we explain the main functions of the package. 197 198\subsection{\textcolor{Chapter }{ElementaryDivisorsPPartRk}} 199\logpage{[ 1, 2, 1 ]}\nobreak 200\hyperdef{L}{X813B0D73868CD751}{} 201{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ElementaryDivisorsPPartRk({\mdseries\slshape A, p[, rk]})\index{ElementaryDivisorsPPartRk@\texttt{ElementaryDivisorsPPartRk}} 202\label{ElementaryDivisorsPPartRk} 203}\hfill{\scriptsize (function)}}\\ 204\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ElementaryDivisorsPPartRkI({\mdseries\slshape A, p, rk})\index{ElementaryDivisorsPPartRkI@\texttt{ElementaryDivisorsPPartRkI}} 205\label{ElementaryDivisorsPPartRkI} 206}\hfill{\scriptsize (function)}}\\ 207\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ElementaryDivisorsPPartRkII({\mdseries\slshape A, p, rk})\index{ElementaryDivisorsPPartRkII@\texttt{ElementaryDivisorsPPartRkII}} 208\label{ElementaryDivisorsPPartRkII} 209}\hfill{\scriptsize (function)}}\\ 210\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ElementaryDivisorsPPartRkExp({\mdseries\slshape A, p, rk, exp})\index{ElementaryDivisorsPPartRkExp@\texttt{ElementaryDivisorsPPartRkExp}} 211\label{ElementaryDivisorsPPartRkExp} 212}\hfill{\scriptsize (function)}}\\ 213\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ElementaryDivisorsPPartRkExpSmall({\mdseries\slshape A, p, rk, exp, il})\index{ElementaryDivisorsPPartRkExpSmall@\texttt{ElementaryDivisorsPPartRkExpSmall}} 214\label{ElementaryDivisorsPPartRkExpSmall} 215}\hfill{\scriptsize (function)}}\\ 216 217 218 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). 219 220 The algorithms for these functions are described in \cite{L98}. 221 222 \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. 223 224 The first version of the command delegates its job to the fourth version by 225trying growing values for \mbox{\texttt{\mdseries\slshape exp}}, see below. 226 227 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 228entries during the computation can be much smaller. 229 230 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. 231 232 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}. 233 234 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 235directly 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. 236 237 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}. 238 239 This last form of the function was already succesfully applied to dense 240matrices of rank up to $11000$. 241 242 Note that you have to compile a file (see \ref{Sect-Install}) while installing this package, if you want to have this kernel function 243available. 244 245 246\begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example] 247 !gapprompt@gap>| !gapinput@ReadPackage("edim", "tst/mat");| 248 Reading 242x242 integer matrix 'mat' with elementary divisors 'eldiv'. 249 true 250 !gapprompt@gap>| !gapinput@ElementaryDivisorsPPartRkI(mat, 2, 242); time; # mat has full rank| 251 [ 94, 78, 69, 57, 23, 23, 9, 2, 2, 0 ] 252 490 253 !gapprompt@gap>| !gapinput@ElementaryDivisorsPPartRkExpSmall(mat, 2, 242, 10, 0); time;| 254 [ 94, 78, 69, 57, 23, 23, 9, 2, 2, 0 ] 255 10 256\end{Verbatim} 257 } 258 259 260 261\subsection{\textcolor{Chapter }{ElementaryDivisorsPPartHavasSterling}} 262\logpage{[ 1, 2, 2 ]}\nobreak 263\hyperdef{L}{X82EC4724865F4DF9}{} 264{\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}} 265\label{ElementaryDivisorsPPartHavasSterling} 266}\hfill{\scriptsize (function)}}\\ 267 268 269 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$. 270 271 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. 272 273 This is an implementation of the modular algorithm described in \cite{HS79}. 274 275 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 276pivot search. 277 278 279\begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example] 280 !gapprompt@gap>| !gapinput@ReadPackage("edim", "tst/mat");| 281 Reading 242x242 integer matrix 'mat' with elementary divisors 'eldiv'. 282 true 283 !gapprompt@gap>| !gapinput@ElementaryDivisorsPPartHavasSterling(mat, 2, 10); time;| 284 [ 94, 78, 69, 57, 23, 23, 9, 2, 2 ] 285 1260 286\end{Verbatim} 287 } 288 289 } 290 291 292\section{\textcolor{Chapter }{Inverse of Rational Matrices}}\label{Sect-InvRatMat} 293\logpage{[ 1, 3, 0 ]} 294\hyperdef{L}{X80FF39C07E03D7EF}{} 295{ 296 297 298\subsection{\textcolor{Chapter }{InverseRatMat}} 299\logpage{[ 1, 3, 1 ]}\nobreak 300\hyperdef{L}{X7A9656D47C4D2D16}{} 301{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{InverseRatMat({\mdseries\slshape A[, p]})\index{InverseRatMat@\texttt{InverseRatMat}} 302\label{InverseRatMat} 303}\hfill{\scriptsize (function)}}\\ 304 305 306 This function returns the inverse of an invertible matrix over the rational 307numbers. 308 309 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 310from their \mbox{\texttt{\mdseries\slshape p}}-adic approximations. See section \ref{Sect-InvRatMatAlg} for more details. 311 312 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)}.) 313 314 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. 315 316 } 317 318 319 320\subsection{\textcolor{Chapter }{RationalSolutionIntMat}} 321\logpage{[ 1, 3, 2 ]}\nobreak 322\hyperdef{L}{X8302B31E86B3AFDB}{} 323{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{RationalSolutionIntMat({\mdseries\slshape A, v[, p[, invA]]})\index{RationalSolutionIntMat@\texttt{RationalSolutionIntMat}} 324\label{RationalSolutionIntMat} 325}\hfill{\scriptsize (function)}}\\ 326 327 328 This function returns the solution $x$ of the system of linear equations $x \mbox{\texttt{\mdseries\slshape A}} = \mbox{\texttt{\mdseries\slshape v}}$. 329 330 Here, \mbox{\texttt{\mdseries\slshape A}} must be a matrix with integer entries which is invertible over the rationals 331and \mbox{\texttt{\mdseries\slshape v}} must be a vector with integer entries of the appropriate length. 332 333 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}$. 334 335 The solution is computed via $p$-adic approximation as explained in \ref{Sect-InvRatMatAlg}. 336 337 } 338 339 340 341\subsection{\textcolor{Chapter }{ExponentSquareIntMatFullRank}} 342\logpage{[ 1, 3, 3 ]}\nobreak 343\hyperdef{L}{X86DA61D978D2D889}{} 344{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ExponentSquareIntMatFullRank({\mdseries\slshape A[, p[, nr]]})\index{ExponentSquareIntMatFullRank@\texttt{ExponentSquareIntMatFullRank}} 345\label{ExponentSquareIntMatFullRank} 346}\hfill{\scriptsize (function)}}\\ 347 348 349 This function returns the biggest elementary divisor of a square integer 350matrix \mbox{\texttt{\mdseries\slshape A}} of full rank. 351 352 For such a matrix \mbox{\texttt{\mdseries\slshape A}} the least common multiple of the denominators of all entries of the inverse 353matrix $\mbox{\texttt{\mdseries\slshape A}}^{-1}$ is exactly the biggest elementary divisor of \mbox{\texttt{\mdseries\slshape A}}. 354 355 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 356return 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 357this is correct). 358 359 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. 360 361 362\begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example] 363 !gapprompt@gap>| !gapinput@ReadPackage("edim", "tst/mat");| 364 Reading 242x242 integer matrix 'mat' with elementary divisors 'eldiv'. 365 true 366 !gapprompt@gap>| !gapinput@inv := InverseRatMat(mat);; time; | 367 840 368 !gapprompt@gap>| !gapinput@ExponentSquareIntMatFullRank(mat, 101, 3); # same as without the `3'| 369 115200 370\end{Verbatim} 371 } 372 373 } 374 375 376\section{\textcolor{Chapter }{All Elementary Divisors Using p-adic Method}}\label{Sect-ElDivPad} 377\logpage{[ 1, 4, 0 ]} 378\hyperdef{L}{X7A6548FA7C837D27}{} 379{ 380 In the following two functions we put things together. In particular we handle 381the prime parts of the elementary divisors efficiently for primes appearing 382with low powers in the highest elementary divisor respectively determinant 383divisor. 384 385\subsection{\textcolor{Chapter }{ElementaryDivisorsSquareIntMatFullRank}} 386\logpage{[ 1, 4, 1 ]}\nobreak 387\hyperdef{L}{X7B6A3B8486872B0C}{} 388{\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}} 389\label{ElementaryDivisorsSquareIntMatFullRank} 390}\hfill{\scriptsize (function)}}\\ 391 392 393 This function returns a list of nonzero elementary divisors of an integer 394matrix \mbox{\texttt{\mdseries\slshape A}}. 395 396 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 397prime is automatically replaced by the next one. 398 399 The rest is done using \texttt{ElementaryDivisorsPPartRkExp} (\ref{ElementaryDivisorsPPartRkExp}) and \texttt{RankMod} (\ref{RankMod}). 400 401 The function fails if the biggest elementary divisor cannot be completely 402factored and the non-factored part is not a divisor of the biggest elementary 403divisor only. 404 405 Note that this function may for many matrices not be the best choice for 406computing all elementary divisors. You may first try the standard \textsf{GAP} library routines for Smith normal form instead of this function. Nevertheless 407remember \texttt{ElementaryDivisorsSquareIntMatFullRank} for hard and big examples. It is particularly good when the largest elementary 408divisor is a very small factor of the determinant. 409\begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example] 410 !gapprompt@gap>| !gapinput@Collected(ElementaryDivisorsSquareIntMatFullRank(mat)); | 411 [ [ 1, 49 ], [ 3, 99 ], [ 6, 7 ], [ 30, 9 ], [ 60, 9 ], [ 120, 2 ], 412 [ 360, 10 ], [ 720, 22 ], [ 3600, 12 ], [ 14400, 14 ], 413 [ 28800, 7 ], [ 115200, 2 ] ] 414 !gapprompt@gap>| !gapinput@time;| 415 860 416 !gapprompt@gap>| !gapinput@last2 = Collected(DiagonalOfMat(NormalFormIntMat(mat, 1).normal));| 417 true 418 !gapprompt@gap>| !gapinput@time;| 419 5170 420\end{Verbatim} 421 } 422 423 424 425\subsection{\textcolor{Chapter }{ElementaryDivisorsIntMatDeterminant}} 426\logpage{[ 1, 4, 2 ]}\nobreak 427\hyperdef{L}{X821E30477A5DCE68}{} 428{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{ElementaryDivisorsIntMatDeterminant({\mdseries\slshape A, det[, rk]})\index{ElementaryDivisorsIntMatDeterminant@\texttt{ElementaryDivisorsIntMatDeterminant}} 429\label{ElementaryDivisorsIntMatDeterminant} 430}\hfill{\scriptsize (function)}}\\ 431 432 433 This function returns a list of nonzero elementary divisors of an integer 434matrix \mbox{\texttt{\mdseries\slshape A}}. 435 436 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. 437 438 The argument \mbox{\texttt{\mdseries\slshape det}} can be given in the form of \texttt{Collected(FactorsInt(\mbox{\texttt{\mdseries\slshape det}}))}. 439 440 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.) 441 442 443\begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example] 444 !gapprompt@gap>| !gapinput@ReadPackage("edim", "tst/mat");| 445 Reading 242x242 integer matrix 'mat' with elementary divisors 'eldiv'. 446 true 447 !gapprompt@gap>| !gapinput@# not so good:| 448 !gapprompt@gap>| !gapinput@ElementaryDivisorsIntMatDeterminant(mat,Product(eldiv)) = | 449 !gapprompt@>| !gapinput@Concatenation([1..49]*0+1, eldiv); time;| 450 true 451 5490 452\end{Verbatim} 453 } 454 455 } 456 457 458\section{\textcolor{Chapter }{Gcd and Normal Forms Using LLL}}\label{Sect-NFIntMatLLL} 459\logpage{[ 1, 5, 0 ]} 460\hyperdef{L}{X788047737FA04422}{} 461{ 462 The \textsf{EDIM}-mini package also contains implementations of an extended Gcd-algorithm for 463integers and a Hermite and Smith normal form algorithm for integer matrices 464using LLL-techiques. They are well described in the paper \cite{HMM98} by Havas, Majewski and Matthews. 465 466 They are particularly useful if one wants to have the normal forms together 467with transforming matrices. These transforming matrices have spectacularly 468nice (i.e., ``small'') entries in cases of input matrices which are non-square or not of full rank 469(otherwise the transformation to the Hermite normal form is unique). 470 471 In detail: 472 473 474 475\subsection{\textcolor{Chapter }{GcdexIntLLL}} 476\logpage{[ 1, 5, 1 ]}\nobreak 477\hyperdef{L}{X799B1A5285D00859}{} 478{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{GcdexIntLLL({\mdseries\slshape n1, n2, ...})\index{GcdexIntLLL@\texttt{GcdexIntLLL}} 479\label{GcdexIntLLL} 480}\hfill{\scriptsize (function)}}\\ 481 482 483 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. 484\begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example] 485 !gapprompt@gap>| !gapinput@GcdexIntLLL( 517, 244, -304, -872, -286, 854, 866, 224, -765, -38);| 486 [ 1, [ 0, 0, 0, 0, 1, 0, 1, 1, 1, 1 ] ] 487\end{Verbatim} 488 } 489 490 491 492\subsection{\textcolor{Chapter }{HermiteIntMatLLL}} 493\logpage{[ 1, 5, 2 ]}\nobreak 494\hyperdef{L}{X7C6AE6777B72F9D2}{} 495{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{HermiteIntMatLLL({\mdseries\slshape A})\index{HermiteIntMatLLL@\texttt{HermiteIntMatLLL}} 496\label{HermiteIntMatLLL} 497}\hfill{\scriptsize (function)}}\\ 498 499 500 This returns the Hermite normal form of an integer matrix \mbox{\texttt{\mdseries\slshape A}} and uses the LLL-algorithm to avoid entry explosion. } 501 502 503 504\subsection{\textcolor{Chapter }{HermiteIntMatLLLTrans}} 505\logpage{[ 1, 5, 3 ]}\nobreak 506\hyperdef{L}{X862962B7878A284F}{} 507{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{HermiteIntMatLLLTrans({\mdseries\slshape A})\index{HermiteIntMatLLLTrans@\texttt{HermiteIntMatLLLTrans}} 508\label{HermiteIntMatLLLTrans} 509}\hfill{\scriptsize (function)}}\\ 510 511 512 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. 513\begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example] 514 !gapprompt@gap>| !gapinput@ReadPackage("edim", "tst/mat2");| 515 Reading 34x34 integer matrix 'mat2' with elementary divisors 'eldiv2'. 516 true 517 !gapprompt@gap>| !gapinput@tr := HermiteIntMatLLLTrans(mat2);; Maximum(List(Flat(tr[2]), AbsInt));| 518 606 519 !gapprompt@gap>| !gapinput@tr[2]*mat2 = tr[1]; | 520 true 521\end{Verbatim} 522 } 523 524 525 526\subsection{\textcolor{Chapter }{SmithIntMatLLL}} 527\logpage{[ 1, 5, 4 ]}\nobreak 528\hyperdef{L}{X8626F15179C09798}{} 529{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{SmithIntMatLLL({\mdseries\slshape A})\index{SmithIntMatLLL@\texttt{SmithIntMatLLL}} 530\label{SmithIntMatLLL} 531}\hfill{\scriptsize (function)}}\\ 532 533 534 This function returns the Smith normal form of an integer matrix \mbox{\texttt{\mdseries\slshape A}} using the LLL-algorithm to avoid entry explosion. } 535 536 537 538\subsection{\textcolor{Chapter }{SmithIntMatLLLTrans}} 539\logpage{[ 1, 5, 5 ]}\nobreak 540\hyperdef{L}{X86094B1B7C87EBF6}{} 541{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{SmithIntMatLLLTrans({\mdseries\slshape A})\index{SmithIntMatLLLTrans@\texttt{SmithIntMatLLLTrans}} 542\label{SmithIntMatLLLTrans} 543}\hfill{\scriptsize (function)}}\\ 544 545 546 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}}. 547 548 We apply the algorithm for Hermite normal form several times to get the Smith 549normal form, that is not in the paper \cite{HMM98}. The transforming matrices need not be as nice as for the Hermite normal 550form. 551 552 553\begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example] 554 !gapprompt@gap>| !gapinput@ReadPackage("edim", "tst/mat2");| 555 Reading 34x34 integer matrix 'mat2' with elementary divisors 'eldiv2'. 556 true 557 !gapprompt@gap>| !gapinput@tr := SmithIntMatLLLTrans(mat2);;| 558 !gapprompt@gap>| !gapinput@tr[2] * mat2 * tr[3] = tr[1]; | 559 true 560\end{Verbatim} 561 } 562 563 } 564 565 566\section{\textcolor{Chapter }{Utility Functions from the \textsf{EDIM}-package}}\label{Sect-Util} 567\logpage{[ 1, 6, 0 ]} 568\hyperdef{L}{X832582857EB36B23}{} 569{ 570 571 572\subsection{\textcolor{Chapter }{RatNumberFromModular}} 573\logpage{[ 1, 6, 1 ]}\nobreak 574\hyperdef{L}{X7EC844F97C469C03}{} 575{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{RatNumberFromModular({\mdseries\slshape n, k, l, x})\index{RatNumberFromModular@\texttt{RatNumberFromModular}} 576\label{RatNumberFromModular} 577}\hfill{\scriptsize (function)}}\\ 578 579 580 This function returns $r/s = \mbox{\texttt{\mdseries\slshape x}} \pmod{\mbox{\texttt{\mdseries\slshape n}}}$, if it exists. More precisely: 581 582 \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. 583 584 } 585 586 587 588\subsection{\textcolor{Chapter }{InverseIntMatMod}} 589\logpage{[ 1, 6, 2 ]}\nobreak 590\hyperdef{L}{X78518E1D81435762}{} 591{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{InverseIntMatMod({\mdseries\slshape A, p})\index{InverseIntMatMod@\texttt{InverseIntMatMod}} 592\label{InverseIntMatMod} 593}\hfill{\scriptsize (function)}}\\ 594 595 596 This function returns an inverse matrix modulo a prime \mbox{\texttt{\mdseries\slshape p}} or \texttt{fail}. More precisely: 597 598 \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. 599 600 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. } 601 602 603 604\subsection{\textcolor{Chapter }{HadamardBoundIntMat}} 605\logpage{[ 1, 6, 3 ]}\nobreak 606\hyperdef{L}{X7CDF3D2081207080}{} 607{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{HadamardBoundIntMat({\mdseries\slshape A})\index{HadamardBoundIntMat@\texttt{HadamardBoundIntMat}} 608\label{HadamardBoundIntMat} 609}\hfill{\scriptsize (function)}}\\ 610 611 612 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}}. } 613 614 615 616\subsection{\textcolor{Chapter }{CheapFactorsInt}} 617\logpage{[ 1, 6, 4 ]}\nobreak 618\hyperdef{L}{X7BAB977C7EB05067}{} 619{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{CheapFactorsInt({\mdseries\slshape n[, nr]})\index{CheapFactorsInt@\texttt{CheapFactorsInt}} 620\label{CheapFactorsInt} 621}\hfill{\scriptsize (function)}}\\ 622 623 624 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). 625 626 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. 627 628 } 629 630 631 632\subsection{\textcolor{Chapter }{RankMod}} 633\logpage{[ 1, 6, 5 ]}\nobreak 634\hyperdef{L}{X8312EDA78209B4EA}{} 635{\noindent\textcolor{FuncColor}{$\triangleright$\enspace\texttt{RankMod({\mdseries\slshape A, p})\index{RankMod@\texttt{RankMod}} 636\label{RankMod} 637}\hfill{\scriptsize (function)}}\\ 638 639 640 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 641integer, then this is the rank of \mbox{\texttt{\mdseries\slshape A}} for all prime divisors of \mbox{\texttt{\mdseries\slshape p}}. 642 643 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, 644rk{\textunderscore}2], ...]}. 645 646 The idea to make this function useful for non primes was to use it with large 647factors of the biggest elementary divisor of \mbox{\texttt{\mdseries\slshape A}} whose prime factorization cannot be found easily. 648 649 650\begin{Verbatim}[commandchars=!@|,fontsize=\small,frame=single,label=Example] 651 !gapprompt@gap>| !gapinput@ReadPackage("edim", "tst/mat");| 652 Reading 242x242 integer matrix 'mat' with elementary divisors 'eldiv'. 653 true 654 !gapprompt@gap>| !gapinput@RankMod(mat, 5);| 655 155 656 !gapprompt@gap>| !gapinput@RankMod(mat, (2*79*4001));| 657 [ [ 2, 148 ], [ 79, 242 ], [ 4001, 242 ] ] 658\end{Verbatim} 659 } 660 661 } 662 663 664\section{\textcolor{Chapter }{InverseRatMat - the Algorithm}}\label{Sect-InvRatMatAlg} 665\logpage{[ 1, 7, 0 ]} 666\hyperdef{L}{X83FD1AAB7EB2E934}{} 667{ 668 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 669John Cannon for pointing out that the basic idea already appeared in the paper \cite{D82} of Dixon. 670 671 Let $A$ be an invertible matrix over the rational numbers. By multiplying with a 672constant we may assume that its entries are in fact integers. 673 674 (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.) 675 676 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})$. 677 678 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$. 679 680 (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]$. 681 682 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$. 683 684 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 < 685\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$). 686 687 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. 688 689 (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 690entries of $y$ it is clear from (2) that we will find $y$ from $y_i$ if $l^i > 2 \mu^2$. 691 692 (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 693find 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$). 694 695 696\subsection{\textcolor{Chapter }{Rank of Integer Matrix}}\label{Ssect-rankintmat} 697\logpage{[ 1, 7, 1 ]} 698\hyperdef{L}{X791ED7D97F87FDFD}{} 699{ 700 The following strategy has shown to be useful in proving that some very big 701integer matrix is not invertible. 702 703 704\begin{itemize} 705\item Check the rank modulo some small primes, say with \texttt{RankMod} (\ref{RankMod}). 706\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 707also linearly dependend on the chosen collection over the rational numbers 708(maybe check modulo several small primes). 709\item Find columns of the collection of lines which give an invertible matrix modulo 710some prime. 711\item Then use \texttt{RationalSolutionIntMat} (\ref{RationalSolutionIntMat}) with the invertible submatrix and corresponding entries of the linearly 712dependend row to prove this. 713\end{itemize} 714 Guessing the rank of a matrix from the rank modulo several primes, chosing a 715maximal set of lines which are linearly independent modulo some primes, and 716using \texttt{RationalSolutionIntMat} (\ref{RationalSolutionIntMat}) with the remaining lines, one may also find the exact rank of a huge integer 717matrix. 718 719 } 720 721 } 722 723 } 724 725 \def\bibname{References\logpage{[ "Bib", 0, 0 ]} 726\hyperdef{L}{X7A6F98FD85F02BFE}{} 727} 728 729\bibliographystyle{alpha} 730\bibliography{edim} 731 732\addcontentsline{toc}{chapter}{References} 733 734\def\indexname{Index\logpage{[ "Ind", 0, 0 ]} 735\hyperdef{L}{X83A0356F839C696F}{} 736} 737 738\cleardoublepage 739\phantomsection 740\addcontentsline{toc}{chapter}{Index} 741 742 743\printindex 744 745\newpage 746\immediate\write\pagenrlog{["End"], \arabic{page}];} 747\immediate\closeout\pagenrlog 748\end{document} 749