Suppose $P$ is a polyhedron whose representation as a system of linear inequalities is given to us: $ P = \{ x ~|~ Ax \leq b\}$ Define $P'$ be the image of $P$ under the linear transformation which maps $x$ to $Cx$:
$ P' = \{ Cx ~|~ x \in P \}.$ Given $A,b,C$, our goal is to compute a representation of $P'$ as a system of linear inequalities, i.e., to compute $D,e$ satisfying $ P' = \{ x ~|~ D x \leq e \}.$ What is the complexity of this problem (i.e., how many arithmetic operations or bit operations are required)?
Let us adopt the convention that $A \in R^{m \times n}$ while $C \in R^{k \times n}$ so the answer should be in terms of $m,n,k$. Further, one may suppose that entries of $P$ are rational numbers whose numerators and denominators take $B$ bits to specify, so that in the bit-model answers should be in terms of $B$ as well.