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