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$?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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$.
answered Aug 10, 2018 at 16:08
-
$\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$ Commented Aug 10, 2018 at 19:20
-
$\begingroup$ @TomWerner Quite right, I've just made the edit. $\endgroup$ Commented 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$ Commented 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$ Commented 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$ Commented Aug 12, 2018 at 7:26