Help with a System of linear inequalities (with 12 variables)

Hi there.

I'm kind of new to MatLab and i'm trying to solve a Linear Algebra problem for my class of Linear Algebra of the course of Physics. Also, my first language is portuguese so forgive me for my not-so-perfect english.

I have a (solved) linear system of 7 equations and 12 variables (A, B, C, D, E, F, G, H, I, J, K, L) that is the following:

A = 33 - K - L

B = 1 + F - J

C = -15 - F + J + K + L

D = 15 + H - K

E = 16 - F - H + J + K

G = 34 - H - J - L

I = 18 - J - K

Note: I'm using letters (A, B, ..., L) instead of X1, X2, ..., X12 because it's easier to write it like this here and because I don't know if the Xn notation is allowed on Maple (i don't think so).

So, the system is possible but undetermined (with 5 degrees of freedom), being F, H, J, K and L the free variables.

Until here, everything's fine. The problem arises when the professor asks us for every solution of the system that satisfies the condition that all the variables (form A to L) are positive integers (A, B, C, D, E, F, G, H, I, J, K, L ϵ IN → natural numbers).

From my understanding, that gives rise to a system of linear inequalities with 12 variables and the following inequalities:

A = 33 - K - L > 0;

B = 1 + F - J > 0;

C = -15 - F + J + K + L > 0

D = 15 + H - K > 0

E = 16 - F - H + J + K > 0

G = 34 - H - J - L > 0

I = 18 - J - K > 0

F > 0

H > 0

J > 0

K > 0

L > 0 (and A,B,C,D,E,F,G,H,I,J,K,L ϵ IN)

After some research, i found that a possible way to solve this type of system of linear inequalities is trough a method of elimination (analog to Gauss-Jordan's elimination method for systems of linear equations) named Fourier-Motzkin. But it's hardwork and i wanted to do it on the computer. Is there a simple way to do it on MatLab?

I really need help solving this as the professor told us that the first one to solve it would win a book, hehe.

I would really apreciate an answer, as my only goal as a future physicist is to unveil the secrets of the Cosmos to us all.

Thank you again.

Miguel Jesus

Answer 1

[Alberto]

There is a simple way to solve the linear system of equalities, instead of using inequalities. You are trying to solve what is called Diophantine Linear System. Your system has to verifies some conditions so there exists integer (not necessary natural number) solutions.

Diophantine equation

Answer 2

[Roger Stafford]

I can give you one hint. Consider one of the equations, say, the last one:

   I = 18 - J - K

We know that the sum J+K cannot exceed 17, so I can envision the first two of five nested for-loops being like this:

   for J = 1:16
     for K = 1:1?-J

Using some of the other equations you can devise further for-loops inside these that take advantage of given values of J and K. Inside all five of them you can test all the remaining equations. Does that get you started? Maybe in the process you will think of something more elegant than this brute force method.