Mixed Volume
Posted by Tom Leinster
Take $2$ convex bodies in $\mathbb{R}^2$, or $3$ convex bodies in $\mathbb{R}^3$, or, more generally, $n$ convex bodies in $\mathbb{R}^n$. Mixed volume assigns to each such family a single real number.
The mixed volume of convex bodies $A_1, \ldots, A_n$ is written as $V(A_1, \ldots, A_n) \in \mathbb{R}$, and it’s uniquely characterized by the following three properties:
- Volume: $V(A, \ldots, A) = Vol(A)$, for any convex body $A$
- Symmetry: $V$ is symmetric in its arguments
- Multiadditivity: $V(A_1 + \tilde{A}_1, A_2, \ldots, A_n)$ equals $V(A_1, A_2, \ldots, A_n) + V(\tilde{A}_1, A_2, \ldots, A_n)$ for any convex bodies $A_i$ and $\tilde{A}_1$, where $+$ denotes Minkowski sum.
This looks rather like the characterization of determinant: $det$ is unique satisfying $det(I) = 1$, antisymmetry, and multilinearity. One difference is that we have symmetry rather than antisymmetry. But a much bigger difference is that where determinant assigns a number to $n$ vectors in $\mathbb{R}^n$, mixed volume assigns a number to $n$ convex bodies in $\mathbb{R}^n$.
But maybe you don’t find the unique characterization satisfying. What is mixed volume?
First I should be precise about what I mean by ‘convex body’. I simply mean a compact, convex, nonempty subset of $\mathbb{R}^n$. (Often people include the condition that the interior is nonempty, but I’m not requiring that.) You might raise an eyebrow at the word ‘nonempty’, but it really does matter.
In a moment I’ll give you lots of examples of mixed volume. Later on, I’ll give you the definition, and I’ll also list some of the other properties that it satisfies (apart from the three that characterize it uniquely). But the examples will be easier to understand if I tell you one of those properties right now:
4. Translation-invariance in each coordinate: $V(x + A_1, A_2, \ldots, A_n) = V(A_1, A_2, \ldots, A_n)$ for any convex bodies $A_i$ and any $x \in \mathbb{R}^n$.
Since $V$ is symmetric, this implies that
$V(x_1 + A_1, \ldots, x_n + A_n) = V(A_1, \ldots, A_n).$
In other words, sliding the bodies around doesn’t change the mixed volume. (Changing their orientations usually does, as we’ll see.) Knowing this helps us to speak more freely. If, say, $n = 2$, then I can say ‘let $A_1$ be a $3 \times 4$ rectangle with edges parallel to the coordinate axes’ — I don’t need to say where in the plane it lives.
Examples of mixed volume
Example I’ve already mentioned that $V(A, \ldots, A) = A$ for any convex body $A$. Now suppose that our $n$ convex bodies are not necessarily equal, but are all scalings of one another. Given a convex body $B$ and scalars $t_1, \ldots, t_n \gt 0$, we have
$V(t_1 B, \ldots, t_n B) = t_1 \cdots t_n Vol(B)$
where $t_i B$ means $\{ t_i b | b \in B\}$. To put it another way: if $A_1, \ldots, A_n$ are all scalings of one another then
$V(A_1, \ldots, A_n) = geometric mean of Vol(A_1), \ldots, Vol(A_n).$
Example The previous example is misleading, because it doesn’t reveal that in general, mixed volume depends on how the convex bodies interact with one another. But a simple example with $n = 2$ will show this. Let $A$ be an $a \times b$ rectangle and $B$ a $c \times d$ rectangle, both with their edges parallel to the coordinate axes. Then
$V(A, B) = \frac{1}{2}(a d + b c).$
Here’s a picture:
The mixed volume — which for $n = 2$ could be called ‘mixed area’ — is not derived from the areas of $A$ and $B$, shown in grey. Instead, it’s the (arithmetic) mean of the areas of the two red rectangles.
The formula for $V(A, B)$ looks a bit like the determinant formula $a d - b c$…. We’ll come back to this.
Example Let’s generalize the previous example to higher dimensions. Rectangles, then, will become cuboids. Previously we established that the word ‘cuboid’ is known to British schoolchildren and comedians, but not American math professors (I’m teasing, John). I believe American English uses some quaint term such as ‘orthogonal parallelepiped’. Anyway: let $n$ be any natural number, let $(a_{i j})$ be an $n \times n$ matrix of nonnegative reals, and for $i = 1, \ldots, n$, let
$A_i = [0, a_{i 1}] \times \cdots \times [0, a_{i n}] \subseteq \mathbb{R}^n.$
(Or you could take $A_i$ to be a translate of this; it doesn’t matter.) Then
$V(A_1, \ldots, A_n) = \frac{1}{n!} \sum_{\sigma \in S_n} a_{1, \sigma(1)} \cdots a_{n, \sigma(n)}.$
Again, this can usefully be compared to the determinant formula
$det((a_{i j})) = \sum_{\sigma \in S_n} sgn(\sigma) a_{1, \sigma(1)} \cdots a_{n, \sigma(n)}.$
Apart from the constant factor, the only difference is in the signs. This corresponds to mixed volume being symmetric and determinant being antisymmetric.
I said before that whereas determinant assigns a number to any $n$ vectors in $\mathbb{R}^n$, mixed volume assigns a number to any $n$ convex bodies in $\mathbb{R}^n$. Actually, every vector gives rise to a convex body: it’s the axis-parallel cuboid whose long diagonal is $v$. For example, the vector $\mathbf{a}_i = (a_{i 1}, \ldots, a_{i n})$ gives rise in this way to the cuboid $A_i$. In the last paragraph, we compared the determinant of the $n$ vectors $\mathbf{a}_1, \ldots, \mathbf{a}_n$ with the mixed volume of the $n$ convex bodies $A_1, \ldots, A_n$ they give rise to.
Minkowski’s theorem
I still haven’t told you the definition of mixed volume. One reason why not is that in order to even state the definition, we first need to know the following theorem of Minkowski.
Theorem (Minkowski) Let $k$ and $n$ be natural numbers. Fix convex bodies $A_1, \ldots, A_k$ in $\mathbb{R}^n$. Then the function
$(t_1, \ldots, t_k) \mapsto Vol(t_1 A_1 + \cdots + t_k A_k)$
($t_i \geq 0$) is a polynomial, homogeneous of degree $n$.
If you understand Minkowski’s theorem, you understand mixed volume. So I’ll do my best to explain it.
The first thing to notice is that whereas we had been discussing $n$ bodies in $n$-dimensional space, we’re now discussing $k$ bodies in $n$-dimensional space. Of course, you can take $k = n$, but it’s probably easier to understand Minkowski’s theorem if we treat it at its natural level of generality.
Now let’s look for the first nontrivial case.
For $k = 0$, the theorem is trivial.
For $k = 1$, it says that given any convex body $A$ in $\mathbb{R}^n$, the function
$t \mapsto Vol(t A)$
($t \geq 0$) is a polynomial in $t$, homogeneous of degree $n$. That’s true, and doesn’t even use convexity: the polynomial is $Vol(A) \cdot t^n$.
It’s when $k = 2$ that things start to get interesting. The statement is that for convex bodies $A, B \subseteq \mathbb{R}^n$, the function
$(s, t) \mapsto Vol(s A + t B)$
is a homogeneous polynomial of degree $n$. Because $Vol$ itself is homogeneous of degree $n$, we might as well fix $s$ to be $1$. Then Minkowski is telling us that
$t \mapsto Vol(A + t B)$
is a polynomial of degree $\leq n$.
Why is that so? The picture below shows an example with $n = 2$. Here $A$ is the blue quadrilateral, $t B$ is any one of the green egg shapes, and $A + t B$ is the whole thing, including the grey parts. (The four copies of $t B$ that I’ve chosen to draw are $a + t B$ for the four vertices $a$ of $A$.)
Minkowski’s theorem implies that the area of the whole thing is a (possibly degenerate) quadratic in $t$.
So let’s try to understand some special cases. I’m sticking with $k = 2$: that is, I’m trying to explain why $Vol(A + t B)$ is a polynomial in $t$ of degree at most $n$, whenever $A$ and $B$ are convex bodies in $\mathbb{R}^n$.
Example Take $B$ to be a singleton $\{b\}$. Then $A + t B = A + t b$, a translate of $A$. Hence $Vol(A + t B) = Vol(A)$ for all $t$. This is certainly a polynomial in $t$ of degree $\leq n$.
Example Take $B = A$. Then
$Vol(A + t B) = Vol((1 + t)A) = Vol(A)\cdot(1 + t)^n,$
which is indeed a polynomial of degree $\leq n$.
Example Choose a point $b \in \mathbb{R}^n$ and take $B$ to be the straight line segment $[0, b]$ from $0$ to $b$. Then
$Vol(A + t B) = Vol(A + [0, t b]).$
Here’s a picture with $n = 2$ and with $b$ somewhere on the positive $x$-axis:
As before, $A$ is in blue. It’s clear that the area of the grey part is proportional to the horizontal distance over which $A$ has been smeared out — that is, proportional to $t$. This gives
$Vol(A + t B) = Vol(A) + c t$
for some constant $c$, and again, this is a polynomial in $t$ of degree $\leq n$.
Example Take $B$ to be the unit ball. Then $A + t B$ is the closed $t$-neighbourhood of $A$, that is, the set of all points $x$ such that $inf_{a \in A} d(x, a) \leq t$. And there’s a famous theorem giving the volume of the $t$-neighbourhood: Steiner’s theorem.
By law, every explanation of Steiner’s theorem must contain the following diagram:
Staring at this picture should reveal to you the following truth: for convex bodies $A$ in $\mathbb{R}^2$,
$Vol(A + t B) = Vol(A) + perimeter(A)\cdot t + \pi t^2.$
This is a polynomial in $t$ of degree $2$. There’s a similar formula in higher dimensions. The coefficients are, up to a constant factor, the intrinsic volumes of $A$.
That’s enough explanation; it’s time to give you the definition.
The definition of mixed volume
Take $n$ convex bodies in $\mathbb{R}^n$, say $A_1, \ldots, A_n$. Minkowski’s theorem states that
$Vol(t_1 A_1 + \cdots + t_n A_n)$
is a polynomial in $t_1, \ldots, t_n \geq 0$, homogeneous of degree $n$. The mixed volume $V(A_1, \ldots, A_n)$ is the coefficient of $t_1 t_2 \cdots t_n$ in this polynomial, divided by $n!$.
This definition is apt to look mysterious. For a start, why this particular coefficient? It’s because, as it turns out, mixed volume tells you all the coefficients.
The precise statement is as follows. Take any natural numbers $k$ and $n$, and any $k$ convex bodies $A_1, \ldots, A_k$ in $\mathbb{R}^n$. Then
$Vol(t_1 A_1 + \cdots + t_k A_k) = \sum_{i_1, \ldots, i_n = 1}^k V(A_{i_1}, \ldots, A_{i_n}) t_{i_1} \cdots t_{i_n}.$
So if someone put an implant in your brain that enabled you to calculate any mixed volume, you’d also be able to calculate the Minkowski polynomial of any family of convex bodies.
Example Take $k = n = 2$. Then this tells us that
$Vol(t_1 A_1 + t_2 A_2) = V(A_1, A_1) t_1^2 + 2V(A_1, A_2) t_1 t_2 + V(A_2, A_2) t_2^2.$
But $V(A_i, A_i) = Vol(A_i)$, so what this essentially says is that
$Vol(A + t B) = Vol(A) + 2V(A, B) t + Vol(B) t^2.$
You can check this in some of the examples above.
Another way to express this equation is:
$Vol(t_1 A_1 + \cdots + t_k A_k) = \sum_{n_1 + \cdots + n_k = n} \binom{n}{n_1, \ldots, n_k} V(A_1^{n_1}, \ldots, A_k^{n_k}) t_1^{n_1} \cdots t_k^{n_k}.$
Here $\binom{n}{n_1, \ldots, n_k}$ is the multinomial coefficient $\frac{n!}{n_1! \cdots n_k!}$, and by definition,
$V(A_1^{n_1}, \ldots, A_k^{n_k}) = V(A_1, \ldots, A_1, \ldots, A_k, \ldots, A_k)$
where each $A_i$ appears $n_i$ times. So, mixed volumes with repeated arguments are important. In this respect, mixed volume is unlike determinant: because of antisymmetry, determinants with repeated arguments are trivial.
The unique characterization
I began by stating that mixed volume is uniquely characterized by three properties: the volume property ($V(A, \ldots, A) = Vol(A)$), symmetry, and multiadditivity. It’s easy to prove that when $n = 2$, there’s at most one function $V$ satisfying the three properties. It’s a bit like the proof that in an inner product space, the norm determines the inner product. Indeed, if $V$ satisfies the properties then by multiadditivity we have
$V(A + B, A + B) = V(A, A) + V(A, B) + V(B, A) + V(B, B),$
and so by symmetry and the volume property,
$V(A, B) = \frac{1}{2}\Bigl\{Vol(A + B) - \bigl[Vol(A) + Vol(B)\bigr]\Bigr\}.$
(This is the same as the formula in the last example, rearranged and with $t = 1$.) So mixed volume can be expressed in terms of ordinary volume and Minkowski sums.
You can do the same kind of thing in higher dimensions. When $n = 3$, for instance, you get
$V(A, B, C) = \frac{1}{3!} \Bigl\{ V(A + B + C) - \bigl[V(A + B) + V(A + C) + V(B + C)\bigr] + \bigl[V(A) + V(B) + V(C)\bigr] \Bigr\}.$
The formula for general $n$ is now exactly as you’d guess.
That’s a very explicit formula for mixed volume, though it’s not clear that it gives much insight. By way of analogy, does the formula
$a b = \frac{1}{2}\bigl\{[a + b]^2 - [a^2 + b^2]\bigr\}$
give you a lot of insight into multiplication of real numbers? It’s probably important in some contexts, and it’s interesting that multiplication can be built out of addition, squaring and halving. But it’s not how most of us think about multiplication.
Further properties of mixed volume
In the absence of a single really compelling way to understand mixed volume, I’ve described several ways in which it can be half-understood. There’s the unique characterization by three properties, there’s the analogy with determinants, there are examples, there’s the definition in terms of the polynomial in Minkowski’s theorem, and there’s the formula we just met, giving mixed volume as a linear combination of ordinary volumes.
I’ll finish with another way of half-understanding it. It’s a long list of properties that mixed volume satisfies. For completeness, I’ll begin with the four that we’ve already seen.
- Volume: $V(A, \ldots, A) = Vol(A)$
- Symmetry: $V$ is symmetric in its arguments
- Multiadditivity: $V(A_1 + \tilde{A}_1, A_2, \ldots, A_n) = V(A_1, A_2, \ldots, A_n) + V(\tilde{A}_1, A_2, \ldots, A_n)$
- Translation-invariance in each coordinate: $V(x + A_1, A_2, \ldots, A_n) = V(A_1, A_2, \ldots, A_n)$
- Isometry-invariance: $V(g A_1, \ldots, g A_n) = V(A_1, \ldots, A_n)$ for any $g$ in the isometry group of $\mathbb{R}^n$
- Special linear invariance: $V(g A_1, \ldots, g A_n) = V(A_1, \ldots, A_n)$ for any $g \in SL(n, \mathbb{R})$
- Scaling: $V(t A_1, A_2, \ldots, A_n) = t V(A_1, A_2, \ldots, A_n)$ for any $t \geq 0$
- Singletons: $V(\{a\}, A_2, \ldots, A_n) = 0$
- Monotonicity: $V(A_1, A_2, \ldots, A_n) \leq V(\tilde{A}_1, A_2, \ldots, A_n)$ whenever $A_1 \subseteq \tilde{A}_1$
- Nonnegativity: $V(A_1, \ldots, A_n) \geq 0$
- Continuity: $V$ is continuous with respect to the Hausdorff metric on convex bodies
- Valuation in each coordinate: $V(A_1 \cup \tilde{A}_1, A_2, \ldots) = V(A_1, A_2, \ldots) + V(\tilde{A}_1, A_2, \ldots) - V(A_1 \cap \tilde{A}_1, A_2, \ldots)$ as long as $A_1 \cup \tilde{A}_1$ is convex.
Perhaps mixed volume can be summarized as a mutual measure of size. The properties listed all fit well with this description. For example, the last one says that coordinatewise, mixed volume is a valuation or finitely additive measure. The analogy between mixed volume and determinants points in the same direction: the determinant of $n$ vectors in $\mathbb{R}^n$ is, after all, the volume of the parallelepiped that they generate. But the direct geometric significance of mixed volume remains, to me, elusive.
Re: Mixed Volume
I’ll add a puzzle.
I described the analogy between mixed volume and determinant. Now, in linear algebra, the determinant of an operator is often best thought of as the product of its eigenvalues, taken with their algebraic multiplicities. But the spectrum — that is, the set-with-multiplicities of eigenvalues — is really a more fundamental object than the determinant. What is the analogue of the spectrum in the world of convex bodies?
I don’t know the answer.