2

In a lecture on the subject of we were given 2 definitions for adjacent vertices.
Let $P \subseteq \mathbb R^n$ be a polyhedron, and $\vec x, \vec y \in P$, then:

(1) $\vec x$, $\vec y$ are adjacent vertices if they have $n−1$ constraints in common which they satisfy.

(2) Let $V(P)$ be the set of the vertices in $P$, then $\vec x$, $\vec y$ are adjacent vertices if $\exists \vec c \in \mathbb R^n, \forall \vec z \in V(P), \vec z \ne \vec x, \vec y: c^T\vec x=c^T\vec y<c^T\vec z$

I've been trying to prove the equivalence between the two definitions, but have been unsuccessful.

My Question: How can I prove that $(1) \rightarrow (2)$? I.e., if $\vec x$, $\vec y$ have $n−1$ constraints in common which they satisfy then $\exists \vec c \in \mathbb R^n, \forall \vec z \in V(P), \vec z \ne \vec x, \vec y: c^T\vec x=c^T\vec y<c^T\vec z$.

Community
  • 1
asherbret
  • 71

1 Answers1

0

Here's what I came up with:

Lemma: Let $x,y,z \in \mathbb R^n; x\ne y\ne z; x,y,z \ne \vec 0$ and $y-x, z-y, x-z \in U\subseteq \mathbb R^n$ where $U$ is vector space which satisfies $dim(U)=1$ then one of the vectors $x,y,z$ is a convex combination of the other two.
Proof: It's given that $dim(U)=1$. From here we conclude that there exists a vector $v=(v_1, ..., v_n)\ne \vec 0$ that satisfies: $$ \forall u\in U, \exists c \ne 0: u=cv $$ Assuming $x=(x_1, ..., x_n), y=(y_1, ..., y_n), z=(z_1, ..., z_n)$ and since $y-x, z-y, x-z \in U$ it can be concluded that $\exists a,b,c \ne 0$ such that for each $i \in {1, ..., n}$: $$y_i-x_i=av_i; z_i-y_i=bv_i; x_i-z_i=cv_i;$$ Since $v\ne \vec0$ we may conclude that $\exists m: v_m \ne 0$. This implies that $x_m\ne y_m \ne z_m$. Without loss of generality we may assume that: $$x_m\lt y_m \lt z_m$$ Define : $$\lambda=\frac{y_m - z_m}{x_m-z_m}=-\frac{bv_m}{cv_m}=-\frac{b}{c}$$ And under our assumption: $0<\lambda<1$. We will now prove that: $$y=\lambda x+(1-\lambda)z$$ $y=\lambda x+(1-\lambda)z \iff \forall i \in \{1, ...,n\}: y_i=\lambda x_i+(1-\lambda)z_i \iff y_i=-\frac{b}{c}x_i+(1+\frac{b}{c})z_i \iff c(y_i-z_i )=b(z_i-x_i ) \iff c⋅-bv_i=b⋅-cv_i$ $$\blacksquare$$ Let $M$ be the matrix built from $n-1$ common constraints of $x,y$. These constraints are linearly independent and so $rank(M)=n-1$. From here we can conclude that: $$dim(Null(M))=1$$ Let $c$ be the vector of column sums of $M$. I.e.: $$c=(c_1,c_2,…,c_n ):c_i=\sum_{j=1}^{n-1} M_{j,i} $$ Let $b=(b_1,...,b_{n-1})$ be the tight constraints vector common for $x,y$. It can be shown that $c^T\vec x=c^T\vec y=\sum_{k=1}^{n-1}b_k$.
We will now prove that $\forall z: c^T\vec x=c^T\vec y<c^T\vec z$ by contradiction. I.e., let's assume $\exists z: c^T\vec x=c^T\vec y=c^T\vec z$. I.e., $c^T\vec z=\sum_{k=1}^{n-1}b_k$. From this we can see that $z$ shares the $n-1$ tight constraints of $x,y$, too. This means that: $$Mx=My=Mz$$
I.e.: $$M(x-z)=M(z-y)=M(y-x)=\vec 0$$ I.e.: $$x-z, z-y, y-x \in Null(M)$$ Since $dim(Null(M))=1$, and according to the lemma, one of the vectors $x,y,z$ is a convex combination of the other two. From this we get a contradiction from fact that each of $x,y,z$ are vertices. $$\blacksquare$$

Botanicus
  • 90
asherbret
  • 71