11
$\begingroup$

Let $n$ line sets be $\mathcal{S}_i=\{a\mathbf{h}_i:0 \le a \le 1\}$, for $1 \le i \le n$, where $\{\mathbf{h}_1,\cdots,\mathbf{h}_n\}$ is a vector group of rank $r$ in the $r$-dimensional Euclidean space. Define the Minkowski sum of two sets as $\mathcal{S}_1+\mathcal{S}_2=\{\mathbf{s}_1+\mathbf{s}_2:\mathbf{s}_1\in\mathcal{S}_1,~\mathbf{s}_2\in\mathcal{S}_2\}$. How to compute the $r$-dimensional volume of $\mathcal{S}_1+\cdots+\mathcal{S}_n$?

$\endgroup$
13
$\begingroup$

Let $M$ be the matrix whose rows are the vectors $\boldsymbol{h_i}$. Then the $r$-dimensional volume of $\mathcal{S}=\mathcal{S}_1+\cdots+\mathcal{S}_n$ is equal to the sum of the absolute values of the $r\times r$ minors of $M$. I don't know who originally showed this, but one can show that $\mathcal{S}$ can be tiled with $r$-dimensional parallelotopes whose volumes are the $r\times r$ minors. This follows for instance from the proof of Lemma 2.1 here.

$\endgroup$
1
  • $\begingroup$ Thanks for your explanation. This problem can be further extended as a new problem I asked several minutes ago. $\endgroup$ – Ryan Chen Jan 3 '20 at 1:33
13
$\begingroup$

The keyword you are looking for is "zonotope", which is defined to be the Minkowski sum of line segments. An early reference for zonotope is: P. McMullen, “On zonotopes”, Transactions of the American Mathematical Society, Vol. 159, 1971.

Following your notation, the $r$-dimensional volume of the zonotope $\mathcal{S}_{1} + ... + \mathcal{S}_{n}$ is equal to

$$\displaystyle\sum_{1\leq i_{1} < i_{2} ... < i_{r}\leq n} \big\vert{\rm{det}}\left(\mathbf{h}_{i_{1}},\mathbf{h}_{i_{2}},...,\mathbf{h}_{i_{r}}\right)\big\vert.$$

For reference, see eqn. (57) in "Combinatorial Properties of Associated Zonotopes" by G.C. Shephard, Canadian Journal of Mathematics, 1974. In that paper, there is an extra factor $2^{r}$ in front of the above expression since the line segments there are defined by $\{a\mathbf{h}_{i} : -1\leq a \leq 1\}$ instead of the OP's convention: $0\leq a \leq 1$. In the very end of this paper, Shephard credits McMullen for drawing attention to this formula. The same formula also appears as Exercise 7.19 in G.M. Ziegler, Lectures on Polytopes, Vol. 152, Springer, 2012; screenshot below: enter image description here

$\endgroup$
3
  • $\begingroup$ Sorry for essentially repeating Richard's answer, his answer came before I finished typing. $\endgroup$ – Abhishek Halder Jan 2 '20 at 3:37
  • 1
    $\begingroup$ I don't have access at the moment to the paper of Shephard, but presumably he is looking at line segments from $-\boldsymbol{v_i}$ to $\boldsymbol{v_i}$, not $0$ to $\boldsymbol{v_i}$. That is why there is an extra factor of $2^d$. If you take $\boldsymbol{h_i}$ to be the $i$th unit coordinate vector in Ryan Chen's question, then the zonotope is a unit cube of volume 1, not $2^r$. The matrix $M$ is the $r\times r$ identity matrix. $\endgroup$ – Richard Stanley Jan 2 '20 at 14:33
  • $\begingroup$ @RichardStanley: You are right, edited. $\endgroup$ – Abhishek Halder Jan 2 '20 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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