A linear programming, polyhedron and extreme points

[mertcan]

Hi,

First assume that there is a polyhedron P, where Ax<=b and x is free variable whose dimension is n. Besides, rank(A) = n. I really wonder if extreme points in a polyhedron can be linearly dependent? I used even ChatGPT, but it includes some shaky calculations while proofing. In short, if extreme points in a polyhedron can be linearly dependent or not, could you provide me with a proof?

Thanks

 

[Bosko]

Hi,

First assume that there is a polyhedron P, where Ax<=b and x is free variable whose dimension is n. Besides, rank(A) = n. I really wonder if extreme points in a polyhedron can be linearly dependent? I used even ChatGPT, but it includes some shaky calculations while proofing. In short, if extreme points in a polyhedron can be linearly dependent or not, could you provide me with a proof?

Thanks

As an example you can consider a triangle in the plane R^2 with vertices
A=(0,1)
B=(1,0)
C=(1,1)

x<=1
y<=1
x+y>=1 ( -x-y<=-1 )

 

[mertcan]

very thanks for your reply. Well, may I ask if ANY TWO extreme points in a polyhedron can be linearly dependent or not (those 2 extreme points are multiple of each other or not), could you provide me with a proof?

Thanks

 

[Office_Shredder]

It's trivial that you can get two points to be linearly dependent. For example the square with vertices (0,0), (0,1), (1,0) and (1,1). (0,0) Is linearly dependent with every other vertex.