Finding Vertices of Polyhedron with Simplex Method

[evinda]

Hello! (Wave)

I want to find the vertices of the polyhedron that the following relations define:$$x_1+ x_2+ x_3+ x_4=2 \\ x_1-x_2+x_3-x_4=1 \\ x_1+x_2-x_3+x_4=1 \\ |x_i| \leq 1, i \in \{ 1, \dots, 4\}$$

I have thought to set $y_i=x_i+1$ since the simplex method requires the variables to be positive or zero.

Then I found the following equations:

$$y_1+y_2+y_3+y_4=6 \\ y_1-y_2+y_3-y_4=1 \\ y_1+y_2-y_3+y_4=3$$

$$0 \leq y_i \leq 2, i \in \{ 1, \dots, 4 \}$$

$A=\begin{bmatrix}
1 & 1 & 1 & 1\\
1 & -1 & 1 &-1 \\
1 & 1 & -1 & 1
\end{bmatrix}$

The rank of $A$ is $3$.$P_1=\begin{bmatrix}
1\\
1\\
1
\end{bmatrix}, P_2=\begin{bmatrix}
1\\
-1\\
1
\end{bmatrix}, P_3=\begin{bmatrix}
1\\
1\\
-1
\end{bmatrix}, P_4=\begin{bmatrix}
1\\
0\\
0
\end{bmatrix}$

• $P_1, P_2, P_3$ are linearly independent.
  
  We solve the system $P_1 y_1+ P_2 y_2+ P_3 y_3=\begin{bmatrix}
  6\\
  1\\
  3
  \end{bmatrix}$ and we get the basic feasible non-degenate solution $\left( 2, \frac{5}{2}, \frac{3}{2}, 0 \right)$.
  
• $P_1, P_2, P_4$ are linearly independent.
  
  We solve the system $P_1 y_1+ P_2 y_2+ P_4 y_4=\begin{bmatrix}
  6\\
  1\\
  3
  \end{bmatrix}$ and we get the basic feasible non-degenate solution $\left( 2, 1,0, 5 \right)$.
  
• $P_2, P_3, P_4$ are linearly independent.
  
  We solve the system $P_2 y_2+ P_3 y_3+ P_4 y_4=\begin{bmatrix}
  6\\
  1\\
  3
  \end{bmatrix}$ and and we see that it cannot be satisfied.
  

Are the non-degenarate basic feasible solutions that I have found right?

If so, are they the same for the initial relations that are given? (Thinking)

 

[I like Serena]

Hey evinda! (Smile)

What happened to the constraint $y_i \le 2$? (Wondering)

 

[evinda]

What happened to the constraint $y_i \le 2$? (Wondering)

Oh, sorry... I forgot them... (Tmi)

So we have additionally the folloiwng relations, right? (Thinking)

$$y_1+y_5=2 \\ y_2+y_6=2 \\ y_3+y_7=2 \\ y_4+y_8=2 \\ y_5,y_6, y_7, y_8 \geq 0$$

Then we have the following matrix, right?$A=\begin{bmatrix}
1 & 1 & 1 & 1 & 0 &0 & 0 & 0 &0 \\
1 & -1 & 1 & -1 & 0 & 0 & 0 & 0 & 0\\
1 & 1 & -1 & 0 & 1 & 0 & 0 & 0 & 0\\
1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\
0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0\\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1
\end{bmatrix}$

 

[I like Serena]

Yes, but I think the 5th column is out of place. (Worried)

 

[evinda]

Yes, but I think the 5th column is out of place. (Worried)

Oh yes, right... The right matrix is the following, right?

$A=\begin{bmatrix}
1 & 1 & 1 & 1 & 0 &0 & 0 & 0 &0 \\
1 & -1 & 1 & -1 & 0 & 0 & 0 & 0 & 0\\
1 & 1 & -1 & 1 & 0 & 0 & 0 & 0 & 0\\
1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\
0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0\\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1
\end{bmatrix}$

The rank is $7$. So do we have $\binom{9}{7}=36$ possible combinations of the columns to check?
Or am I wrong?

 

[I like Serena]

Oh yes, right... The right matrix is the following, right?

I think you have 8 variables.
Shouldn't there be 8 columns then, instead of 9? (Wondering)

 

[evinda]

I think you have 8 variables.
Shouldn't there be 8 columns then, instead of 9? (Wondering)

I think this is the right matrix:

$A=\begin{bmatrix}
1 & 1 & 1 & 1 & 0 &0 & 0 & 0 \\
1 & -1 & 1 & -1 & 0 & 0 & 0 & 0 \\
1 & 1 & -1 & 1 & 0 & 0 & 0 & 0\\
1 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\
0 & 1 & 0 & 0 & 0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 & 0 & 0 & 1 & 0\\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 1
\end{bmatrix}$

Isn't it? (Tmi)

If so, then the rank is again $7$ and so there are $\binom{8}{7}=8$ possible combinations, right?

 

[I like Serena]

Isn't it? (Tmi)

If so, then the rank is again $7$ and so there are $\binom{8}{7}=8$ possible combinations, right?

Right! (Nod)

 

[evinda]

Right! (Nod)

Is there an other way to check if seven columns are linearly independent rather than checking if the following holds?

$a_1 P_1 + a_2 P_2+ \dots + a_7 P_7=0 \Rightarrow a_i=0 , i \in \{ 1,\dots, 7 \}$

 

[I like Serena]

Is there an other way to check if seven columns are linearly independent rather than checking if the following holds?

$a_1 P_1 + a_2 P_2+ \dots + a_7 P_7=0 \Rightarrow a_i=0 , i \in \{ 1,\dots, 7 \}$

We can create a matrix of those 7 columns and then reduce it to column echelon form.
That is, add or subtract multiples of one column to another, making as much zero as possible.
The result will tell us if the original columns were independent. (Nerd)

 

[evinda]

We can create a matrix of those 7 columns and then reduce it to column echelon form.
That is, add or subtract multiples of one column to another, making as much zero as possible.
The result will tell us if the original columns were independent. (Nerd)

I got this matrix:$\begin{bmatrix}
1 & 1 & 1 & 1 & 0 &0 & 0 & 0 \\
0 & 2 & 0 & 2 & 0 & 0 & 0 & 0 \\
0 & 0 & 2 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 2 & 0 & 0 & 0\\
0 & 1 & 0 & 0 & 0 & -2 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & -2 & 0\\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 1
\end{bmatrix}$

How can we deduce now which of the columns are independent? (Thinking)

 

[I like Serena]

Err... that doesn't really look like column echelon form.
Nor is it a matrix of 7 columns.
Ah, I guess I should have said that we can also multiply or divide a column by a non-zero constant. (Wait)
And we can also swap columns.
We should start from 7 columns though. (Worried)First we should pick the matrix of the 7 columns that we wish to check for independence.
Suppose we pick the first 7 columns, effectively setting $y_8=0$.
\begin{bmatrix}
1 & 1 & 1 & 1 & 0 &0 & 0 \\
1 & -1 & 1 & -1 & 0 & 0 & 0 \\
1 & 1 & -1 & 1 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 1 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 1 & 0 & 0 & 0
\end{bmatrix}

As the first step, let's subtract column 5 from column 1, column 6 from column 2, and column 7 from column 3:
\begin{bmatrix}
1 & 1 & 1 & 1 & 0 &0 & 0 \\
1 & -1 & 1 & -1 & 0 & 0 & 0 \\
1 & 1 & -1 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 1 & 0 & 0 & 0
\end{bmatrix}

Now we can tell that columns 4, 5, 6, and 7 are independent of all others, since they only have a single non-zero entry in a row. (Mmm)
That leaves the question whether columns 1, 2, and 3 are independent.Ideally we get a $a_{11} = 1$ in the top left with only zeroes to the right
And then $a_{22} = 1$ with only zeroes to the right.
And so on.

We can work into that direction by subtracting the first column from respectively the 2nd, 3rd, and 4th column:
\begin{bmatrix}
1 & 0 & 0 & 0 & 0 &0 & 0 \\
1 & -2 & 0 & -2 & 0 & 0 & 0 \\
1 & 0 & -2 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 1 & 0 & 0 & 0
\end{bmatrix}

Then divide both the 2nd and 3rd column by $-2$.
\begin{bmatrix}
1 & 0 & 0 & 0 & 0 &0 & 0 \\
1 & 1 & 0 & -2 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 1 & 0 & 0 & 0
\end{bmatrix}

And finally subtract the 2nd column from the 1st and the 4th, and also subtract the 3rd column from the 1st:
\begin{bmatrix}
1 & 0 & 0 & 0 & 0 &0 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 1 & 0 & 0 & 0
\end{bmatrix}

Now we can see that all columns are independent.
(Whew)

It should now be a bit quicker for the other combinations, since the matrix is pretty much identical. (Nerd)
I think we will find that any combination of 7 columns is independent.

 

[Opalg]

Hello! (Wave)

I want to find the vertices of the polyhedron that the following relations define:$$x_1+ x_2+ x_3+ x_4=2 \\ x_1-x_2+x_3-x_4=1 \\ x_1+x_2-x_3+x_4=1 \\ |x_i| \leq 1, i \in \{ 1, \dots, 4\}$$

I have thought to set $y_i=x_i+1$ since the simplex method requires the variables to be positive or zero.

Unless the question specifically asks you to use the simplex method, I think that you would find it very much easier to solve these equations using the usual echelon reduction process for the three given equations. The matrix $$\begin{bmatrix}1&1&1&1&2 \\ 1&-1&1&-1&1 \\ 1&1&-1&1&1 \end{bmatrix}$$ reduces to $$\begin{bmatrix}1&1&1&1&2 \\ 0&-2&0&-2&-1 \\ 0&0&-2&0&-1 \end{bmatrix}.$$ From that, you can read off the values for $x_1$ and $x_3$. The other two variables satisfy the equation $x_2 + x_4 = \frac12$. The extreme values of that occur when either $x_2$ or $x_4$ is equal to $1$ (and the other one is $-\frac12$).

 

[evinda]

Unless the question specifically asks you to use the simplex method, I think that you would find it very much easier to solve these equations using the usual echelon reduction process for the three given equations. The matrix $$\begin{bmatrix}1&1&1&1&2 \\ 1&-1&1&-1&1 \\ 1&1&-1&1&1 \end{bmatrix}$$ reduces to $$\begin{bmatrix}1&1&1&1&2 \\ 0&-2&0&-2&-1 \\ 0&0&-2&0&-1 \end{bmatrix}.$$ From that, you can read off the values for $x_1$ and $x_3$. The other two variables satisfy the equation $x_2 + x_4 = \frac12$. The extreme values of that occur when either $x_2$ or $x_4$ is equal to $1$ (and the other one is $-\frac12$).

I found this matrix:

$\begin{bmatrix}
1 & 1 & 1 & 1 & | & 2\\
0 & -2 & 2 & -2 & | & 0\\
0 & 0 & 2 & 0 & | & 1
\end{bmatrix}$

Is it also right? (Thinking)

From this we get $x_3=\frac{1}{2}, x_2+ x_4=\frac{1}{2}, x_1=1$, right?

How do we find the extreme values of $x_2 + x_4 = \frac12$ ?
And do we use these to find the vertices? (Thinking)

 

[I like Serena]

I found this matrix:

$\left[\begin{array}{cccc|c}
1 & 1 & 1 & 1 & 2\\
0 & -2 & 2 & -2 & 0\\
0 & 0 & 2 & 0 & 1
\end{array}\right]$

Is it also right? (Thinking)

From this we get $x_3=\frac{1}{2}, x_2+ x_4=\frac{1}{2}, x_1=1$, right?

How do we find the extreme values of $x_2 + x_4 = \frac12$ ?
And do we use these to find the vertices? (Thinking)

Yes, that is also right. (Nod)
We can verify that by subtracting the 3rd row from the 2nd row.

The extreme values follow from the additional conditions that $|x_i| \le 1$, so we should check $x_2=\pm 1$ and $x_4=\pm 1$.
The result is indeed the set of vertices.

 

[evinda]

The extreme values follow from the additional conditions that $|x_i| \le 1$, so we should check $x_2=\pm 1$ and $x_4=\pm 1$.

Could you explain it further to me why, given that $|x_i| \le 1$, we have to check $x_2=\pm 1$ and $x_4=\pm 1$? (Thinking)

 

[I like Serena]

From this we get $x_3=\frac{1}{2}, x_2+ x_4=\frac{1}{2}, x_1=1$, right?

How do we find the extreme values of $x_2 + x_4 = \frac12$ ?
And do we use these to find the vertices? (Thinking)

Could you explain it further to me why, given that $|x_i| \le 1$, we have to check $x_2=\pm 1$ and $x_4=\pm 1$? (Thinking)

The solution of the system is $(x_1,x_2,x_3,x_4) = (1, t, \frac 12, \frac 12 - t)$ where $t \in [\frac 12, 1]$.
It represents a line segment.
Since we only want the vertices of the (degenerate) polyhedron, we pick the (possible) end points. (Nerd)

 

[evinda]

The solution of the system is $(x_1,x_2,x_3,x_4) = (1, t, \frac 12, \frac 12 - t)$ where $t \in [\frac 12, 1]$.

Why does it hold that $t \in [\frac 12, 1]$ ? (Thinking)

 

[I like Serena]

Why does it hold that $t \in [\frac 12, 1]$ ? (Thinking)

How would we solve $x_2+x_4=\frac 12$ with the conditions $-1\le x_2 \le 1$ and $-1\le x_4 \le 1$? (Wondering)

 

[evinda]

How would we solve $x_2+x_4=\frac 12$ with the conditions $-1\le x_2 \le 1$ and $-1\le x_4 \le 1$? (Wondering)

$$-1 \leq x_2 \leq 1 \Rightarrow -1 \leq \frac{1}{2}-x_4 \leq 1 \Rightarrow -\frac{3}{2} \leq - x_4 \leq \frac{1}{2} \Rightarrow -\frac{1}{2} \leq x_4 \leq \frac{3}{2}$$

And respectively we get $-\frac{1}{2} \leq x_2 \leq \frac{3}{2}$.

What other restrictions could we get? (Thinking)

 

[I like Serena]

$$-1 \leq x_2 \leq 1 \Rightarrow -1 \leq \frac{1}{2}-x_4 \leq 1 \Rightarrow -\frac{3}{2} \leq - x_4 \leq \frac{1}{2} \Rightarrow -\frac{1}{2} \leq x_4 \leq \frac{3}{2}$$

And respectively we get $-\frac{1}{2} \leq x_2 \leq \frac{3}{2}$.

What other restrictions could we get? (Thinking)

Shouldn't both $x_2$ and $x_4$ be less or equal to $1$? (Wondering)

 

[evinda]

Shouldn't both $x_2$ and $x_4$ be less or equal to $1$? (Wondering)

Yes. So we deduce that $x_2, x_4 \in \left[ -\frac{1}{2},1\right]$, right?

 

[I like Serena]

Yes. So we deduce that $x_2, x_4 \in \left[ -\frac{1}{2},1\right]$, right?

Right! (Nod)

 

[evinda]

The solution of the system is $(x_1,x_2,x_3,x_4) = (1, t, \frac 12, \frac 12 - t)$ where $t \in [\frac 12, 1]$.
It represents a line segment.
Since we only want the vertices of the (degenerate) polyhedron, we pick the (possible) end points. (Nerd)

So we have that the solution of the system is $(x_1,x_2,x_3,x_4) = (1, t, \frac 12, \frac 12 - t)$ where $t \in [-\frac 12, 1]$.

Why in order to find the vertices of the (degenerate) polyhedron do we pick the (possible) end points?
Also do we find the end points by picking $t=-\frac{1}{2}$ and $t=1$?
If so we can reject the case $t=-\frac{1}{2}$ since the solution that we get isn't basic feasible, right? (Thinking)

 

[Opalg]

$$-1 \leq x_2 \leq 1 \Rightarrow -1 \leq \frac{1}{2}-x_4 \leq 1 \Rightarrow -\frac{3}{2} \leq - x_4 \leq \frac{1}{2} \Rightarrow -\frac{1}{2} \leq x_4 \leq \frac{3}{2}$$

And respectively we get $-\frac{1}{2} \leq x_2 \leq \frac{3}{2}$.

What other restrictions could we get? (Thinking)

If you combine the inequalities $-\frac{1}{2} \leqslant x_2 \leqslant \frac{3}{2}$ and $-1 \leqslant x_2 \leqslant 1$ then you get $-\frac{1}{2} \leqslant x_2 \leqslant 1.$

 

[evinda]

If you combine the inequalities $-\frac{1}{2} \leqslant x_2 \leqslant \frac{3}{2}$ and $-1 \leqslant x_2 \leqslant 1$ then you get $-\frac{1}{2} \leqslant x_2 \leqslant 1.$

I see... But how do we find now the vertices?
Do we look at $t=-\frac{1}{2}$ and $t=1$ ? If so, why is it like that?

 

[Opalg]

I see... But how do we find now the vertices?
Do we look at $t=-\frac{1}{2}$ and $t=1$ ? If so, why is it like that?

In this example, the "polyhedron" is one-dimensional, namely the line segment $(x_1,x_2,x_3,x_4) = (1, t, \frac 12, \frac 12 - t)$ (for $-\frac12 \leqslant t\leqslant 1$), and its "vertices" are the endpoints of that line segment.

 

[evinda]

In this example, the "polyhedron" is one-dimensional, namely the line segment $(x_1,x_2,x_3,x_4) = (1, t, \frac 12, \frac 12 - t)$ (for $-\frac12 \leqslant t\leqslant 1$), and its "vertices" are the endpoints of that line segment.

For $t=-\frac{1}{2}$, $(1, t, \frac 12, \frac 12 - t)=\left( 1, -\frac{1}{2}, \frac{1}{2},1 \right)$
and for $t=1$, $(1, t, \frac 12, \frac 12 - t)=\left( 1, 1, \frac{1}{2},- \frac{1}{2} \right)$.

So are these two points the "vertices" of the "polyhedron" ? (Thinking)

 

[evinda]

Since we only want the vertices of the (degenerate) polyhedron, we pick the (possible) end points. (Nerd)

What do you mean with degenerate polyhedron? (Thinking)

 

[I like Serena]

For $t=-\frac{1}{2}$, $(1, t, \frac 12, \frac 12 - t)=\left( 1, -\frac{1}{2}, \frac{1}{2},1 \right)$
and for $t=1$, $(1, t, \frac 12, \frac 12 - t)=\left( 1, 1, \frac{1}{2},- \frac{1}{2} \right)$.

So are these two points the "vertices" of the "polyhedron" ? (Thinking)

Yes. (Nod)

What do you mean with degenerate polyhedron? (Thinking)

Normally a polyhedron consists of a number of vertices connected by edges, such that faces (polygons) are formed.
A polyhedron usually has a certain volume.
If there are 2 faces or less, it won't contain a volume, and is considered degenerate.
In this case we don't even have a face - only a single line segment. (Nerd)

 

[evinda]

Normally a polyhedron consists of a number of vertices connected by edges, such that faces (polygons) are formed.
A polyhedron usually has a certain volume.
If there are 2 faces or less, it won't contain a volume, and is considered degenerate.
In this case we don't even have a face - only a single line segment. (Nerd)

So in this case we can say that if the line segment is one of the edges of a polyhedron , then its endpoints are vertices of the polyhedron. Right? (Thinking)

 

[I like Serena]

So in this case we can say that if the line segment is one of the edges of a polyhedron , then its endpoints are vertices of the polyhedron. Right? (Thinking)

Exactly. (Nod)

 

[evinda]

Exactly. (Nod)

Nice... Thank you! (Smile)