# How to compute the image of a polyhedron under a linear transformation

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.

-
Perhaps you should add something on why you expect this not to be simply the complexity of computing $D=AC^{-1}$ (assuming $C$ is invertible). – joriki Aug 25 '12 at 8:00

I think the common approach is to use quantifier elimination. The image $P'$ is defined by the formula $$\exists x. Ax \leq b \land x' = Cx$$ By eliminating the quantifiers for the $x$-variables, you get a system of inequalities on the variables $x'$ that define the resulting polyhedron $P'$.

Quantifier elimination for linear arithmetic can be done by Ferrante and Rackoff's method [1, Chapter 7.3]. The complexity of this method is $2^{2^{pn}}$ for a formula of length $n$ and some fixed constant $p$ [1, Theorem 2.24].

[1] Bradley, A.R., Manna, Z.: The Calculus of Computation: Decision Procedures with Applications to Verification. Springer, Heidelberg (2007)

-

Here is a step-by-step instruction of the Ferrante and Rackoff's method as pointed out in the previous post. Let $F[x] = Ax \leq b \land x' = Cx$

1. $F_1[x] = (Ax < b \lor Ax = b)\land x' = Cx$
2. $F_2[x] = (x < A^{-1}b \lor x = A^{-1}b)\land C^{-1}x' = x$
3. $F_3[x] = F_{-\infty} \lor F_{+\infty} \lor F_S$

$F_{-\infty} = (\top \lor \bot) \land \bot = \bot$

$F_{+\infty} = (\bot \lor \bot) \land \bot = \bot$

Let $S=\{A^{-1}b, C^{-1}\}$

$F_{S} = F_2[A^{-1}b] \lor F_2[\frac{A^{-1}b+C^{-1}}{2}] \lor F_2[C^{-1}]$

$F_2[A^{-1}b] = (\bot \lor \top) \land (C^{-1}x'=A^{-1}b) = (C^{-1}x'=A^{-1}b)$

$F_2[C^{-1}x'] = ((C^{-1}x' < A^{-1}b) \lor (C^{-1}x'=A^{-1}b)) \land \top = (C^{-1}x' < A^{-1}b) \lor (C^{-1}x'=A^{-1}b)$

$F_2[\frac{A^{-1}b+C^{-1}x'}{2}] = ((C^{-1}x' < A^{-1}b) \lor (C^{-1}x'=A^{-1}b)) \land (C^{-1}x'=A^{-1}b)) = \bot \land (C^{-1}x'=A^{-1}b) = \bot$

We have therefore

$F_3[x] = (C^{-1}x'=A^{-1}b) \lor (C^{-1}x' < A^{-1}b)$

The conclusion is that $F_3[x] = (C^{-1}x' \leq A^{-1}b)$ is equivalent to $F[x]$, so that we can finally use this result to write

$P' = \{ x ~|~ D x \leq e \}, D= C^{-1}, e = A^{-1}b$.

The complexity of this depends therefore on inverting $C \in R^{k \times n}$, inverting $A \in R^{m \times n}$ and multiplication of $A^{-1} \in R^{n \times m}$ with $b \in R^{m}$. However, since normally you would solve the pseudo inverse by computing the SVD, given an exact count of arithmetic operations seems only be possible in special cases.

-
This cannot be true. Since this implies polytope $P'$ has at most $n$ facets. But there are examples where after a projection, the polytope has $2^n$ facets. lall.stanford.edu/data/engr210b_0405/… see slide 15 – Chao Xu Jan 31 '15 at 2:40