# Solving a system of linear equations over the integers

I have a matrix with integral entries $A$ and integer vector $b$, and want to determine if there is exactly one vector $x$ such that $Ax=b$. $A$ is rectangular, and I know there always is a solution.

Now, Sage has a wonderful function to calculate this: solve_right. But when the input matrix and vector have dimensions around $1600$ this function eats up a lot of time and memory: 5 gigabytes and a lot of time before I finally killed it. Using the real field doesn't work either because Sage only solves linear equations with square matrices over the real field.

Are there any approaches to the above problem? Perhaps I can figure out some bounds on coefficients that would let me work over a large finite field.

• Usually one can compute the null space of A to determine if it has a nonzero vector. Since your A has integer entries, the null space will too. Is there a reason this will not help you? Gerhard "This Is A Singular Problem?" Paseman, 2018.03.05. Mar 5, 2018 at 22:03
• Re "Perhaps I can figure out some bounds on coefficients that would let me work over a large finite field.": when I was working on similar problems I thought [I. Borosh, M. Flahive, D. Rubin, B. Treybig, A sharp bound for solutions of linear Diophantine equations, Proc. Amer. Math. Soc. 105 (1989), 844-846] to be the best result in this regard (though there might of course be more recent and better tools available). Mar 5, 2018 at 22:05
• Isn’t this equivalent to asking whether there is a non-zero vector $x$ such that $Ax=0$? (If $x_1$ and $x_2$ are solutions to $Ax=b$ then $x_1-x_2$ is a solution to $Ax=0$, and conversely if $Ax=b$ and $Ax'=0$ then $A(x+kx')=b$ for all $k\in\mathbb{Z}$.) Mar 5, 2018 at 22:59
• Plus finding one solution. The challenge is really the efficiency. Mar 5, 2018 at 23:50
• Ah, I didn’t realise you need to find $x$ as well as determining if it’s unique. In that case the following is less relevant. But anyway: the .elementary_divisors() function seems to be faster than .solve_right(). But it’s probably still prohibitively slow at your dimensions. Mar 5, 2018 at 23:56

To make sure I understand: you have an $m \times n$ matrix and vector in $\mathbb{Z}^n.$ Is the system a priori over- or under-determined? The former case is a little easier than the latter, but in any case, your problem is the so-called intermediate expression swell, and the easiest way to get around it is to solve it mod many primes and then chinese-remainder the results together. You don't actually need an a priori bound - you just find your solution mod $2, 3, \cdots,$ and keep chinese remaindering, until the result is actually a solution of the system (actually, the faster way is to work modulo as big primes as possible, so 32 bits primes, since the arithmetic is no slower than for small primes, and you will need fewer of them).