18 Grassmann–Cayley extensor algebra
This chapter sets up the part of the Grassmann–Cayley algebra that Katoh and Tanigawa use [ KT11 , § 2.1 ] , and proves their Lemma 2.1. A point of \(K^d\) is written in homogeneous coordinates in \(K^{d+1}\), and the affine subspace spanned by points \(p_1, \dots , p_k\) is represented by its extensor, the product of their homogeneous coordinate vectors in the exterior algebra of \(K^{d+1}\). KT Lemma 2.1 (lemma 18.9) says that if \(p_1, \dots , p_{d+1}\) are affinely independent points of \(K^d\), then the extensors of the \(D = \binom {d+1}{2}\) sets of \(d-1\) of these points are linearly independent. Section 19 builds the rigidity matrix of a body-hinge framework from the extensors of its hinges, and the proof of KT Theorem 5.5 uses Lemma 2.1 in its last case (section 23).
Nothing in the chapter uses an inner product, an order or a hypothesis on the characteristic, so we work over an arbitrary field \(K\); Katoh and Tanigawa work over \({\mathbb {R}}\). Section 18.1 shows that points are affinely independent if and only if their homogeneous coordinate vectors are linearly independent (lemma 18.2). Section 18.2 defines extensors and their join in the exterior algebra, following Barnabei, Brini and Rota [ BBR85 ] . It relates extensors to the Plücker coordinates through which Katoh and Tanigawa define them, and defines the extensor of an affine subspace. Section 18.3 proves KT Lemma 2.1.
18.1 Homogeneous coordinates and affine independence
As in section 16 and section 17, \(d\) is the dimension and \(D = \binom {d+1}{2}\); over \({\mathbb {R}}\), \(D\) is the dimension of the space of infinitesimal motions of a rigid body in \({\mathbb {R}}^d\). Following Katoh and Tanigawa, we give each point of \(K^d\) a homogeneous coordinate vector in \(K^{d+1}\).
Let \(p \in K^d\). The homogeneous coordinate vector of \(p\) is the vector \(\bar p = (p, 1) \in K^{d+1}\), obtained by appending the coordinate \(1\).
Recall that points \(p_1, \dots , p_k\) of \(K^d\) are affinely independent if the only scalars \(w_1, \dots , w_k\) with \(\sum _i w_i = 0\) and \(\sum _i w_i p_i = 0\) are \(w_1 = \cdots = w_k = 0\).
Let \(p_1, \dots , p_k \in K^d\). Then \(p_1, \dots , p_k\) are affinely independent if and only if \(\bar p_1, \dots , \bar p_k\) are linearly independent. In particular, \(d+1\) points \(p_1, \dots , p_{d+1}\) of \(K^d\) are affinely independent if and only if the \((d+1) \times (d+1)\) matrix with rows \(\bar p_1, \dots , \bar p_{d+1}\) has nonzero determinant.
Let \(w_1, \dots , w_k \in K\). The first \(d\) coordinates of \(\sum _i w_i \bar p_i\) are those of \(\sum _i w_i p_i\), and its last coordinate is \(\sum _i w_i\). So \(\sum _i w_i \bar p_i = 0\) if and only if \(\sum _i w_i p_i = 0\) and \(\sum _i w_i = 0\). The linear relations among \(\bar p_1, \dots , \bar p_k\) are therefore exactly the families \(w\) in the definition of affine independence, and one kind of independence holds if and only if the other does. The second statement follows, since the rows of a square matrix are linearly independent if and only if its determinant is nonzero.
18.2 Extensors, the join, and Plücker coordinates
Let \(\bigwedge K^{d+1}\) be the exterior algebra of \(K^{d+1}\), and let \(\bigwedge ^j K^{d+1}\) be its graded piece of degree \(j\), which has dimension \(\binom {d+1}{j}\). An extensor is a product of vectors in this algebra. We follow Barnabei, Brini and Rota [ BBR85 , § 3 ] .
Let \(v_1, \dots , v_j \in K^{d+1}\). The extensor of the family \((v_1, \dots , v_j)\) is the product \(v_1 \wedge \cdots \wedge v_j\) in \(\bigwedge K^{d+1}\). A \(j\)-extensor is an element of \(\bigwedge K^{d+1}\) of this form.
A \(j\)-extensor lies in \(\bigwedge ^j K^{d+1}\). The extensor of \((v_1, \dots , v_j)\) is linear in each \(v_i\) and alternating: it is zero when two of the \(v_i\) are equal, and it changes sign when two of them are exchanged. So it does not change when a multiple of one \(v_i\) is added to another, and it is zero when \(v_1, \dots , v_j\) are linearly dependent. Conversely, let \(v_1, \dots , v_j\) be linearly independent, and extend them to a basis of \(K^{d+1}\). The products of basis vectors over the increasing sequences of indices form a basis of \(\bigwedge K^{d+1}\), and \(v_1 \wedge \cdots \wedge v_j\) is one of them. So the extensor of \((v_1, \dots , v_j)\) is nonzero if and only if \(v_1, \dots , v_j\) are linearly independent (extensor_ne_zero_iff_linearIndependent), as Katoh and Tanigawa recall [ KT11 , p. 651 ] . Barnabei, Brini and Rota call only a nonzero product an extensor; like Katoh and Tanigawa, we allow the zero product.
Barnabei, Brini and Rota call the product of the exterior algebra the join.
Let \(A, B \in \bigwedge K^{d+1}\). The join of \(A\) and \(B\) is their product \(A \vee B = A \wedge B\) in \(\bigwedge K^{d+1}\).
The join is associative, and the join of two extensors is the extensor of the concatenated family:
(join_extensor). The extensor of \((v_1, \dots , v_j)\) is therefore the join \(v_1 \vee \cdots \vee v_j\) of its vectors, and from now on we write it so, as Katoh and Tanigawa do. Two bases of one \(j\)-dimensional subspace of \(K^{d+1}\) have extensors that differ by a nonzero scalar, and a nonzero \(j\)-extensor determines the subspace spanned by its vectors [ BBR85 , Proposition 3.4 ] . Let \(F\) and \(G\) be nonzero extensors of subspaces \(X\) and \(Y\). Then \(F \vee G = 0\) if \(X \cap Y \neq 0\), and otherwise \(F \vee G\) is an extensor of \(X + Y\) [ BBR85 , Proposition 3.5 ] .
Katoh and Tanigawa define extensors through coordinates, which we define next.
Let \(v_1, \dots , v_j \in K^{d+1}\), and let \(A(v)\) be the \(j \times (d+1)\) matrix whose \(i\)-th row is \(v_i\). For \(1 \le i_1 {\lt} \cdots {\lt} i_j \le d+1\), the Plücker coordinate \(P_{i_1, \dots , i_j}\) of \((v_1, \dots , v_j)\) is \((-1)^{1 + i_1 + \cdots + i_j}\) times the determinant of the \(j \times j\) submatrix of \(A(v)\) on the columns \(i_1, \dots , i_j\). The Plücker coordinate vector of \((v_1, \dots , v_j)\) is the vector of its \(\binom {d+1}{j}\) Plücker coordinates.
The sign is Katoh and Tanigawa’s [ KT11 , p. 651 ] . Katoh and Tanigawa work with the Plücker coordinate vector and call the extensor its symbolic version. For \(j = d+1\) there is one Plücker coordinate, \(\pm \det A(v)\) (pluckerCoord_univ). For homogenized points, \(\det A(v)\) is the determinant of lemma 18.2.
Let \(v_1, \dots , v_j \in K^{d+1}\). The products \(e_{i_1} \wedge \cdots \wedge e_{i_j}\) with \(i_1 {\lt} \cdots {\lt} i_j\) form a basis of \(\bigwedge ^j K^{d+1}\), and the coordinate of \(v_1 \vee \cdots \vee v_j\) at \(e_{i_1} \wedge \cdots \wedge e_{i_j}\) is \((-1)^{1 + i_1 + \cdots + i_j} P_{i_1, \dots , i_j}\), the Plücker coordinate up to Katoh and Tanigawa’s sign.
Write each \(v_i\) in the standard basis and expand \(v_1 \wedge \cdots \wedge v_j\) by multilinearity and alternation. The coefficient of \(e_{i_1} \wedge \cdots \wedge e_{i_j}\) is the minor of \(A(v)\) on the columns \(i_1, \dots , i_j\). The sign squares to \(1\), so this minor is the coordinate \(P_{i_1, \dots , i_j}\) times the sign.
The pin is the library’s basis of the exterior power induced by the standard basis, and the expansion is its coordinate formula (exteriorPower.basis_repr_apply) for the minor. Katoh and Tanigawa’s sign is the one in definition 18.5, so the statement carries it.
Katoh and Tanigawa represent an affine subspace by the extensor of the homogeneous coordinate vectors of points that span it.
Let \(p_1, \dots , p_k \in K^d\). The extensor of \(p_1, \dots , p_k\) is
If \(p_1, \dots , p_k\) are affinely independent and span the affine subspace \(U\), we also write \(C(U)\) for \(C(p_1, \dots , p_k)\) and call it a \(k\)-extensor supporting \(U\).
By lemma 18.2, the points \(p_1, \dots , p_k\) are affinely independent if and only if \(\bar p_1, \dots , \bar p_k\) are linearly independent. By the criterion after definition 18.3, this holds if and only if \(C(p_1, \dots , p_k) \neq 0\) (affineSubspaceExtensor_ne_zero_iff). Now let \(p_1, \dots , p_k\) be affinely independent with affine span \(U\), and let \(W\) be the subspace of \(K^{d+1}\) spanned by \(\bar p_1, \dots , \bar p_k\). A point \(p\) lies in \(U\) if and only if \(\bar p \in W\), so \(U\) and \(W\) determine each other. By Proposition 3.4 of Barnabei, Brini and Rota [ BBR85 ] , \(W\) determines its nonzero extensors up to a nonzero scalar, and each of them determines \(W\). So \(C(U)\) is determined by \(U\) up to a nonzero scalar, and it determines \(U\).
18.3 Independence of the \((d-1)\)-extensors (KT Lemma 2.1)
This subsection proves KT Lemma 2.1. Katoh and Tanigawa call it a fundamental fact about extensors and prove it for completeness [ KT11 , pp. 651–652 ] ; we follow their proof.
Let \(p_1, \dots , p_{d+1} \in K^{d}\) be affinely independent. Then the \(D = \binom {d+1}{2}\) extensors
are linearly independent in \(\bigwedge ^{d-1} K^{d+1}\), where a hat marks an omitted vector.
For \(a {\lt} b\), write \(E_{ab}\) for the extensor in the statement: the join of the \(\bar p_i\) with \(i \neq a, b\), in increasing order of \(i\). Suppose that \(\sum _{a {\lt} b} \lambda _{ab} E_{ab} = 0\) for scalars \(\lambda _{ab}\), and fix a pair \(a {\lt} b\). We join the relation on the left with \(\bar p_a \vee \bar p_b\), which gives
Every term with \(\{ c, c'\} \neq \{ a, b\} \) vanishes. Indeed, one of \(a\) and \(b\), say \(a\), is not in \(\{ c, c'\} \), so \(\bar p_a\) is one of the vectors joined in \(E_{cc'}\). Then \(\bar p_a \vee \bar p_b \vee E_{cc'}\) is the join of a family in which \(\bar p_a\) occurs twice, and it is zero because the join is alternating (definition 18.3).
The remaining term is \(\lambda _{ab}\, \bar p_a \vee \bar p_b \vee E_{ab}\). Its join is that of the family obtained from \(\bar p_1, \dots , \bar p_{d+1}\) by a bijection of \(\{ 1, \dots , d+1\} \): the first two places go to \(a\) and \(b\), and the remaining \(d-1\) places go, in order, to the elements of \(\{ 1, \dots , d+1\} \setminus \{ a, b\} \) in increasing order. The vectors \(\bar p_1, \dots , \bar p_{d+1}\) are linearly independent (lemma 18.2), so the reordered family is linearly independent too, and its join is nonzero (definition 18.3). Hence \(\lambda _{ab} = 0\). As the pair \(a {\lt} b\) was arbitrary, every \(\lambda _{ab}\) is zero.
The formalization writes \(d = e + 1\), so that the points lie in \(K^{e+1}\) and each \(E_{ab}\) is an \(e\)-extensor, and it indexes the extensors by the pairs \(a {\lt} b\). The three declarations are \(E_{ab}\) (omitTwoExtensor), the lemma as stated (omitTwoExtensor_linearIndependent), and the lemma for any \(d+1\) linearly independent vectors of \(K^{d+1}\) (omitTwoExtensor_linearIndependent_of_li), from which the lemma as stated follows by lemma 18.2.
The proof uses the points only through the linear independence of \(\bar p_1, \dots , \bar p_{d+1}\), so the lemma holds for any linearly independent vectors \(v_1, \dots , v_{d+1}\) of \(K^{d+1}\). Since \(\bigwedge ^{d-1} K^{d+1}\) has dimension \(\binom {d+1}{d-1} = D\), the \(D\) extensors then form a basis of it. So a linear functional on \(\bigwedge ^{d-1} K^{d+1}\) that vanishes on all of them is zero. Katoh and Tanigawa use the lemma in this way in the last case of the proof of KT Theorem 5.5: in KT Claim 6.12 for \(d = 3\), and in KT Lemma 6.13 for general \(d\) [ KT11 , § 6.4 ] . There they choose \(d+1\) affinely independent points such that the affine subspace spanned by any \(d-1\) of them lies in one of \(d\) given panels. Case III of section 23 uses the lemma for linearly independent vectors (lemma 23.169).