Dimension of a polyhedron

Dependencies:

1. Polyhedral set and polyhedral cone
2. Implicit equality
3. Affine independence (incomplete)
4. Dimension of a set of vectors
5. Rank of a homogenous system of linear equations
6. Linearly independent set is not bigger than a span
7. Interior point of polyhedron

$\newcommand{\defeq}{=}$ $\newcommand{\rank}{\operatorname{rank}}$ $\newcommand{\xhat}{\widehat{x}}$ $\let\eps\epsilon$ Let $P \defeq \{x \in \mathbb{R}^n: (a_i^Tx \ge b_i, \forall i \in I) \wedge (a_i^Tx = b_i, \forall i \in E)\}$ be a non-empty polyhedron without any implicit equalities. Let $A \defeq \{a_i: i \in E\}$. Then $\dim(P) = n - \rank(A)$.

Proof

Interpret $A$ as a matrix whose rows are $\{a_i^T: i \in E\}$. Let $S \defeq \{x \in \mathbb{R}^n: Ax = 0\}$. By the rank-nullity theorem, $\dim(S) = n - \rank(A)$.

Proof that $\dim(P) \le n - \rank(A)$.

Let $X \defeq \{x^{(0)}, x^{(1)}, \ldots, x^{(m)}\}$ be the max number of affinely independent vectors in $P$. Then $\dim(P) = m$. For $i \in [m]$, let $d^{(i)} \defeq x^{(i)} - x^{(0)}$ and $D \defeq \{d^{(i)}: i \in [m]\}$. Then $D$ is linearly independent.

For any $j \in E$, we have $a_j^Td^{(i)} = a_j^Tx^{(j)} - a_j^Tx^{(0)} = b_j - b_j = 0$. Hence, $Ad^{(i)} = 0$. Hence, $D \subseteq S$. Since $D$ is linearly independent, $|D| \le \dim(S) = n - \rank(A)$. Since, $\dim(P) = |D|$, we get $\dim(P) \le n - \rank(A)$.

Proof that $\dim(P) \ge n - \rank(A)$

Let $D \defeq \{d^{(1)}, \ldots, d^{(m)}\}$ be a basis of $S$. Then $m = n - \rank(A)$. Let $\xhat \in P$ be an interior point of $P$. Let $x^{(0)} \defeq \xhat$. For $i \in [m]$, let $x^{(i)} \defeq \xhat + \eps d^{(i)}$, where $\eps$ is an arbitrarily small positive real number. For small enough $\eps$, we can guarantee that $x^{(i)} \in P$ for all $i \in [m]$. This is because $\xhat$ is an interior point of $P$, and for every $j \in E$, $a_j^Tx^{(i)} = a_j^T\xhat = b_j$. By construction, $X \defeq \{x^{(i)}: 0 \le i \le m\}$ is affinely independent. Also, $X \subseteq P$. Hence, $\dim(P) \ge |X| - 1 = m = n - \rank(A)$.

Dependency for: None

Info:

• Depth: 9
• Number of transitive dependencies: 45

Transitive dependencies:

1. /linear-algebra/matrices/gauss-jordan-algo
2. /linear-algebra/vector-spaces/condition-for-subspace
3. /sets-and-relations/equivalence-relation
4. Group
5. Ring
6. Polynomial
7. Field
8. Vector Space
9. Cone
10. Convex combination and convex hull
11. Convex set
12. Linear independence
13. Affine independence (incomplete)
14. Span
15. Integral Domain
16. Comparing coefficients of a polynomial with disjoint variables
17. Semiring
18. Matrix
19. Polyhedral set and polyhedral cone
20. Implicit equality
21. Interior point of polyhedron
22. Stacking
23. System of linear equations
24. Product of stacked matrices
25. Matrix multiplication is associative
26. Reduced Row Echelon Form (RREF)
27. Elementary row operation
28. Every elementary row operation has a unique inverse
29. Row equivalence of matrices
30. Matrices over a field form a vector space
31. Row space
32. Row equivalent matrices have the same row space
33. RREF is unique
34. Identity matrix
35. Inverse of a matrix
36. Inverse of product
37. Elementary row operation is matrix pre-multiplication
38. Row equivalence matrix
39. Equations with row equivalent matrices have the same solution set
40. Basis of a vector space
41. Linearly independent set is not bigger than a span
42. Homogeneous linear equations with more variables than equations
43. Rank of a homogenous system of linear equations
44. Rank of a matrix
45. Dimension of a set of vectors