Exercise 2.19* (Dimension of polyhedra)

Question

Let $P \subset \mathfrak{R}^n$ be a polyhedron in standard form whose definition involves $m$ linearly independent equality constraints. Its dimension is defined as the smallest integer $k$ such that $P$ is contained in some $k$-dimensional affine subspace of $\mathfrak{R}^n$.
\begin{enumerate}[label=(\alph*)]
\item Explain why the dimension of $P$ is at most $n-m$.
\item Suppose that $P$ has a nondegenerate basic feasible solution. Show that the dimension of $P$ is equal to $n-m$.
\item Suppose that $\mathbf{x}$ is a degenerate basic feasible solution. Show that $\mathbf{x}$ is degenerate under every standard form representation of the same polyhedron (in the same space $\mathfrak{R}^n$).
\end{enumerate}

Elu Thingol · Accepted Answer

\begin{enumerate}[label=(\alph*)]
\item It is obvious from the definition of a standard form polyhedron that $P$ can be alternatively represented as the positive subset of the null space of the affine transformation $f(\mathbf{x}) = \mathbf{A}\mathbf{x} - \mathbf{b}$, i.e., $P \subseteq \operatorname{null}(f)$. By the monotonicity of dimension, we have $$\dim P \leq \dim(\operatorname{null}(f)) = \dim\left(\operatorname{null}(\mathbf{A})ight).$$
Finally, by the Dimension Theorem (see p.30), we have
$$\dim\left(\operatorname{null}(\mathbf{A})ight) = n - \operatorname{rank}(\mathbf{A}) = n - m$$
as $\operatorname{rank}(A) = m$ by the theorem assumption.

\item We now demonstrate that $\dim(P) \geq n-m$. 	extit{Per definitionem}, we must find $n-m$ linearly independent vectors in $P$.
ewline

By the exercise assumption, there exist exactly $m$ linearly independent columns $\mathbf{A}_{B(1)},\, \ldots,\, \mathbf{A}_{B(m)}$ corresponding to the non-zero entries of the basic feasible solution $\mathbf{x}^*$ and forming the basis matrix $\mathbf{B}$. Similarly, there are exactly $n-m$ columns $\mathbf{A}_{i_1},\,\ldots,\mathbf{A}_{i_{n-m}}$ corresponding to the zero entries of $\mathbf{x}^*$. Without loss of generality, assume that $\mathbf{A}$ is of the form $[\mathbf{B} \ | \mathbf{A}_{i_1},\,\ldots,\mathbf{A}_{i_{n-m}} ]$ (i.e., rearrange the columns of $\mathbf{A}$ so that the basic columns come first).
ewline

Since $\mathbf{B}$ is invertible, we can define
$$\forall 1 \leq j \leq n-m: \quad \mathbf{d}_j := -\mathbf{B}^{-1}\mathbf{A}_{i_j},$$
which is a collection of $n-m$ vectors in $\mathfrak{R}^m$ with the property that $\mathbf{B}\mathbf{d}_j + \mathbf{A}_{i_j} = \mathbf{0}$. Using these vectors, we can define $n-m$ direction vectors in $\mathfrak{R}^n$ by setting
$$\forall 1 \leq j \leq n-m: \quad \hat{\mathbf{d}}_j := \begin{bmatrix} \mathbf{d}_j\ \mathbf{e}_j \end{bmatrix},$$
where $\mathbf{e}_j$ denote the $j$th unit vector in $\mathfrak{R}^{n-m}$. By construction $\mathbf{A}\hat{\mathbf{d}}_j = \mathbf{0}$ and due to the unit vector tail, these directions are linearly independent. In other words, we already have $\mathbf{A}(\mathbf{x}^* + \hat{\mathbf{d}}_j) = \mathbf{b}$ for $n-m$ independent vectors. Furthermore, we can insure that the resulting vectors also satisfy non-negativity by tweaking them using an $\epsilon > 0$ small enough:
$$\forall 1 \leq j \leq n-m: \quad 	ilde{\mathbf{x}}_j := \mathbf{x}^* + \epsilon \cdot \hat{\mathbf{d}}_j \in P.$$
Thus, $	ilde{\mathbf{x}}_1,\ldots,	ilde{\mathbf{x}}_{n-m}$ are definitely contained in $P$. Since $\hat{\mathbf{d}}_1,\ldots,\hat{\mathbf{d}}_{n-m}$ are linearly independent, so are $	ilde{\mathbf{x}}_1,\ldots,	ilde{\mathbf{x}}_{n-m}$ and we are done.

\item Using parts 1 and 2, compare the number $m,m'$ of equality constraints in two representations of $P$ under which $x$ is degenerate and nondegenerate, respectively. Then, count active constraints and arrive at a contradiction regarding the dimension $\dim(P)$ of $P$.
\end{enumerate}

Exercise 2.19* (Dimension of polyhedra)

Answers

Comments

Exercise 2.19* (Dimension of polyhedra)

Answers

Comments

Add answer