Exterior Algebra #7: Simplex Volumes and Boundaries

March 2, 2019

More on simplexes in oriented projective geometry (OPG), since they are connected to everything else. See the previous post for details on OPG.

In this article I am switching back to the exterior algebra notations, so \(\^\) is the wedge product and the “meet” operation, and \(\vee\) is the “join” operation.

As a reminder, the objects we’re discussing are “oriented simplexes” in \(\bb{O}^n\). A \(k\)-simplex is a \(k\)-dimensional line segment (\(0\)=point, \(1\)=line segment, \(2\)=triangle, \(3\)=tetrahedron, etc), which is constructed from \((k+1)\) points.

We can map simplexes to equivalence classes of multivectors in \(\bb{R}^{n+1}\), where two multivectors are the same object if they differ by a positive scalar coefficient. The requirement that the scalar be positive is what makes our geometry oriented and causes the representation to be equivalent to exterior algebra. In particular a \(k\)-simplex maps to in homogenous coordinates to the wedge product of \((k+1)\)-vectors in \(\^^{k+1} \bb{R}^{n+1}\).

I like to use \(\b{w}\) as the unit vector corresponding to the projective/homogenous coordinate, so for instance the point \((a,b)\) in \(\bb{O}^2\) is represented by the vector \((1, a, b) = \b{w} + a \b{x} + b \b{y}\) in \(\bb{R}^3\). A \(k\)-simplex in \(\bb{O}^n\) may be written as a list of points \(\alpha = (p_0 p_1 \ldots p_k)\), and its representation in homogenous coordinates is the multivector \(\alpha = (\b{w} + p_0) \^ (\b{w} + p_1) \^ \ldots (\b{w} + p_k) \in \^^{k+1} \bb{R}^{n+1}\).

Now let’s talk about the volumes of simplexes.

1. The Volume of a Simplex

We’ll start with a triangle in the plane as an illustrative eample. In \(\bb{R}^2\) the usual \(\frac{1}{2} \text{base} \times \text{height}\) formula translates into vectors as

\[\text{area}(abc) = \frac{1}{2}(\vec{b}-\vec{a}) \^ (\vec{c}-\vec{a})\]

Which produces a single bivector with basis element \(\b{x \^ y}\) and coefficient equal to the signed area.

This is a bit weird, though, because it treats the vector \(\vec{a}\) differently from the other two. It seems like we should be able to write down a version that treats all three vectors symmetrically, and indeed we can:

\[\text{area}(abc) = \frac{1}{2}(\vec{a} \^ \vec{b} + \vec{b} \^ \vec{c} + \vec{c} \^ \vec{a})\]

Which you can check is trivially equivalent to the previous formula.

That formula can be visualized in an interesting way by working in homogenous coordinates in \(\bb{R}^{3}\). We imagine that the triangle is drawn on the plane given by \(w = 1\), so it’s really one face of the tetrahedron \((\mathcal{O}, \b{w} + \vec{a}, \b{w} + \vec{b}, \b{w} + \vec{c})\). Since this tetrahedron is created by three vectors from the origin, its oriented volume is given by their wedge product:

\[\text{vol}(\mathcal{O}abc) = \frac{1}{3!} (\b{w} + \vec{a}) \^ (\b{w} + \vec{b}) \^ (\b{w} + \vec{c})\]

(Without the \(\frac{1}{3!}\) factor it would instead be the volume of the paralleliped with those vectors as its sides.)

We can expand this as:

\[\text{vol}(\mathcal{O}abc) = \frac{1}{3!} [ \cancel{\vec{a} \^ \vec{b} \^ \vec{c}} + \b{w} \^ (\vec{a} \^ \vec{b} + \vec{b} \^ \vec{c} + \vec{c} \^ \vec{a})]\]

The first term cancels because it’s the wedge product of three vectors in \(\bb{R}^2\), which is zero. The area has shown up in the second term on the right. \(\b{w}\) may be regarded as the “height” of the tetrahedron, while \((\vec{a} \^ \vec{b} + \vec{b} \^ \vec{c} + \vec{c} \^ \vec{a})\) is the multivector for its base, so really what this says is

\[\text{vol}(\mathcal{O}abc) = \frac{1}{3} \b{w} \^ \text{area}(abc)\]

Which is a multivector version of the volume of a tetrahedron \(V = \frac{1}{3} bh\) (compare to a triangle’s area \(A = \frac{1}{bh}\)).

We might want to finish up by contracting to remove the \(\frac{1}{3} \b{w}\) coefficient:

\[\begin{aligned} \text{area}(abc) &= 3 \b{w} \cdot \text{vol}(\mathcal{O}abc) \\ &= 3 \b{w} \cdot [\frac{1}{3!} (\b{w} + \vec{a}) \^ ( \b{w} + \vec{b}) \^ (\b{w} + \vec{c})] \\ &= \frac{1}{2} (\vec{b} - \vec{a}) \^ (\vec{c} - \vec{a}) \end{aligned}\]

For a general \(k\) simplex in \(n\)-space, this formula becomes:

\[\begin{aligned} \text{vol}_k(p_1, p_2, \ldots p_{k+1}) &= (k+1) \b{w} \cdot \text{vol}_{k+1} (\mathcal{O}, \b{w} + p_1, \b{w} + p_2, \ldots \b{w} + p_{k+1}) \\ &= (k+1) \b{w} \cdot [\frac{1}{(k+1)!} \bigwedge_{1}^{k+1} (\b{w} + \vec{p}_i)] \\ &= \frac{1}{k!} \b{w} \cdot \bigwedge_{1}^{k+1} (\b{w} + \vec{p}_i) \end{aligned}\]

(I’ve added subscripts to the \(\text{vol}\)s as a reminder of what type they’re expecting: a \(2\)-volume is an area, a \(3\)-volume is a volume, etc.)

When \(k = n\), we can write this as the determinant of the \((n+1) \times (n+1)\)-matrix spanned by the \((1, \vec{p}_i)\):

\[\text{vol}(p_1 p_2 \ldots p_{n+1}) = \frac{1}{n!} \un{n+1}{\det} \begin{pmatrix} 1 & \vec{p}_1 \\ 1 & \vec{p}_2 \\ \vdots & \vdots \\ 1 & \vec{p}_{n+1} \end{pmatrix} =\frac{1}{n!} \bigwedge^{n+1} \begin{pmatrix} 1 & \vec{p}_1 \\ 1 & \vec{p}_2 \\ \vdots & \vdots \\ 1 & \vec{p}_{n+1} \end{pmatrix}\]

For example:

\[\text{vol}(a,b,c) = \frac{1}{2!} \begin{pmatrix} 1 & a_x & a_y \\ 1 & b_x & b_y \\ 1 & c_x & c_y \end{pmatrix}\]

When \(k < n\), the volume \(k\)-simplex can still be computed by the same formula. However, the result is a multivector with multiple components instead of a scalar, representing an oriented volume in the larger space. Keep in mind that we can only regard \(n\)-volumes as scalars because they can be compared against the orientation of the enclosing space (which is specified by the order we write our coordinates). For a \(k \neq n\) volume, like the area of a arbitrary triangle floating in a space, there is nothing intrinsic to compare its orientation to. In that case we can either leave the result as a multivector or take its magnitude to get a scalar value (which will necessarily be positive, i.e. unoriented).

In higher dimensions the \(\vec{a} \^ \vec{b} \^ \vec{c}\) term will not necessarily be zero, so when computing the volume of \(k\)-simplexes the contraction with \(\b{w}\) is critical or you will get the wrong answer. For example here’s that triangle \((abc)\) floating in space in \(\bb{R}^3\):

\[\begin{aligned} \text{area}(abc) &= \b{w} \cdot \frac{1}{2!}(\b{w} + \vec{a}) \^ (\b{w} + \vec{b}) \^ (\b{w} + \vec{c}) \\ &= \frac{1}{2!} \b{w} \cdot [\vec{a} \^ \vec{b} \^ \vec{c} + \b{w} \^ (\vec{a} \^ \vec{b} + \vec{b} \^ \vec{c} + \vec{c} \^ \vec{a} ] \\ &= \frac{1}{2!} (\vec{a} \^ \vec{b} + \vec{b} \^ \vec{c} + \vec{c} \^ \vec{a}) \\ &= \frac{1}{2!} (\vec{b} - \vec{a}) \^ (\vec{c} - \vec{a}) \end{aligned}\]

The \(\b{w} \cdot\) prevents us from including the \(\vec{a} \^ \vec{b} \^ \vec{c}\) term, which was zero in 2d but in 3d is the volume of the tetrahedron \((\mathcal{O}abc)\), where that \(\mathcal{O}\) refers to the \(\bb{R}^3\) origin, not the homogenous one. It’s a meaningful quantity, but not for computing the area.1

In summary, to compute multivector areas of simplexes in homogenous coordinates:

\[\boxed{\text{vol}(p_1 p_2 \ldots p_{k+1}) = \b{w} \cdot \frac{1}{k!} \bigwedge_{i=1}^{k+1} (\b{w} + p_i)}\]

By the way: even if all of this is elegant and symmetric and all those things we like, it’s not necessarily efficient. It will in most cases be more better to use the \(\frac{1}{k!} (p_1 - p_0) \^ \ldots (p_k - p_0)\) formula to actually compute volumes, since it is a product of only \(k\) vectors instead of \(k+1\). These homogenous representations are useful for intuition, though, because they lead us to an explicit multivector representation of the bounday operator.

2. The Boundary Operator

Each term in the expression \(\vec{a} \^ \vec{b} + \vec{b} \^ \vec{c} + \vec{c} \^ \vec{a}\) corresponds to one of the edges of the triangle \((abc)\). For higher \(k\)-simplexes this pattern continues, with each term corresponding to one of the oriented \((k-1)\) faces of the simplex. For a \(1\)-simplex i.e. a line segment defined by two points \((\vec{a}, \vec{b})\), the corresponding term is \(\b{w} \cdot [(\b{w} + \vec{a}) \^ (\b{w} + \vec{b}))] = \vec{b} - \vec{a}\), i.e. two points, one positively oriented and one negatively oriented.

There is a standard operation on simplexes called the boundary operator, written \(\p\), which we have just concocted an algebraic expression for. The boundary of the \(k\)-simplex \(p = (p_0, p_1, \ldots p_k)\) is the chain / formal linear combination of \((k-1)\)-simplexes given by:

\[\p p = \sum_j (-1)^{j} (p_0, \ldots p_{j-1}, p_{j+1}, \ldots p_k)\]

And then extended linearly over sums of simplexes. That is: we omit one vertex at a time and produce an alternating sum of the results. The boundary consists of one simplex for each facet (the generic term for a vertex, edge, face, etc of a figure) of \(p\). Examples (we define boundary of a point as the empty set):

\[\begin{aligned} \p(a) &= () \\ \p(ab) &= (b) - (a) \\ \p(abc) &= (bc) - (ac) + (ab) \\ \p(abcd) &= (bcd) - (acd) + (abd) - (abc) \end{aligned}\]

Normally, in e.g. algebraic topology, these objects are called chains, and they’re “formal linear combinations” of simplexes. The coefficients are allowed to be positive and negative integers, and they’ll cancel out, but otherwise they have no geometric meaning other than the fact that reversing the orientation of a simplex negates it (\((ab) = -(ba)\)).

The boundary operator is defined (or assumed, I guess) to distribute over this formal sum, which (it is easy to see) causes “the boundary of a boundary to be zero”:

\[\p^2 = 0\]

For instance:2

\[\p^2 (abc) = \p[(bc) + (ca) + (ab)] = (b) - (c) + (c) - (a) + (a) - (b) = 0\]

It is clear that there is a connection between the boundary operator and wedge powers. Whatever the boundary operator does to a simplex gets translated, when the simplex is mapped to its multivector representation, into a bunch of wedge products.

That is, the \((k)\) simplex \(P = (p_0 p_1 \ldots p_k)\) maps to the multivector

\[P \Ra \^^{k} \begin{pmatrix} 1 & \vec{p}_0 \\ 1 & \vec{p}_1 \\ \vdots & \vdots \\ 1 & \vec{p}_k \end{pmatrix}\]

And its boundary maps to the multivector

\[\p P \Ra \^^{k-1} \begin{pmatrix} 1 & \vec{p}_0 \\ 1 & \vec{p}_1 \\ \vdots & \vdots \\ 1 & \vec{p}_k \end{pmatrix}\]

Which becomes a formal sum of all the \((k-1)\)-simplex faces of \(P\); their sum is its actual volume as a simplex (well, up to a factor of \(\frac{1}{k!}\) I guess).3

3. The Shoelace Formula

As mentioned, the boundary operator distributes over chains (which are formal linear combinations of simplexes). For instance the boundary of a chain of connected line segments that don’t form a closed loop is formal difference of their endpoints:

\[\p((ab) + (bc) + (cd)) = (b) - (a) + (c) - (b) + (d) - (c) \\ = (d) - (a)\]

Which is basically exactly what we would expect: the internal points do cancel out, leaving only the endpoints of the chain. Among other things, this has the pleasing property that if you take a long line segment (or any simplex really) and break it up into a bunch of shorter components, its boundary comes out correct.

We can represent a general polygon (or any polytope) as a chain of the oriented simplexes which compose it. For example, consider the five-sided figure \(P\) created by the points \((a,b,c,d,e)\) in the plane. \(P\) can be decomposed into simplexes as \(P = (abc) + (acd) + (ade)\). Then the boundary operator produces only the external boundaries, because the internal boundaries all cancel out:

\[\begin{aligned} \p P &= \p(abc) + \p(acd) + \p(ade) \\ &= (bc) + (ca) + (ab) + (cd) + (da) + (ac) + (de) + (ea) + (ad) \\ &=[(ac) - (ac)] + [(ad) - (ad)] + (bc) + (ab) + (cd) + (de) + (ea) \\ &= (ab) + (bc) + (cd) + (de) + (ea) \end{aligned}\]

But as we saw before, this (with a factor of \(\frac{1}{2}\)) is the area of the figure, when regarded as a sum of multivectors. Thus:

\[\text{area}(P) = \frac{1}{2} [\p(abc) + \p(acd) + \p(ade)] = \frac{1}{2}[(ab) + (bc) + (cd) + (de) + (ea)]\]

Where the final addition is performed treating each object as a multivector \(\in \bb{R}^n\).

This is the shoelace formula for the area of a polygon, which I wrote an expository post about before I had really studied EA in any depth. I knew it was going to show up…

Clearly the same form generalizes to any dimension. However, it gets a lot harder to use, just because we have to decompose our \(n\)-polytope into \(n\)-simplexes, which is painful in practice (try it. It requires figuring out which points are neighbors of which other points, which I’m sure there is an algorithm for but it’s very annoying and you end up with some very long lists). But if we do it, we can can compute the oriented volume of any \(n\)-polytope.

4. Scalar Volume

The multivector volume of a \(k\)-simplex \(P\) is \(\frac{1}{k!} \p P\) regarded as a multivector \(\in \^^k \bb{R}^n\). Since this is not in general a scalar, we might want to take its norm:

\[\| \text{vol}(P) \|^2 = \frac{1}{(k!)^2} \| \p P \|^2\]

For a line segment \((ab)\) this is just its squared length: \(\| \text{vol}(ab) \|^2 = \| \vec{b} - \vec{a} \|^2\), which reminds us that the vector representation of a line segment is its vector displacement. For a point, it doesn’t seem to be meaningful: \(\|\text{vol}(p)\|^2 = \frac{1}{0!^2} \| \emptyset \|^2 \stackrel{?}{=} 1\).

Since we can write \(\p P\) as the \(\^^k\) power of \(P\)’s matrix representation, we can write, using Cauchy-Binet (\(\^^q AB = \^^q A \^^q B\)) and the definition of the multivector inner product, an expression for the volume as the determinant of a symmetric matrix:4

\[\begin{aligned} (k!)^2 \| \text{vol}(P) \|^2 &= \det [(\^^k P) (\^^k P)^T] \\ &= \det (\^^k [PP^T]) \\ &= \det (\^^k \begin{pmatrix} p_0 \cdot p_0 & p_0 \cdot p_1 & \ldots \\ p_1 \cdot p_0 & p_1 \cdot p_1 & \ldots \\ \vdots & \vdots & \ddots \end{pmatrix} ) \end{aligned}\]

For instance for the triangle \((abc)\):

\[|\text{vol}(abc)|^2 = \frac{1}{(2!)^2} \det \big[ \^^2 \begin{pmatrix} a \cdot a & a \cdot b & a \cdot c \\ b \cdot a & b \cdot b & b \cdot c \\ c \cdot a & c \cdot b & c \cdot c \end{pmatrix} \big]\]

I am not entirely sure what’s going on when we take the determinant (a \(\^^{k+1}\) power) of a \(\^^k\) power.5

I’m sure there’s a deep understanding there I haven’t found yet. But I did find a way to transform this into another known formula for volumes.

We can write the vectors of \(P\) as displacements relative to a common vector \(\p_0\), giving

\[\begin{aligned} (k!)^2 \| \text{vol}(P) \|^2 &= \det \begin{pmatrix} \| p_1 - p_0 \|^2 & (p_1 - p_0)\cdot(p_2 - p_0) & \ldots \\ (p_2 - p_0)\cdot(p_1 - p_0) & \| p_2 - p_0 \|^2 & \ldots \\ \vdots & \vdots & \ddots \end{pmatrix} \end{aligned}\]

Writing \(L_{ij} = \| p_j - p_i \|\) for the length of the \(ij\)‘th side, we can check that

\[\begin{aligned} L_{ij}^2 &= |p_j - p_i|^2 \\ &= |(p_j - p_0) - (p_i - p_0)|^2 \\ &= |p_j - p_0|^2 + |p_i - p_0|^2 - 2 (p_j - p_0) \cdot (p_i - p_0) \\ (p_j - p_0) \cdot (p_i - p_0) &= \frac{1}{2} (L_{j0}^2 + L_{i0}^2 - L_{ij}^2) \end{aligned}\]

Substituting into the previous determinant gives (one form of) the Cayley-Menger determinant formula, which expresses the volume of a simplex in terms of only its squared side lengths, a large symmetric polynomial in the coefficients.

\[| \text{vol}(P) |^2 = \frac{1}{k!^2 2^k} \det \begin{pmatrix} 2L_{02}^2 & L_{01}^2 + L_{02}^2 - L_{12}^2 & \ldots \\ L_{01}^2 + L_{02}^2 - L_{12}^2 & 2L_{02}^2 & \ldots \\ \vdots & \vdots & \ddots \end{pmatrix}\]

There are a couple other expressions for the same thing which include extra rows or columns of \(1\)s on the outside the matrix; presumably because they were not aware of smaller wedge powers than determinants.

For our triangle, if we label the side lengths \(A,B,C\):

\[|\text{area}(abc)|^2 = \frac{1}{16} \det \begin{pmatrix} 2A^2 & A^2 + B^2 - C^2 \\ A^2 + B^2 - C^2 & 2B^2 \end{pmatrix}\]

This is closely related to Heron’s Formula using the semiperimeter \(s = \frac{A + B + C}{2}\): \(\text{area}(abc) = \sqrt{s (s-A) (s-B) (s-C)}\). The transformation to get there isn’t quite intuitive (try it!), but at leaset it’s clear where you would start to generalize Heron’s Formula to higher dimensions.

My other articles about Exterior Algebra:

  1. Oriented Areas and the Shoelace Formula
  2. Matrices and Determinants
  3. The Inner product
  4. The Hodge Star
  5. The Interior Product
  6. EA as Linearized Set Theory?
  7. Oriented Projective Geometry
  8. Simplex Volumes and Boundaries
  9. All the Exterior Algebra Operations
  1. In particular, it seems like \(\frac{\^^{k} (abc)}{\^^(k-1) (abc)}\) is an expression for vectorial “height” of the triangle from the origin, that is, the vector displacement to the plane it lies in. Probably useful somewhere! 

  2. Strictly speaking we do not have to construct these linear combinations such that opposite orientations pick up a minus sign. We could have continued using the \(\neg\) symbol, so e.g. \((ab) = \neg (ba) \neq - (ba)\). In that case the boundary of a boundary would not be zero until we go and map it into a representation that equates \(\neg\) and \(-\). I think there’s a really good reason to keep track of \((a) + \neg(a)\), which is that it acts like a “distributional derivative” similar to \(\delta'(x)\) (in particular, integrating \(\int_{(a) + \neg (a)} f\) is zero unless \(f\) has a singularity at \(a\))… but let’s not worry about that today. 

  3. I’m not sure what to make of the operation “given a matrix of multivectors, sum all of its elements together”. I guess that that amounts to taking one of those “formal linear combinations” and just identifying every basis element with each other, so that all the components just add together. It’s kind of like a trace, but… not? 

  4. Slightly interesting aside. In differential geometry integrals often include a square root of the metric: \(\int \sqrt{\det g} f dV\). The metric can be written as \(g = A^T A\) for a tetrad field, so that \(\sqrt{g}\) is really \(\sqrt{\det (A^T A)}\), the same object as we get here. 

  5. I will note that this corresponds to a standard determinant identity which can be found on Wikipedia under adjugate matrix: \(\det (\text{adj}(A)) = (\det A)^{n-1}\)

    In our notation this would read \(\^^{n} \^^{n-1} A = (\^^n A)^{n-1}\). This seems to hint at some more involved theory of “exterior powers of exterior powers,” but I don’t know what it is yet.