Take the 2-minute tour ×

I am trying find all solution to dependent system linear equation. Suppose that I have one solution to system linear equation. It's possible modify system linear equation to find other solutions?

EDIT: Thanks for replies.

I specify my equations, Ax = b. Matrix A is square integer matrix size 144. b is vector contains all-6 number. I am looking only 0-1 solution, i.e x=0 or x=1. Number of variables is 144. I found one solution from gurobi optimalization(find only one optimal solution), but I know that exists another solutions. I want to modify system of linear equation. Is it possible?

share|improve this question
What do you know about the general form of a solution to $Ax=b$? –  Dominique Mar 30 '13 at 13:58
You can find the kernel of your system i.e. the solutions to $Ax = 0$. Then with the solution you found ($x_0$) the general solution is $x_0 + \ker A$ –  Andre Mar 30 '13 at 14:03

1 Answer 1

up vote 0 down vote accepted

It depends on the size of the kernel, and whether the system in homogeneous or not. If you the system in homogeneous and the kernel's dimension is 1, then your one solution will suffice, as the rest are just multiples of that solution.

However, if the kernel's dimension is larger, you'll need more solutions, and any linear combination of them would be a solution as well.

If the system in inhomogeneous, a single solution together with all the solutions to the corresponding homogeneous system, should produce all solutions.

share|improve this answer

Your Answer


