Pointing a polyhedron

Dependencies:

$\newcommand{\defeq}{=}$ $\newcommand{\rank}{\operatorname{rank}}$ $\newcommand{\Span}{\operatorname{span}}$ $\newcommand{\xhat}{\widehat{x}}$ $\newcommand{\xtild}{\widetilde{x}}$ $\newcommand{\yhat}{\widehat{y}}$

Let $P \defeq \{x \in \mathbb{R}^n: (a_i^Tx = b_i, \forall i \in E) \wedge (a_i^Tx \ge b_i, \forall i \in I)\}$ be a non-empty polyhedron. Let $A \defeq \{a_i: i \in I \cup E\}$. Let $B \defeq \{a_i: i \in T\}$ (where $T \subseteq I \cup E$) be a basis of $A$.

Let $D \defeq \{x \in \mathbb{R}^n: (a_i^Tx = 0, \forall i \in I \cup E)\}$. Let $C \defeq \{a_i: i \in H\}$ (where $H$ is a new set of indices, i.e., $H \cap (I \cup E) = \emptyset$) be a basis of $D$. Let $P' \defeq \{x \in P: (a_i^Tx = 0, \forall i \in H)\}$.

Then the following hold:

$|C| = n - \rank(A)$ and $B \cup C$ is a basis of $\mathbb{R}^n$
$P = \{\xhat + d: \xhat \in P', d \in D\}$.

Note that part 1 implies that $P'$ is a full-rank polyhedron. Part 2 implies that any polyhedron $P$ can be decomposed into a full-rank polyhedron $P'$ and the double recession space of $P$.

Proof

By the rank-nullity theorem, we get $|C| = n - \rank(A) = n - |B|$. Since $\forall i \in I \cup E$, $\forall j \in H$, $a_i^Ta_j = 0$, we get that $B \cup C$ is linearly independent. Since $|B \cup C| = |B| + |C| = n$, we get that $B \cup C$ is a basis of $\mathbb{R}^n$.

For $\xhat \in P'$ and $d \in D$, we get $\xhat + d \in P$ since $d$ is a double direction of $P$.

Let $x \in P$. Since $B \cup C$ is a basis of $\mathbb{R}^n$, we get $x = \sum_{i \in I \cup E \cup H} \alpha_ia_i$. Let $\xhat \defeq \sum_{i \in I \cup E} \alpha_ia_i$ and $d \defeq \sum_{i \in H} \alpha_ia_i$. Then $\xhat + d = x$. $d \in \Span(C) = D$. For $i \in I \cup E$, $a_i^T\xhat = a_i^Tx - a_i^Td = a_i^Tx$. Hence, $\xhat \in P$. Also, for $j \in H$, $a_j^T\xhat = \sum_{i \in I \cup E} \alpha_i(a_j^Ta_i) = 0$. Hence, $\xhat \in P'$.

Dependency for: None

Info:

Depth: 9
Number of transitive dependencies: 53

Transitive dependencies:

/linear-algebra/matrices/gauss-jordan-algo
/linear-algebra/vector-spaces/condition-for-subspace
/complex-numbers/conjugation-is-homomorphic
/sets-and-relations/equivalence-relation
Group
Ring
Polynomial
Field
Vector Space
Cone
Convex combination and convex hull
Convex set
Double direction of a convex set and double recession space
Inner product space
Orthogonality and orthonormality
Inner product is anti-linear in second argument
Linear independence
A set of mutually orthogonal vectors is linearly independent
Incrementing a linearly independent set
Span
Gram-Schmidt Process
Joining orthogonal linindep sets
Integral Domain
Comparing coefficients of a polynomial with disjoint variables
Semiring
Matrix
Polyhedral set and polyhedral cone
Double directions of a polyhedron (incomplete)
Stacking
System of linear equations
Product of stacked matrices
Matrix multiplication is associative
Reduced Row Echelon Form (RREF)
Elementary row operation
Every elementary row operation has a unique inverse
Row equivalence of matrices
Matrices over a field form a vector space
Row space
Row equivalent matrices have the same row space
RREF is unique
Identity matrix
Inverse of a matrix
Inverse of product
Elementary row operation is matrix pre-multiplication
Row equivalence matrix
Equations with row equivalent matrices have the same solution set
Basis of a vector space
Linearly independent set is not bigger than a span
Homogeneous linear equations with more variables than equations
Rank of a homogenous system of linear equations
Rank of a matrix
Basis of F^n
A set of dim(V) linearly independent vectors is a basis