# Linear map of Zonotopes [closed]

Consider a linear system with a map $A: \mathbb{R}^n \rightarrow \mathbb{R}^m$ such that $y = A x$ with $n \geq m$

The input space $x$ is constrained by a zonotope set $\mathcal{X} \subseteq \mathbb{R}^n$ in an $\mathcal{H}$-representation given

$$\mathcal{X} = \{ \, x \in \mathbb{R}^n\, | \, \, C_{x}^{T} x \leq d_{x} \, \}$$

We need to characterize the output variable $y$ by obtaining a set $\mathcal{Y} \subseteq \mathbb{R}^m$ such that

$$\mathcal{Y} = \{ \, y \in \mathbb{R}^m \, | \, \, y = A x ,\, x \in \mathcal{X} \,\}$$

WE know that the set $\mathcal{Y}$ is also a Zonotope and could be expressed in $\mathcal{H}$-representation as

$$\mathcal{Y} = \{ \, y \in \mathbb{R}^m\, | \, \, C_{y}^{T} y \leq d_{y} \, \}$$

Our questions are:

1. How to mathematically prove that $\mathcal{Y}$ is a Zonotope.
2. How to compute $\mathcal{Y}$ i.e. obtain $\{C_{y}, d_{y}\}$ given $A$ and $\{C_{x}, d_{x}\}$.

## 1 Answer

If $\mathcal{X}$ is the Minkowski sum of line segments $l_1,\ldots,l_k$, then $\mathcal{Y}$ is the Minkowski sum of line segments $Al_1,\ldots, Al_k$ (and hence a zonotope). As far as computing $C_y$ and $d_y$, this is a well known procedure for any polytope known as Fourier-Motzkin elimination.

• Any details or supporting materials will be appreciated. Dec 5 '14 at 14:32
• See for example the first part of Theorem 6.1 here math.lsa.umich.edu/~barvinok/polynotes669.pdf Dec 6 '14 at 22:04
• The material is really helpful but it has been presented for a simple projection on a subset of the input coordinates which is clearly easy using FM elimination. Are there any general approach to do that? Dec 15 '14 at 10:24