# In Octave, how do I specify that the solution to a matrix equation should be over integers?

In Octave, how do I specify that the solution to a matrix equation should be over integers? I.e., Given matrix $A$, vectors $x$ and $b$; $Ax=b$. Find vector $x=A^{-1}b$ such that all its entries are integers. While I'm primarily concerned with Octave, your answer may alternatively consider Wolfram|Alpha, or any other software available with a free online interface. If discussing Wolfram|Alpha or other systems, please also explain how to load a sparse matrix, which is currently in row, col, value format (i.e., I would prefer to do minimal format conversions).

$A$, in sparse format (row, col, value):

1 1 1
2 1 1
3 2 1
4 3 1
5 3 1
6 4 1
7 4 1
8 4 1
9 5 1
10 5 1
11 6 1
12 6 1
13 7 1
14 9 1
15 9 1
16 10 1
17 11 1
18 12 1
19 12 1
20 13 1
21 13 1
22 14 1
23 14 1
24 14 1
25 15 1
26 15 1
27 16 1
28 17 1
29 17 1
30 17 1
31 18 1
32 19 1
33 20 1
34 20 1


Coefficients:

30
27
26
26
24
25
25
20
17
21
13
14
17
18
17
13
14
13
12
12
11
6
2
3
3
2
4
2
3
0
2
1
4
4

• What about your system guarantees that the entries $x$ are integers? – Dan May 14 '12 at 2:38
• It's a requirement I imposed upon the solution. Even if no such solution exists I still need to only consider the integers. – user490735 May 14 '12 at 2:57
• If no solution exists in the integers, it should just return "no solution" (as opposed to some integer $x$ that is as close as possible to the solution)? – Dan May 14 '12 at 3:06
• Yes, because I know there is a solution in the reals. – user490735 May 14 '12 at 3:35
• What I wanted to clarify was whether you wanted the vector of integers which minimized the residual, or just the actual solution if the entries are integers and "no solution" otherwise. – Dan May 14 '12 at 8:42

If $A$ is full-rank, there is only one solution to $Ax=b$, and it is either integer or not.
If $A$ is not full-rank, this problem starts to look like a search for least common multiples in the null space or integer programming.
This isn't something that a general numerical linear algebra solver like those in Octave will be able to do on its own. If your problem is large, you could try entering this as a feasibility problem into an integer programming solver like lpsolve or COIN-CBC. If $A$ is not so big or nearly full-rank, then you might try an eigenvalue decomposition and searching in the null space for the nearest set of integers.