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$?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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.
answered Jan 2, 2020 at 3:29
-
$\begingroup$ Thanks for your explanation. This problem can be further extended as a new problem I asked several minutes ago. $\endgroup$– RyanChanJan 3, 2020 at 1:33
$\begingroup$
$\endgroup$
3
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:
-
$\begingroup$ Sorry for essentially repeating Richard's answer, his answer came before I finished typing. $\endgroup$ Jan 2, 2020 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$ Jan 2, 2020 at 14:33
-
$\begingroup$ @RichardStanley: You are right, edited. $\endgroup$ Jan 2, 2020 at 17:52