Thread Subject:

Finding all the integer solutions to an underdetermined system

Hello,

I have a linear system A*x = b, where A has more columns than it has rows, size(A) = [3,4]. I can find a solution to this underdetermined system using either backslash or linprog (I used linprog as I wanted to constrain the solutions to be between a certain range), however I now need to find all the solutions.
The vector x actually represents 4 signals each having 12 bit resolution so there are a finite number of solutions. I believe from reading previous posts the best way to deal with this is using integers (so in my case 0-4095, also the range of possible values in x) and finding the number of integer solutions (which may require some form of Diophantine equation..?). I came across intlin written by Bruno but that appears to only deal with cases where b is a scaler (in my case: size(b) = [3,1]) .

Here is an example:
A =
  1.0e+004 *
    0.9021 1.2608 0.3340 0.4806
    0.3887 0.8936 1.6628 0.0945
    0.0003 0.0017 0.5049 2.6343

b =
  1.0e+007 *
    3.6942
    1.5916
    0.0011

x determined with linprog
x =
1.0e+003 *
    4.0950
    0.0000
    0.0000
    0.0000

In this particular case of b there is probably only one solution (as it at the extreme end of my signal gamut), I have however a range of b values where there are multiple solutions.
So I'm wondering how to determine all the possible solutions given a particular value of b (x with values >0 and <= 4095). Any help in this matter, such as pointers to relevant threads (even though I have gone through them) or pointers to relevant functions or text (to get a handle on this problem), would be greatly appreciated.

Cheers,

Gary

"Gary B" wrote in message <iohie8$rod$1@ginger.mathworks.com>...
> ........
> I have a linear system A*x = b, where A has more columns than it has rows, size(A) = [3,4]. I can find a solution to this underdetermined system using either backslash or linprog (I used linprog as I wanted to constrain the solutions to be between a certain range), however I now need to find all the solutions.
> .........
- - - - - - - - -
  Forget for a moment that you are seeking solutions with "12 bit resolution" but are dealing with numbers of infinite precision in the real domain. Suppose you have found some vector solution x0 to A*x0 = b. Now carry out a singular value decomposition on A.

 [U,S,V] = svd(A);

so that A = U*S*V' (all with hypothetically infinite precision.) The last column of the 3 x 4 diagonal matrix S must be all zero and therefore the last column eigenvector of the 4 x 4 matrix V, call it x1, or any scalar multiple t thereof, will be a solution to A*x = 0. Hence you now have a general solution to A*x = b which is x = x0+t*x1 for any scalar t. In other words it is a certain "line" in four dimensional space parallel to the x1 vector running through the point x0.

  There are clearly infinitely many possible points along this line which satisfy your three equations. Most probably none of these will be either all integers or even have a precisely 12 bit resolution. I claim therefore that you should be seeking vectors for x in which its four elements do satisfy your requirement (i.e., integers or 12-bit fractions and within some allowed ranges) and which (orthogonally?) depart from the above line by no more than some specified tolerance which you decide upon. The greater the tolerance you select, the larger the number of possible solutions. Note that the special solution x0 itself may not need to satisfy your requirements, but only points somewhere along the given line through x0.

  If you were in two dimensions instead of four, picture yourself drawing a line on graph paper in which there was a grid of "acceptable" points, and you wish to determine all of these points which are sufficiently close to the line. That is the problem you face.

  I haven't solved your problem but hopefully this may help to shed a little light on its true nature (at least as I envision it.)

Roger Stafford

Thanks very much Roger, I used your approach, it worked great. I do understand the problem much better now as well.

Cheers,

Gary