Inequality matrix algebra?

mikau · 2008-05-01 06:39:55

When I was taking linear algebra, I started to wonder if you could develop a direct method to solve systems of inequalities, and determine if a solution exists, and what restrictions there were. I did manage to come up with a method of solving using matrices. I was thinking about posting about it, but I'm not sure if its already been invented and everyone here knows about it.

I'm sure someones come up with a way, but has anyone here ever heard of using matrices to solve systems of inequalities?

Last edited by mikau (2008-05-01 06:40:52)

Dragonshade · 2008-05-01 07:06:22

nope, but I guess it would be under the same principle as solving equalities?

mathsyperson · 2008-05-01 07:10:07

I might be being really stupid here, but how do you 'solve' systems of inequalities?
I'm assuming you're basically talking about systems of equations, but with the = replaced by another relation.

eg.

x+y = 2
x-y = 2

becomes

x+y > 2
x-y < 2, for example.

It's easy enough to solve the first system and give a concise, useful answer (x=2, y=0).
What would the equivalent 'solution' be in the inequality version?

mikau · 2008-05-01 07:17:59

well for now, lets just worry about the following question

how can we show that a solution exists?

my method essentially deals with that. I THINK you can use it to work backwards and find the exact restrictions, but i have to recall how i did this. Its been several months since i played with this.

nope, but I guess it would be under the same principle as solving equalities?

not really. At least not my method. In normal matrix algebra, for a system of equations, if we have two rows, like
1 2 3
1 4 1

we subtract one row from the other to reduce it to

1 2 3
0 2 -2

and again to get

1 0 5
0 2 -2

problem though. If we are dealing with inequalities, such as
x + y < 5 and
x - 2y < 2

you cannot subtract one from the other, you can only add. So we cannot apply the same method to reduce it row by row.

Last edited by mikau (2008-05-01 07:22:50)

TheDude · 2008-05-01 07:19:09

x + y > 2, x - y < 2
x > 2 - y, x < 2 + y
->
2 - y < 2 + y
->
0 < 2y
->
y > 0

The 'solution' would be y > 0, 2 - y < x < 2 + y (alternatively, |x - 2| < y). I've never heard of such a thing mikau, would you mind posting your method?

Last edited by TheDude (2008-05-01 07:27:10)

mikau · 2008-05-01 07:26:42

like I said, my solution deals primarily with, does a solution exist? I don't exactly remember to what extent it shows you the actual solutions, I think it does. But I don't remember how far it goes.

My method is complicated, and I'll have to remember as I go along. I'll start working on the post now.

mikau · 2008-05-01 07:39:22

Okay, first for this discussion I'm going to be dealing with 'less than or equal to, greater than or equal to' I think you can also apply the same reasoning for > and < but for now, i'm dealing only with ≤ and ≥

I'm going to post these in parts, as I work them out.

part 1. matrix representation

the first thing is how to represent a system of inequalities as a matrix. Simple, put all variables on the left side, the constants on the right side, and multiply each equation by -1 in order to set all inequality signs in the same direction, for the sake of consistency, always set it to '≤'

so the matrix

would represent:

x + 4y - 3z ≤ 2
5x + 2y + yz ≤ 5
-8x + 4y - 2z ≤ -6

simple, right?

Now here are some algebra rules for the matrix. We may, of course,
swap two rows.
We may
multiply a row by a positive scaler,
and we can
add two rows together. (not subtract)

Last edited by mikau (2008-05-01 07:42:23)

mikau · 2008-05-01 08:23:30

part 2.

In otherwords, where the coefficient of one of the variables is equal and opposite in sign, they may be added together, and the resulting inequality has a solution if and only if the first two have solutions.

To show this, suppose the first two inequalities have a solution (x, y, z), then:

rearranging:

we therefore, must have that for these solution values,

rearranging

which implies the sum of the inequalities also has a solution.

Now suppose there is no point (x, y, z) such that

are both satisfied, and there is a point (x, y, z) such that

has a solution.

rearranging the latter inequality, for the solution point

now suppose we take a value that lies between these two by letting u equal the average of the values on either side. we therefore have:

or

and

rearranging we get

and

now suppose we chose the value x such that u = ax, (x = a/u)

we therefore have

and

a contradiction. Thus we are finished with the proof.

Last edited by mikau (2008-05-01 08:56:00)

Ricky · 2008-05-01 09:31:59

Just wanted to add, part of algebraic geometry is the study of solving systems of polynomial.s

mikau · 2008-05-01 09:35:35

sweet!

Anyway, I'm working on the next part of the discussion, it involves another proof, and i can't remember exactly how I did it.

mathsyperson · 2008-05-01 11:21:46

Can't you prove that theorem with a one-liner?
You've said that adding of inequalities is allowed, so add them to get:
ax + by + cz - ax + dy + ez ≤ k+j
(b+d)y + (c+e)z ≤ k+j

Also, I'm pretty sure the implication only works that way. Since x isn't involved in the right side, you can choose values of y and z to make the right side true and then a value of x to make sure the left side gets mucked up.

mikau · 2008-05-01 12:42:53

well one way its easy to prove. But showing the implication works the other way puts a restriction on the solution sets. I had a proof that showed how this could be used for reduction, but i can't remember exactly what it was, or how i proved it. argh!

I'll keep thinking about it.

Math Is Fun Forum

#1 2008-05-01 06:39:55

Inequality matrix algebra?

#2 2008-05-01 07:06:22

Re: Inequality matrix algebra?

#3 2008-05-01 07:10:07

Re: Inequality matrix algebra?

#4 2008-05-01 07:17:59

Re: Inequality matrix algebra?

#5 2008-05-01 07:19:09

Re: Inequality matrix algebra?

#6 2008-05-01 07:26:42

Re: Inequality matrix algebra?

#7 2008-05-01 07:39:22

Re: Inequality matrix algebra?

#8 2008-05-01 08:23:30

Re: Inequality matrix algebra?

#9 2008-05-01 09:31:59

Re: Inequality matrix algebra?

#10 2008-05-01 09:35:35

Re: Inequality matrix algebra?

#11 2008-05-01 11:21:46

Re: Inequality matrix algebra?

#12 2008-05-01 12:42:53

Re: Inequality matrix algebra?

Board footer