2
$\begingroup$

In a book of combinatorial optimization the following definition is stated:

A polyhedron in $\mathbb{R}^n$ is a set of type $P = \left\{x \in \mathbb{R}^n \;:\; Ax \leq b \right\}$ for some matrix $A \in \mathbb{R}^{m \times n}$ and some vector $b \in \mathbb{R}^m$. If $A$ and $b$ are rational, then $P$ is a rational polyhedron. A bounded polyhedron is also called a polytope. We denote by $rank(A)$ the rank of a matrix $A$. The dimension $dim \; X$ of a nonempty set $X \subseteq \mathbb{R}^n$ is defined to be $n- max\left\{rank(A) \;:\; A \in \mathbb{R}^{n \times n}, \; Ax= Ay \;\;\forall x, y \in X\right\}$. A polyhedron $P \subseteq \mathbb{R}^n$ is called full-dimensional if $dim \; P = n$.

I was trying to figure out if there's a geometric meaning for the piece:

The dimension $dim \; X$ of a nonempty set $X \subseteq \mathbb{R}^n$ is defined to be $n- max\left\{rank(A) \;:\; A \in \mathbb{R}^{n \times n}, \; Ax= Ay \;\;\forall x, y \in X\right\}$

With such goal in mind I started with $n = 2$ and $X$ the unit circle with origin $O = (0,0)$, And I was trying to find a matrix that satisfy the conditions, however I can't understand if there's a geometric interpretation of the set used to define the the dimension.

$\endgroup$
  • $\begingroup$ I'm not even sure what's meant by $Ax\leq b$ considering both objects are vectors in $\mathbb{R}^m$. $\endgroup$ – Justin Benfield Jun 27 '16 at 10:33
  • $\begingroup$ @JustinBenfield That is actually standard notation in optimization: $Ax= b$ stands for a system of linear equations (check any freshman linear algebra book for this), and $Ax\leq b$ similarly stands for a system of linear inequalities all written on the $\leq$ form. $\endgroup$ – A.Sh Jun 27 '16 at 10:37
  • $\begingroup$ @A.Sh I saw these in high school algebra, but never as matricies notated like this (and I took 3 different Linear Algebra classes in the course of my undergrad!; standard intro class, junior level applications class, and advanced linear and multilinear algebra). Interesting..... $\endgroup$ – Justin Benfield Jun 27 '16 at 10:41
  • $\begingroup$ @JustinBenfield Perhaps this might help for the case of systems of equations: en.wikipedia.org/wiki/System_of_linear_equations#General_form The case of inequalities is similar. $\endgroup$ – A.Sh Jun 27 '16 at 10:47
2
$\begingroup$

$Ax = Ay$ is the same thing as $A(x-y) = 0$ — if $Ax = Ay$ for all $x,y \in X$, then if you choose any $P \in X$, you have $X \subseteq P + \text{Nullspace(A)}$.

$\text{Nullspace(A)}$ is an $(n - \text{rank}(A))$-dimnsional vector space; consequently it would be reasonable to insist that $\dim(X) \leq n - \text{rank}(A)$ whenever such a thing were to happen.

That definition is equivalent to defining the dimension of a set $X$ as the dimension of its affine hull. The set of all differences $x-y$ for $x,y \in X$ span a vector space $V$, and if $P \in X$, we call $P +V$ the affine hull of $X$.

e.g. the affine hull of a pair of points is the line through them. For a triple of noncollinear points, it's the plane containing them. For a triple of collinear points, the affine hull is the line through them.

An alternative definition is that the affine hull of a set $X$is the set of all affine linear combinations of points of $X$: that is, linear combinations whose coefficients add up to $1$.them.

Another alternative is that the affine hull of $X$ is the smallest affine set containing $X$.

$\endgroup$
  • $\begingroup$ So the $dim \;X$ is the dimension of the smallest affine space that contains the set $X$, right? $\endgroup$ – user8469759 Jun 27 '16 at 12:14
  • $\begingroup$ @user8469759: Right $\endgroup$ – Hurkyl Jun 27 '16 at 12:14
  • $\begingroup$ Out of curiosity, for the case I exposed dim $X$ is two right? Because the smallest affine space containing the set $X$ is $\mathbb{R}^2$, right? $\endgroup$ – user8469759 Jun 27 '16 at 12:23
  • $\begingroup$ @user8469759: Right. $\endgroup$ – Hurkyl Jun 27 '16 at 12:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.