&v.html

Function: Bigebra[`&v`] -- the vee (meet) product.
Bigebra[meet] -- the meet product.

Calling Sequence:

c3 := &v(c1,c2) [or c1 &v c2, not recommended ]
c3 := meet(c1,c2) -- synonym.

Parameters:

c1,c2 - expressions of `type/clipolynom`

Output:

c3 - expression of `type/clipolynom`

Global variables:

dim_V - dimension of the vector space (V,B) that is defined in CLIFFORD as a global variable.

Description:

The pair of operations wedge (i.e. join) and meet acting on Graßmann multi-vectors make up, together with the duality operator, the Graßmann Cayley algebra . This algebra is of tremendous importance in geometrical applications like robotics, visual perception, camera calibration. However, incidence geometries have their own well developed mathematical theory, see e.g. P. Dembowski, Finite Geometries, Springer Verlag, New York, 1968.

To avoid confusion we should point out that the notion of a meet is not unique in literature. Let A be a homogeneous decomposable multivector called an extensor . Every such extensor spans a linear subspace of the space over which it was constructed. The span of A is called the support of A, denoted as supp A . Meet and join can be defined in set theoretic terms on the support of extensors. Let A, B denote extensors, one defines:

A cup B := {x in V | x in supp A or in supp B} i.e. the set theoretic union
A cap B := {x in V | x in supp A and in supp B} i.e. the set theoretic intersection

The operators cup and cap are the same as in set theory. Under these operations every set is an idempotent: A cup A = A and B cap B = B. Moreover, one finds cup o cup = Id and cap o cap = Id for these operators. Including the set theoretic operation of taking the complement, (A -> |A with A cup |A = whole space, where we have used, in lack of an over bar, the Graßmann notation of a preceeding bar), this constitutes the structure of an ortho-modular lattice. Boolean logic is based on this construction. The two operations of meet and join are related by de Morgan laws:

|( A cup B) = (|A) cap (|B)
|( A cap B) = (|A) cup (|B).

In terms of logic we have: cup = and , cap = or , | = not .

In CLIFFORD and Bigebra packages, the meet and join are defined in the following way:

The wedge product of two extensors A and B is an extensor C which has as support the disjoint union of the supports of A and B. However, extensors having the same support are isomorphic (interchangable). We define the join to be this wedge operation. The meet is usually defined using a symmetric correlation in the projective space P ^dim(V). It needs thus a theorem to show that the meet is independent from its construction. Graßmann defined the meet, which he called regressive product , in [A2] , 1862, §5, No. 94 page 61ff. The regressive product was already present in [A1] , chapter 3, §125ff. Graßmann edited in 1877 a reprint with annotations where he gave some explanations on his presentation. A careful reading shows that the regressive product was present already in 1844. The Ergänzung is not explicit in [A1] , but Graßmann discusses the grade of the complement |A which he calls there 'Ergänzzahlen' (A1 §133)) using the so called 'Ergänzung' (Graßmann A2, §4, No. 89 page 57), which we defined already above as |, of an extensor A to be |A. In analogy to de Morgan laws (which he most likely did not knew) as:

| (A \/ B) := (|A) /\ (|B).

[Graßmann used no sign for products, having over 16 of them working, many at the same time and their type had to be deduced by context. He used furthermore no parentheses which makes his writings cumbersome to read. The /\ sign mutated from an (uppercase) Lambda used by Burali-Forti and Marcolongo to be the wedge of Bourbaki.]

The usage of the Ergänzung points out clearly that the meet depends on the dimension of the space. We will see below, that this definition of the meet is computationally very ineffective.

Alfred Lotze, (Über eine neue Begründung der regressiven Multiplikation extensiver Größen in einem Hauptgebiet n-ter Stufe, Jahresbericht der DMV, 57:102-110,1955) defined a universal formula for the regressive product of r-factors. He showed that if one considers the n-1 dimensional space as a space of co-vectors then the original wedge product becomes by the same formula the regressive product of the co-vectors, pointing out the fact that a symmetric correlation is needed for this purpose. That is: (n-1)-multi-vectors are not co-vectors, but may be seen as reciprocal vectors. In [4] , G.-C. Rota and coworkers gave a definition of the meet in terms of a Peano algebra which is essentially the same construction. However, they used the notion of Hopf algebra which allows to write down the formulas in a comprehensible way.

The Graßmann wedge product has as logical counterpart in the exclusive or xor , the Ergänzung is not w.r.t. the choosen volume form of the space V the Graßmann algebra is build over. The meaning of the meet follows from his duality relation.

In Bigebra, the meet and &v (vee) products are implemented as follows ( note the order of factors in the bracket!):

meet(c1,c2) := [c2_(1),c1] c2_(2)
&v(c1,c2) := c1_(1) [c2,c1_(2)] ,

where the bracket [ , ] is a scalar valued alternating multilinear volume form and the co-products are given in Sweedler notation. It can be shown (and is tested below) that both forms represent the same operation.

The Hopf algebraic definition of the meet gives us a great deal of computational benefits as we will show below in some benchmarks. However it works exactly as the Graßmann regressive product.

Graßmann introduced the so called stereometric product , which, being context sensitive, switches between the wedge and the &v (vee-) product. Using polymorphism this could be implemented, and the user can easily program such a wrapper function. We found it peculiar to implement it using the same notation for basis elements for vectors and co-vectors.

The meet as defined here is independent of the assigned scalar product B or the assigend co-scalarproduct BI . In fact it can be shown that the vee-product is SL_n invariant. If one is interested in projective geometry, the invariants derived from meet and join are GL_n invariants.

The meet product is related to the notion of a Hopf algebraic integral [3] . As a remarkable fact, in any Clifford Hopf gebra over dim V = 2 one is not able to find an non zero integral. The notion of meet has thus to be reconsidered in the deformed case.

Examples:

> restart:_CLIENV[_SILENT]:=`true`:with(Bigebra):

Warning, new definition for drop_t

Warning, new definition for gco_d_monom

Warning, new definition for gco_monom

Warning, new definition for init

Infix form ( not recommended , see help page on &t ). Note that we have not assigned a scalar- or co-scalarproduct.

> dim_V:=2:
e1 &v e2;
e1 &v e1we2, e1we2 &v e2, e1we2 &v e1we2;

Firts of all let us check that both versions of teh meet compute indeed identical:

> for i from 1 to 4 do
dim_V:=i:
bas:=cbasis(dim_V);
X:=add(_X[i]*bas[i],i=1..2^dim_V):
Y:=add(_Y[i]*bas[i],i=1..2^dim_V):
printf("In dimension %d the equation `meet(X,Y)=&v(X,Y)` is %a\n",dim_V,evalb(0=simplify(meet(X,Y)-&v(X,Y))));
od:

In dimension 1 the equation `meet(X,Y)=&v(X,Y)` is true

In dimension 2 the equation `meet(X,Y)=&v(X,Y)` is false

In dimension 3 the equation `meet(X,Y)=&v(X,Y)` is true

In dimension 4 the equation `meet(X,Y)=&v(X,Y)` is false

The following example will show, that the meet and the join are exterior products on their own right and cannot be distinguished. This makes it unnecessary to use the \/ (vee) sign for the ordinary wedge product as Rota promoted to stress the analogy with set theoretic operators. We will see that the join of points is the meet of (hyper) planes and the meet of points is the join of (hyper) planes. To demonstrate this, we compute the meet for a Graßmann basis. We check associativity, unit, and show that this product is an exterior product on its own right on reciprocal (sometimes called wrongly dual) vectors (i.e. hyperplanes). The reciprocal meet is then defined to be the meet w.r.t. hyper-planes. Then it is shown that this reciprocal meet is indeed the wedge (join of points) with which we started. [To give a crude reciprocal meet we use Graßmann's Ergänzung, but a combinatorial evaluation is also possible but proved to be too long for this help page.]

We present our demonstration in dimension 3. Define the n-1 (i.e. 2-) vectors A(i). These multi-vectors are the images of a covector basis under dualization, see [4,3] and should be called reciprocal vectors. Their definition involves a symmetric correlation. The 'meet' or `&v` (vee) product of vectors acts as an exterior (or wedge) product on these reciprocal vectors. This is an imediate consequence of categorial duality and is related to the Plücker coordinatization of hyper-planes.

While we show here explicitely how to define a a Meet and Join for hyperplanes, there is an generic Graßmann co-product &gco_pl in the package which could be used with some benefits for the performance, but would probably obscure out aim here.

> dim_V:=3:
# A(i),A(ij) etc are new basis elements
#
# ==> define the hyperplane basis A(i), A(ij) etc
A:=proc(x)
local T;
T:=table([123=-Id,
31=-e2,23=-e1,12=-e3,
13= e2,32= e1,21= e3,
3=e1we2,2=-e1we3,1=e2we3,
0=e1we2we3]);
RETURN(T[x]);
end:
#
# w2A is a translation procedure which turns the output
# into the new A basis of reciprocal vectos (plane vectors)
#
# ==> w2A (wedge basis to hyperplane basis A(i)
w2A:=proc(x)
local bas,y;
bas:={Id=-'A(123)',
e1=-'A(23)', e2= 'A(13)',e3= -'A(12)',
e1we2='A(3)',e1we3=-'A(2)',e2we3='A(1)',
e1we2we3='A(0)'};
RETURN(subs(bas,Cliff5[reorder](x)));
end:
#
# &V (uppercase) is a wrapper function to make the usage of the
# A(i) basis more comfortable
#
# ==> &V can act on the hyperplane basis A(i) seen as wedge multivectors
# and yields A(jk) hyperplane 2-vectors
# [same goes for the Meet (formerly meet)]
`&V`:=proc(x,y)
w2A(&v(eval(x),eval(y)));
end:
`Meet`:=proc(x,y)
w2A(meet(eval(x),eval(y)));
end:

After these preliminary definitions we can directly show the meet to be the ' wedge product of hyperplanes '. First of all we check some elementary properties of the meet acting on hyperplanes.

> A(0),w2A(A(0)); # The 'scalar' w.r.t. the &v product
A(1),w2A(A(1));
A(2),w2A(A(2));
A(3),w2A(A(3)); # (reciprocal) vectors

> &V(A(0),A(1)),&V(A(1),A(0)); # shows A0 to be the identity
Meet(A(0),A(1)),Meet(A(1),A(0)); # synonym but internally computed differently

Now we produce reciprocal bi-vectors (bi-hyperplanes to be precise) A(ij) and the volume element A(123)

> &V(A(1),A(2)),&V(A(2),A(3)),&V(A(3),A(1)); # BI-HYPERPLANES
&V(A(1),&V(A(2),A(3))), # VOLUME ELEMENT EVALUATES TO -ID
&v(A(1),eval(&V(A(2),A(3)))); # eval is needed here to apply A(23)

There are no higher multi-hyperplanes (reciprocal multi-vectors) and the following expressions evaluate to zero:

> &V(A(1),A(123)),&V(A(12),A(23));

The bracket for co-vectors can be defined using the fact that -Id is the volume in the space of hyperplanes as the projection onto -Id. Hence we can define the reciprocal meet RMeet of reciprocal vectors. This is also a demonstration how to extend the features of the CLIFFORD/Bigebra packages:

> B:=linalg[diag](1$dim_V): ### internally used for Grassmann Erg"anzung
`&RMeet`:=proc(x,y) ### function co-meet
local yy,res,lst,var_i,v1,v2;
option `Copyright (c) Ablamowicz, Fauser 2000/02. All rights reserved.`;
## crude version of the Grassmann co-product on the 'multivector plane space' \/A
yy:=&t(e1we2we3,&gco(eval(cmul(e3we2we1,y))),e1we2we3);
yy:=&map(tcollect(&map(switch(yy,3),3,cmul)),1,cmul);
##
if type(yy,tensorbasmonom) or type(yy,tensormonom)then
lst:=[yy];
else
lst:=[op(yy)];
fi;
res:=0;
for var_i in lst do
v1,v2:=peek(var_i,1);
res := res - scalarpart(&v(eval(x),v1))*drop_t(op(v2));
od;
res;
end:

To exemplify out claim, let us define the two mutually reciprocal basis sets of points, joined points (i.e., lines) and point space volume and the hyperplanes bi-hyperplanes (i.e., lines) and the volume of the hyperplane multi-vector space -Id.

> bas:=cbasis(3);
bas_A:=[A(0),A(1),A(2),A(3),A(12),A(13),A(23),A(123)];

For easy comparison, we compute the multiplication table of the RMeet product. This multiplication table is a tensor of rank three. To be able to display this tensor as rank two array, we put the resulting multivectors (in Graßmann basis) into the array. The numerical matrices m_[ij]^k are then obtained by setting one basis element to 1 and all other to zero (i.e. by acting with the dual multivectors on this scheme.)

> Mul_tab_RMeet:=linalg[matrix](2^dim_V,2^dim_V,(i,j)-> 0):
for i from 1 to 2^dim_V do
for j from 1 to 2^dim_V do
Mul_tab_RMeet[i,j]:=reorder(&RMeet(bas[i],bas[j]));
od:od:
evalm(Mul_tab_RMeet);

Our final goal is to show, that the above defined multiplication for RMeet (the meet of hyperplanes) is equivalent to the wedge product of points . We compute therefore the multiplication table for the wedge also:

> Mul_tab_wedge:=linalg[matrix](2^dim_V,2^dim_V,(i,j)-> 0):
for i from 1 to 2^dim_V do
for j from 1 to 2^dim_V do
Mul_tab_wedge[i,j]:=&w(bas[i],bas[j]);
od:od:
evalm(Mul_tab_wedge);

The final check is to add both matrices which gives zero. This shows that up to a sign (which is irrelevent in projective plane geometry) the products are the same. Or, as operator equation:

RMeet(x,y) = -wedge(x,y)

The sign belongs to the fact that in three dimensions we find that the volume element squares to negative identity, which means that we would reach the original wedge after a second turn in our argumentation. However, we resist to demonstrate this explicitly here.

> evalm(Mul_tab_RMeet+Mul_tab_wedge);

Fianlly we will provide some BENCHMAKS which shall show how efficient the two alternate definitions of the meet are. One, as adopted recently by Hestenes and followers, is based on the Grassmann's Ergänzung and the other is based on Hopf algebra methods as employed in Bigebra and given by Lotze and Rota.

> restart:_CLIENV[_SILENT]:=`true`:with(Bigebra):

Warning, new definition for drop_t

Warning, new definition for gco_d_monom

Warning, new definition for gco_monom

Warning, new definition for init

> dim_V:=3:B:=linalg[diag](1$dim_V):

We use dimension 3 and a orthogonal, normalized Euclidean bilinear form (the polar form of a quadratic form).

As a Benchmark we compute 100 times a certain meet (this is not a good idea, since some functions may remember its results, e.g. the wedge product from the CLIFFORD package, but it gives nevertheless a feeling what is going on).

The Hopf algebraic case needs:

> s:=time():
for i from 1 to 100 do
&v(e1we2,e2we3);
od:
printf("This took us %f seconds",time()-s);
&v(e1we2,e2we3);

This took us 5.087000 seconds

> restart:_CLIENV[_SILENT]:=`true`:with(Bigebra): # reload everything to be fair
dim_V:=3:B:=linalg[diag](1$dim_V):
s:=time():
for i from 1 to 100 do
cmul(e3we2we1,wedge(cmul(e1we2we3,e1we2),cmul(e1we2we3,e2we3)));
od:
printf("This took us %f seconds",time()-s);
cmul(e3we2we1,wedge(cmul(e1we2we3,e1we2),cmul(e1we2we3,e2we3)));

Warning, new definition for drop_t

Warning, new definition for gco_d_monom

Warning, new definition for gco_monom

Warning, new definition for init

This took us 1.332000 seconds

Since we compute the Clifford product using a very fast Hopf algebraic function cmulRS, this works out faster. However, we could speed up &v by directly employing the Hopf algebraic routines and avoinging wrapper functions as `peek`. Furthermore we have not computed the inverse of the Ergänzung but introduced simply e3we2we1 which is (e1we2we3)^(-1) in our case.

Now let us go for a non-orthogonal but still symmetric bilinear form (a polar form of a quadratic form or a symmetric correlation) and check what happens there:

> restart:_CLIENV[_SILENT]:=`true`:with(Bigebra):

Warning, new definition for drop_t

Warning, new definition for gco_d_monom

Warning, new definition for gco_monom

Warning, new definition for init

> dim_V:=3:B:=linalg[matrix](dim_V,dim_V,(i,j)->if i<=j then g[i,j] else g[j,i] fi);

Compute the Bigebra meet &v (vee product):

> s:=time():
clicollect(&v(e1we2,e2we3));
printf("This took us %f seconds",time()-s);

This took us .050000 seconds

We reload once more the package to be fair and compute the meet using the Ergänzung:

> restart:_CLIENV[_SILENT]:=`true`:with(Bigebra):
dim_V:=3:B:=linalg[matrix](dim_V,dim_V,(i,j)->if i<=j then g[i,j] else g[j,i] fi);
s:=time():
clicollect(cmul(e3we2we1,wedge(cmul(e1we2we3,e1we2),cmul(e1we2we3,e2we3))));
printf("This took us %f seconds",time()-s);

Warning, new definition for drop_t

Warning, new definition for gco_d_monom

Warning, new definition for gco_monom

Warning, new definition for init

This took us .210000 seconds

This shows already a difference (approx. a factor 6, which varies from computation to computation due to garbage collection overhead) which would further increase if the dimension were higher. Thus, the computational efficiency of the meet has been demonstrated.

Moreover, we can go beyond the possibilities of the Ergänzungs method since we can compute the meet in the presence of a non-symmetric bilinear form (which cannot be derived from a quadratic form by polarization) using Hopf algebra methods. Our meet works independently of the assigned bilinear form while the Eränzungs method needs an orthogonal non-degenerate bilinear form (which is the polar form of the symmetric correlation, i.e. a quadratic form).

Let us use an arbitrary bilinear form in 3 dimensions:

> B:=linalg[matrix](dim_V,dim_V,(i,j)->b[i,j]);