1
$\begingroup$

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!

  • 0
    Do you understand what's going on if $X$ happens to be a vector subspace of $\mathbb{R}_n$?2012-12-16
  • 1
    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 ). @user1089032012-12-16
  • 0
    I think @user108903's point was: Do you understand what _this_ definition works out to when $X$ happens to be a subspace?2012-12-16
  • 0
    @HenningMakholm: not really.2012-12-16
  • 0
    OK, it looks you need to think about the rank-nullity theorem to understand that.2012-12-16
  • 0
    I'd appreciate if there is some detailed explanation. I know about the rank-nullity theorem, but can't relate it here. Thanks! @user1089032012-12-16
  • 0
    A simplification: suppose 0 is in the interior of your set X (why can I do this?). Then the definition of dimension becomes $n - \max\{\mathrm{rank}(A): Ax = 0\;\forall x\in X\}$. Does this look a little more like something you recognise? If not, what if I replace $X$ by $V = \mathrm{span}(X)$?2012-12-16
  • 0
    If $X$ is a vector subspace and $Ax=Ay$ for all $x,y\in X$, then $Ax=0$ for all $x\in X$ (take $y=0$). So the nullity of $A$ is at least $\dim(X)$, the ordinary dimension of $X$. Does that help?2012-12-16
  • 0
    @Ethan: Try to work it out in that special case, then. The definition is independent of basis choices (because matrix rank is), so start by choosing a basis for $X$ and extend it to a basis for $\mathbb R^n$. Consider how the matrix $A$ must look in order to satisfy the condition in the definition. What are the possible ranks of such a matrix? (In this special case where $X$ is assumed to be a subspace, it may help to consider in particular what $Ax=Ay$ means in the case where $x\in X$ is the zero vector).2012-12-16
  • 0
    Thanks, @user108903, Billy and Henning! Now I understand the definition when $X$ is a subspace. But when $X$ is a general subset, can you explain why consider$Ax=Ay$ for all $x,y∈X$? For example if $X$ is a translated subspace, then $Ax$ is not zero. But will the dim $X$ depend on how much it is translated? Intuitively, it shouldn't right?2012-12-16
  • 0
    No, translating $X$ should give the same answer. After all, if you translate $X$ by $v$ to get $X+v$ and $A$ is a matrix, then $A(X+v)=A(X)+Av$, so $A(X+v)$ is a singleton if and only if $A(X)$ is a singleton. Hence $\dim(X+v)=\dim(X)$.2012-12-16

1 Answers 1

3

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.

  • 0
    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?2012-12-16
  • 0
    @Ethan: See my edit. Orthogonality is not used anymore.2012-12-16
  • 0
    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$?2012-12-16
  • 0
    @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.2012-12-17
  • 0
    Thanks! In general, how is dim P determined from A and b?2012-12-17