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

$$ $$ $$ $$ Let $P=\{x\in {\mathbb{R}}^n:(a_i^{T}x\ge b_i,\mathrm{\forall }i\in I)\wedge (a_i^{T}x=b_i,\mathrm{\forall }i\in E)\}$ be a non-empty polyhedron without any implicit equalities. Let $A=\{a_i:i\in E\}$. Then $\dim (P)=n-\mathrm{rank}(A)$.

Proof

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

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

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

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

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

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

Dependency for: None

Info:

• Depth: 9
• Number of transitive dependencies: 45

Transitive dependencies:

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