Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

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

mikau
Member
Registered: 2005-08-22
Posts: 1,504

Inequality matrix algebra?

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)


A logarithm is just a misspelled algorithm.

Offline

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

Dragonshade
Member
Registered: 2008-01-16
Posts: 147

Re: Inequality matrix algebra?

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

Offline

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

mathsyperson
Moderator
Registered: 2005-06-22
Posts: 4,900

Re: Inequality matrix algebra?

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?


Why did the vector cross the road?
It wanted to be normal.

Offline

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

mikau
Member
Registered: 2005-08-22
Posts: 1,504

Re: Inequality matrix algebra?

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)


A logarithm is just a misspelled algorithm.

Offline

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

TheDude
Member
Registered: 2007-10-23
Posts: 361

Re: Inequality matrix algebra?

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)


Wrap it in bacon

Offline

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

mikau
Member
Registered: 2005-08-22
Posts: 1,504

Re: Inequality matrix algebra?

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.


A logarithm is just a misspelled algorithm.

Offline

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

mikau
Member
Registered: 2005-08-22
Posts: 1,504

Re: Inequality matrix algebra?

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)


A logarithm is just a misspelled algorithm.

Offline

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

mikau
Member
Registered: 2005-08-22
Posts: 1,504

Re: Inequality matrix algebra?

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)


A logarithm is just a misspelled algorithm.

Offline

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

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Inequality matrix algebra?

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


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

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

mikau
Member
Registered: 2005-08-22
Posts: 1,504

Re: Inequality matrix algebra?

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.


A logarithm is just a misspelled algorithm.

Offline

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

mathsyperson
Moderator
Registered: 2005-06-22
Posts: 4,900

Re: Inequality matrix algebra?

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.


Why did the vector cross the road?
It wanted to be normal.

Offline

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

mikau
Member
Registered: 2005-08-22
Posts: 1,504

Re: Inequality matrix algebra?

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.


A logarithm is just a misspelled algorithm.

Offline

Board footer

Powered by FluxBB