Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Re: solve - integer solution

• To: mathgroup at smc.vnet.net
• Subject: [mg34160] Re: [mg34145] solve - integer solution
• From: Daniel Lichtblau <danl at wolfram.com>
• Date: Tue, 7 May 2002 03:53:56 -0400 (EDT)
• References: <200205060920.FAA20031@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

Chris Krook wrote:
> 
> Hello,
> I need to find an instance from the integers that satisfies the following
> equation:
> 
> {12 c[1, 0] + 12 c[2, 0] + 25 c[3, 0] - 50 c[3, 1] + 25 c[4, 0] - 50 c[4,
> 1],
>   12 c[1, 1] + 12 c[2, 1] + 10 c[3, 0] + 15 c[3, 1] + 10 c[4, 0] + 15 c[4,
> 1],
>    c[1, 0] + 2 c[2, 0], c[1, 1] + 2 c[2, 1], c[3, 0] - 5 c[4, 1],
>   c[3, 1] + c[4, 0] - c[4, 1]}=={0,0,0,0,0,0}
> 
> Using Solve doesn't give (explicit) integer solutions; Furthermore, since I
> only need an arbitrary integer-instance is there an easier way to obtain
> one? (if not, how can I adjust solve?)
> (this is small example; my actual problem involves much larger lists)
> 
> Thanks in advance,
> Chris

Since you are solving a homogeneous linear system, one method is to use
NullSpace to get rational solutions and then clear denominators if any
are present.

polys = {
	12*c[1,0] + 12*c[2,0] + 25*c[3,0] - 50*c[3,1] + 25*c[4,0] - 50*c[4,1],
	12*c[1,1] + 12*c[2,1] + 10*c[3,0] + 15*c[3,1] + 10*c[4,0] + 15*c[4,1],
	c[1,0] + 2*c[2,0],
	c[1,1] + 2*c[2,1],
	c[3,0] - 5*c[4,1],
	c[3,1] + c[4,0] - c[4,1]};

vars = Variables[polys];

<<LinearAlgebra`MatrixManipulation`

Out[36]//InputForm= 
{{{12, 0, 12, 0, 25, -50, 25, -50}, {0, 12, 0, 12, 10, 15, 10, 15}, 
  {1, 0, 2, 0, 0, 0, 0, 0}, {0, 1, 0, 2, 0, 0, 0, 0}, 
  {0, 0, 0, 0, 1, 0, 0, -5}, {0, 0, 0, 0, 0, 1, 1, -1}}, {0, 0, 0, 0, 0,
0}}

In[37]:= InputForm[sol = NullSpace[mat]]

Out[37]//InputForm= 
{{-50, -160, 25, 80, 60, 12, 0, 12}, {-150, 10, 75, -5, 0, -12, 12, 0}}

No denominators to clear. We check the solutions.

In[38]:= mat . sol[[1]]
Out[38]= {0, 0, 0, 0, 0, 0}

In[39]:= mat . sol[[2]]
Out[39]= {0, 0, 0, 0, 0, 0}


Daniel Lichtblau
Wolfram Research

• References:
  • solve - integer solution
    • From: "Chris Krook" <c.krook@student.tue.nl>