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}$.

  • $\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 grinberg May 21 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$ – student May 21 at 23:11
  • $\begingroup$ In "the inverse of a matrix $M$ can be written as a[n] $x$-adic expansion", what is $x$? $\endgroup$ – LSpice May 23 at 2:47

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.