Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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

2 Answers 2

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)

share|improve this answer

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.

share|improve this answer
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 at 2:40

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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