Let $X\subseteq\mathbb{R}^n$ be a convex set. Let $\pi{:}\ X\to\mathbb{R}^m$ be a linear map, with $m<n$ (for example, a projection). Let $\pi^{-1}(y)=\{x\in X\mid\pi(x)=y\}$ denote the inverse of $\pi$. If $F$ is a face of $\pi(X)$, what is the set $\pi^{-1}(F)$? Is it a face of $X$?

up vote 6 down vote accepted

The question in the title is not how I'd phrase your question. I'd say what you're asking is "Is the preimage of a face under an affine map a face?", and the answer to that is yes.

The argument is simple. Let $f : X \rightarrow Y$ be an affine map (in your case, $\pi : X \rightarrow \pi(X)$), and let $F$ be a face of $Y$. To show that $f^{-1}(F)$ is a face of $X$, let $x,x' \in X$ and $\alpha \in [0,1]$ such that the convex combination $\alpha x + (1 -\alpha)x' \in f^{-1}(F)$. Because $f$ is affine, $\alpha f(x) + (1 - \alpha)f(x') \in F$. We then use the fact that $F$ is a face to deduce that $f(x), f(x') \in F$, and therefore $x,x' \in f^{-1}(F)$, proving $f^{-1}(F)$ is a face. (In case of confusion, I will state that I consider the empty set to be a face.)

For completeness, I'll say that the answer to the question I get from a natural interpretation of your title is no (is the projection of a face a face). Take $X$ to be an equilateral triangle and take $\pi$ to be the projection onto its base $Y$. The apex of the triangle is an extreme point, and therefore a face of $X$, but it projects down to a point half-way between the two extreme points of the base $Y$, which is not a face of $Y$.

  • Many thanks, I did not expect the proof would be so simple. I rephrased the title as you suggest. Note the typo in your proof: in the last sentence there should be "$x,x'\in f^{-1}(F)$, proving that $f^{-1}(F)$ is a face". – Tom Werner Aug 10 at 19:20
  • @TomWerner Quite right, I've just made the edit. – Robert Furber Aug 10 at 19:24
  • Still there is something I do not understand. Suppose $F$ is a face of $Y$ that back-projects to a face $E=f^{-1}(F)$ of $X$. Then, obviously, $f(E)=F$. But it is known that a projection of a polytope can have more faces than the original polytope. So sometimes it must happen that two different faces of $Y$, say $F$ and $F'$, back-project to a single face of $X$, i.e., $f^{-1}(F)=E=f^{-1}(F')$. But this contradicts the fact that $f$ is a function, because $f(E)$ would be ambiguous. Where am I doing a mistake? – Tom Werner Aug 11 at 11:23
  • 1
    @TomWerner Can you show me an explicit example where the projection has more faces? I can't think of one. – Robert Furber Aug 12 at 4:03
  • As I think of it, it cannot. Maybe that's the mistake. It is surely true of facets, following from Fourier-Motzkin elimination (see, eg, mathoverflow.net/questions/260107/…), but apparently not of faces. My argument above thus only proves that facets not always back-project to facets - which is obvious. – Tom Werner Aug 12 at 7:26

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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