# Understanding definition of “dimension” of a subset of $\mathbb{R}^n$

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.

• I'm not even sure what's meant by $Ax\leq b$ considering both objects are vectors in $\mathbb{R}^m$. – Justin Benfield Jun 27 '16 at 10:33
• @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. – A.Sh Jun 27 '16 at 10:37
• @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..... – Justin Benfield Jun 27 '16 at 10:41
• @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. – A.Sh Jun 27 '16 at 10:47

$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$.

• So the $dim \;X$ is the dimension of the smallest affine space that contains the set $X$, right? – user8469759 Jun 27 '16 at 12:14
• @user8469759: Right – Hurkyl Jun 27 '16 at 12:14
• 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? – user8469759 Jun 27 '16 at 12:23
• @user8469759: Right. – Hurkyl Jun 27 '16 at 12:52