4
$\begingroup$

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$?

$\endgroup$

1 Answer 1

6
$\begingroup$

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$.

$\endgroup$
5
  • $\begingroup$ 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". $\endgroup$
    – Tom Werner
    Aug 10, 2018 at 19:20
  • $\begingroup$ @TomWerner Quite right, I've just made the edit. $\endgroup$ Aug 10, 2018 at 19:24
  • $\begingroup$ 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? $\endgroup$
    – Tom Werner
    Aug 11, 2018 at 11:23
  • 1
    $\begingroup$ @TomWerner Can you show me an explicit example where the projection has more faces? I can't think of one. $\endgroup$ Aug 12, 2018 at 4:03
  • $\begingroup$ 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. $\endgroup$
    – Tom Werner
    Aug 12, 2018 at 7:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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