Let's consider two non-singular integer matrices $A,B \in\mathbb{Z}^{n\times n}$. I want a test to check if $A\times B^{-1}$ is integral (or no denominators). I am referring the unimodular certification paper by Storjohann. The inverse of a matrix $M$ can be written as a $x$-adic expansion: $$M^{-1}=c_0+c_1x+ c_2x^2+\cdots $$ If the matrix $M$ is unimodular, the $x$-adic expansion is finite and Storjohann provides a fast algorithm to check this. (Here $x\in \mathbb{Z}_{>2}$ is relatively prime to determinant of $M$). My approach was: I computed few $x$-adic terms of $B^{-1}$. Say: $B^{-1}=b_0+b_1x+\cdots$. I can write matrix $A$ as a finite $x$-adic expansion. Let $A=a_0+a_1x+\cdots +a_m+x^m$. Similarly, if $A\times B^{-1}$ is integral, I should be able to write it as a finite $x$-adic expansion. Hence, I checked if $a_0 \times b_i$ (or $a_j\times b_i$) becomes zero at some point. I test for some examples (for matrices over Number fields), but it didn't work. Is there any problem with the theory? or Can someone suggest me a way to certify integrality of the product $A\times B^{-1}$.
3
-
3$\begingroup$ This question is likelier to get an answer if you get more specific to the paper you are referring (which section? which criterion?) and explain what $x$ is (a big prime?). $\endgroup$– darij grinbergCommented May 21, 2020 at 22:19
-
$\begingroup$ My first attempt is to try for linear lifting section 2.1. Linear lifting algorithm is similar to the Dixon algorithm in paper :Exact Solution of Linear Equations §link.springer.com/article/10.1007/BF01459082§ for linear systems solving: $Ax=I$ taking RHS matrix $I$ to be the identity matrix. In this case $x$ is a prime or anything which does not divide Determinant of $A$. When it comes to the fast algorithm Double-plus-one Section 3, $x$ should be large enough. $x>max{10000, 3.61 n^2[A]} $, maximum entry =[A] $\endgroup$– studentCommented May 21, 2020 at 23:11
-
4$\begingroup$ In "the inverse of a matrix $M$ can be written as a[n] $x$-adic expansion", what is $x$? $\endgroup$– LSpiceCommented May 23, 2020 at 2:47
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
I considered $x$-adic expansions for $B^{-1}$ and $A$ separately and try to check whether product of terms becomes zero. It is not possible to test integrality of the product $AB^{-1}$ in this way as the series ($x$-adic expansion) grows (diverge) when B is not unimodular. Hence, I applied Dixon's algorithm to solve the linear system $yB=A$. This will compute the $x$-adic expansion of $AB^{-1}$ directly. Hence, I can check if this expansion becomes finite. Now, the next step is to modify "fast-Double-plus-One algorithm" to achieve this certification.