Solve underdetermined system of equations in matlab

Question

I have a system of under-determined linear equations Ax = b (i.e. more unknowns than equations) that I would like so solve in matlab.

I know that this would usually mean an infinite number of solutions, but I also know the solutions should be positive integers and less than a certain number. Can I find all the solutions that meet those additional requirements?

This problem come from having an unknown matrix where I know the sum of each row and column.

e.g. unknown matrix to find

0 3 2 0
0 2 4 1
2 1 0 0

Row sums known

5
7
3

Column Sums know

2 6 6 1

I've tried the lsqnonneg(A,b) function which gives only one valid solution

0 0 5 0
0 6 0 1
2 0 1 0

I'm pretty sure there will usually be exponentially-many such solutions. — user380772

percusse percusse · Accepted Answer · 2016-09-06T14:55:18

What you have is often called integer-linear programming and it is known to be NP-hard (which means don't hold your breath until a solution comes out).

If you want to solve it without the integerness, you have a linear program and hence can use linprog. If you think of your unknown matrix as vector of unknown entries then column sum is just

col_sum = kron(eye(4),[1,1,1]);

col_sum =

     1     1     1     0     0     0     0     0     0     0     0     0
     0     0     0     1     1     1     0     0     0     0     0     0
     0     0     0     0     0     0     1     1     1     0     0     0
     0     0     0     0     0     0     0     0     0     1     1     1

Similarly, row sum is

row_sum = repmat(eye(3),1,4);

row_sum =

     1     0     0     1     0     0     1     0     0     1     0     0
     0     1     0     0     1     0     0     1     0     0     1     0
     0     0     1     0     0     1     0     0     1     0     0     1

These are your equality constraints also you have the inequality constraints but only to bound the unknown values. linprog can bound them as extra arguments. However you don't have an objective function which you can make up something like sum of all unknowns minimized or one of them or any other linear objective would do or you can leave it empty and you get any feasible result.

Aeq = [col_sum;row_sum]
beq = [2 6 6 1 5 7 3]';

X = linprog([],[],[],Aeq,beq,zeros(12,1),10*ones(12,1))% 0 <= vars <= 10

X = reshape(X,3,4)

X =

    0.6550    2.0160    2.0160    0.3130
    1.1192    2.5982    2.5982    0.6845
    0.2258    1.3859    1.3859    0.0025


>> sum(X,1)

ans =

    2.0000    6.0000    6.0000    1.0000

>> sum(X,2)

ans =

    5.0000
    7.0000
    3.0000

If you have certain entries that are guaranteed to be zero etc. Then it might be possible that all solutions are forced to be integers. Otherwise you need to have nonconvex specific integer programming solvers for example given here

Solve underdetermined system of equations in matlab

2 Answers