I'm not familiar with Fourier-Motzkin, so I don't know how different the following argument is from what one usually does, but it's direct and elementary (and constructive, it in principle produces the new constraints from the old ones).

The claim *is* trivial if $A\in\mathbb R^{n\times n}$ is invertible, and a general $A$ can be written as $A=PB$, with $B$ invertible and $P$ a projection, so we can focus on projections. We can in fact also assume that $P$ is a projection on a codimension $1$ subspace, say $P(y+\alpha e)=y$, for $y\perp e$ and $\alpha\in\mathbb R$. Suppose the polyhedron $Q$ is defined by the constraints $x\cdot n_j\le c_j$. We are then interested in
$$
S=P(Q)=\{ y\in\{e\}^{\perp} : y\cdot n_j \le c_j + d_j\alpha \:\textrm{ for some }\alpha\in\mathbb R \textrm{ and }j=1,\ldots, N \}
$$
(the same $\alpha$ for all $j$ of course).
We can further assume that $d_j=0$ or $\pm 1$. Call a constraint zero, positive, or negative according to the sign of $d_j$. The zero constraints are already of the desired type and can be ignored. The case of only positive (or only negative) constraints is trivial ($S=\{e\}^{\perp}$ in both cases). In the remaining case, I claim that $y\in S$ precisely if
$$
y\cdot (n_k^+ + n_j^-) \le c_k^+ + c_j^-\quad\quad\quad (1)
$$
for all choices of pairs $(k,j)$ of one positive and one negative condition. Indeed, we can rewrite (1) as
$$
y\cdot n_k^+ \le c_k^+ + \min (c_j^--y\cdot n_j^-) ,
$$
and then observe that the largest $\alpha$ that satisfies all negative constraints for a given $y$ is $\alpha=\min (c_j^--y\cdot n_j^-)$. It is now clear that (1) is equivalent to $y\in S$.

simpleproof that presumably works from first principles, i.e., from the definition he gives of polyhedron. My own feeling is that the question should be honored. $\endgroup$ – Todd Trimble♦ Jun 28 '14 at 23:37