Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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
up vote 3 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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