2
$\begingroup$

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
$\endgroup$
  • $\begingroup$ What about your system guarantees that the entries $x$ are integers? $\endgroup$ – Dan May 14 '12 at 2:38
  • $\begingroup$ It's a requirement I imposed upon the solution. Even if no such solution exists I still need to only consider the integers. $\endgroup$ – user490735 May 14 '12 at 2:57
  • 1
    $\begingroup$ 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)? $\endgroup$ – Dan May 14 '12 at 3:06
  • $\begingroup$ Yes, because I know there is a solution in the reals. $\endgroup$ – user490735 May 14 '12 at 3:35
  • $\begingroup$ 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. $\endgroup$ – Dan May 14 '12 at 8:42
6
$\begingroup$

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.

$\endgroup$

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.