# How to understand the dimension of a subset in a vector space?

I feel difficult to understand the dimension of a subset in a vector space, defined in Bernhard Korte and Jens Vygen's Combinatorial Optimization:

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\{\text{rank}(A): A\text{ is an }n \times n\text{-matrix with }Ax = Ay, \text{ for all }x, y \in X \}.$$ A polyhedron $P \subseteq \mathbb{R}_n$ is called full-dimensional if dim $P = n$. Equivalently, a polyhedron is full-dimensional if and only if there is a point in its interior.

I will think $A$ as a linear mapping on $\mathbb{R}_n$. The dimension of a subset $X$ is defined as the nullity of the linear mapping with the maximum rank, over all linear mappings on $\mathbb{R}_n$ such that each maps $X$ to a single point.

Intuitively, I don't understand how the dimension of a subset (or even a polyhedrion) is related to the ranks and nullities of the linear mappings, and neither do I understand the purpose of considering only linear mappings that map $X$ to a single point.

Thanks for any clarification!

-
Do you understand what's going on if $X$ happens to be a vector subspace of $\mathbb{R}_n$? – user108903 Dec 16 '12 at 15:35
Yes. Consider a subspace V of Rn. The number of vectors in a basis of V is called the dimension of V , denoted by dim(V ). @user108903 – Ethan Dec 16 '12 at 15:38
I think @user108903's point was: Do you understand what this definition works out to when $X$ happens to be a subspace? – Henning Makholm Dec 16 '12 at 15:49
@HenningMakholm: not really. – Ethan Dec 16 '12 at 15:50
OK, it looks you need to think about the rank-nullity theorem to understand that. – user108903 Dec 16 '12 at 15:51

Given an arbitrary finite or infinite set $X\subset{\mathbb R}^n$ the "thickness" or "dimensionality" of $X$ can be felt by looking at all differences $y-x$ between two points $x$, $y\in X$. When, say, all these differences are parallel to a certain $2$-dimensional sample plane $E^2$ then we are inclined to say that $X$ is two-dimensional. Now we have to make this idea precise.

The set $\Delta:=\{y-x\ |\ x,\ y\in X\}$ of these differences spans a certain subspace $U\subset{\mathbb R}^n$, and this subspace has a well defined dimension $d$, where $0\leq d\leq n$. Korte/Vygen give one of many possible characterizations of this number $d$, given $X$, presumably one which is particularly useful when dealing with polyhedra.

To understand this criterion, note that the condition $Ax=Ay$ for all $x$, $y\in X$ is equivalent to $Az=0$ for all $z\in\Delta$, and this implies $Az=0$ for all $z\in U$. Conversely: If $Az=0$ for all $z\in U$ then a fortiori $Az=0$ for all $z\in\Delta$ and therefore $Ax=Ay$ for all $x$, $y\in X$.

Therefore Korte/Vygen's criterion can be read as follows: ${\rm dim}(X)$ is $n$ minus the maximal rank of a matrix annihilating all vectors of $U$. "Annihilating all vectors of $U$" means ${\rm ker}(A)\supset U$, in particular $$n-{\rm rank}(A)={\rm dim}\bigl({\rm ker}(A)\bigr)\geq {\rm dim}(U)=d\ .$$

Choose a basis $(e_1,e_2,\ldots, e_n)$ of ${\mathbb R}^n$ such that $(e_1,\ldots,e_d)$ is a basis of $U$. Then the map $A:\ {\mathbb R}^n\to{\mathbb R}^n$ with $Ae_i:=0$ $\ (1\leq i\leq d)$ and $Ae_i:=e_i$ $\ (d+1\leq i\leq n)$ has ${\rm ker}(A)=U$ and ${\rm rank}(A)=n-d$, so this $A$ is one of the $A$'s with maximal rank mentioned in the criterion.

-
Thanks! I saw you use orthogonal projection, which makes sense only when an inner product is defined. In a vector space without an inner product defined, does the dimension of a subset defined by Korte and Vygen still coincide with the dimension of a vector subspace, when the subset is a vector subspace? – Ethan Dec 16 '12 at 17:57
@Ethan: See my edit. Orthogonality is not used anymore. – Christian Blatter Dec 16 '12 at 18:51
Thanks! An example: given a convex polyhedron $P=\{x \in \mathbb{R}^n: A x =< b\}$, can we determine dim $P$ from $A$ and $b$? – Ethan Dec 16 '12 at 19:30
@Ethan: Since $P$ is completely determined by $A$ and $b$ its dimension is determined by $A$ and $b$ as well. In particular, if all $b_i>0$ then ${\rm dim}(P)=n$, since $P$ then contains a neighborhood of the origin. – Christian Blatter Dec 17 '12 at 9:30
Thanks! In general, how is dim P determined from A and b? – Ethan Dec 17 '12 at 15:33