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
    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! In general, how is dim$P$determined from$A$and b?2012-12-17