# Integrality certification for product of two matrices $A B^{-1}$

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

• 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?). – darij grinberg May 21 at 22:19
• 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] – student May 21 at 23:11
• In "the inverse of a matrix $M$ can be written as a[n] $x$-adic expansion", what is $x$? – 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.