Wikipedia:Reference desk/Archives/Mathematics/2016 June 27

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

June 27

Linear transformations using the geometric product

I think that I have read that when using Clifford algebras it is possible to represent linear transformations using the geometric product. Well, how? Any guidance would be appreciated.--Leon (talk) 13:12, 27 June 2016 (UTC)

The simplest transformation is that for any element of an algebra M and unit vector a the product M‘ = aMa is a reflection, in the direction of a and about the origin. Note this applies to all elements M, in all dimensions. The direction of the reflection is specified rather than the plane so it works in all dimensions. The vector is e.g. the normal vector of a plane mirror in three dimensions. This is easy to check for e.g. vectors, and as everything in the algebra can be built from vector products it applies to all elements of the algebra.

Two reflections make a rotation. This is easy to demonstrate, and is the basis of eg. Kaleidoscope toys. The algebra is simple. If the reflections are given by a and b they are just applied in order, e.g. M‘‘ = aM‘a = a(bMb)a = abMba.

The product ab is a rotor, and it does rotations, i.e. orthogonal transformations. if R = ab is a rotor the rotation is RMR*, where R* is the reversion.

In two and three dimensions that’s all you need. In higher dimensions you come across slightly more complex rotors, e.g. ones which are sums of products of vectors. But the approach is the same, you can still build up the rotations from reflections and single vectors. Geometric algebra#Geometric interpretation covers it in some detail, Plane of rotation and Bivector cover some aspects of it.--JohnBlackburne^words_deeds 00:36, 28 June 2016 (UTC)

That's only orthogonal transformations. The dot product is $v\cdot w=(vw+wv)/2$, so you could write an arbitrary linear transformation (edit: of a vector u) $\textstyle \sum _{i}v_{i}(w_{i}\cdot u)$ as $\textstyle {\tfrac {1}{2}}\sum _{i}v_{i}(w_{i}u+u\,w_{i})={\tfrac {1}{2}}\sum _{i}v_{i}w_{i}u+v_{i}u\,w_{i}$. -- BenRG (talk) 02:57, 28 June 2016 (UTC)

Just for clarity, this applies to transformations of the vectors (or 1-vectors in GA terminology), which is a distinguished subspace of the Clifford algebra, and is quite possibly what you (the OP) intended. It does not produce an arbitrary linear transformation of the space of all elements the Clifford algebra. —Quondum 15:04, 28 June 2016 (UTC)

So this method doesn't work for e.g. bivectors? I did want something that would work for all the elements of the Clifford algebra. — Preceding unsigned comment added by Star trooper man (talk • contribs) 16:19, 28 June 2016 (UTC)

The approach I described does. It can be used on all elements of the algebra, and generate all orthogonal transformations. It has another benefit too, over the approach given by BenRG, that it is coordinate free.

One thing to clarify, is that there are two things, geometric algebra and Clifford algebra, but they are not really different but two different ways of looking at the same thing. I tend to refer to them them interchangeably but that’s as I’m mostly concerned with the geometric applications of them like this, where the differences don’t matter so much or can be ignored.--JohnBlackburne^words_deeds 18:15, 28 June 2016 (UTC)

But your approach only generates orthogonal transformations. There are other linear transformations.--Leon (talk) 18:19, 28 June 2016 (UTC)

You can generate other transformations. Scaling can be done by multiplying by a scalar, that does not require geometric algebra but it is a valid operation in GA. Geometric algebra#Geometric interpretation describes how to do projection and rejection. You can combine these to produce other operations such as scaling in one direction.

These are all transformations that fix the origin. If you want to do more general transformations including translations you can use conformal geometric algebra which uses GA two dimensions higher to effect general transformations in a space.--JohnBlackburne^words_deeds 18:55, 28 June 2016 (UTC)

JohnBlackburne, your statement "It can be used on all elements of the algebra", must be qualified in the sense that one should interpret it as acting on the 1-vectors from which a bivector are built as a sum-of-products-of-vectors, not as an orthogonal transformation of the bivector as an element of the algebra (because a "dot product" on a bivector and some other element in terms of which to define an "orthogonal transformation" is not properly defined). BenRG's approach is coordinate-free; it just needs to enumerate several elements used to build up the operation.

Leon, please confirm that you mean the linear transformations to apply to a vector space (having n dimensions) and not the Clifford algebra (having 2ⁿ dimensions). Further, do you wish the operation to act as a linear transformation of the vectors in the sum-of-products-of-vectors in the way rotors do? I believe that this can be represented in the Clifford algebra (I understand that there is even a term for it, but I'd have to dig it out), but it is probably not based on projections. —Quondum 00:36, 29 June 2016 (UTC)

Yes, my suggestion wasn't very good because it only works with vectors. (But it was coordinate-free.)

What I should have said: you can write any linear transformation as a weighted sum of orthogonal transformations, and any orthogonal transformation can be represented in the Clifford algebra by a conjugation, so any linear transformation can be written $T(z)=\sum _{i}k_{i}R_{i}zR_{i}^{\dagger }$ where each k is a scalar and each R is a product of vectors. This works for arbitrary $z\in C\ell (V)$. (You could almost get away without k, but when the algebra is real I think you sometimes need k = −1.) -- BenRG (talk) 03:00, 29 June 2016 (UTC)

I'm retracting this because I think a linear transformation that doubles vectors ought to quadruple bivectors, and this doesn't do that. I did honestly look for sources before trying to invent my own answer, but they're hard to find for Clifford algebra. -- BenRG (talk) 07:23, 29 June 2016 (UTC)

My "It can be used on all elements of the algebra" is based simple algebra. If p and q are vectors, and you reflect each as described, e.g.

p‘ = apa & q‘ = aqa

then multiplying you get

p‘q‘ = apa aqa = apaaqa = apqa' (as a² = 1) = a(pq)a = (pq)‘

I.e. reflecting the product of two vectors, that is a bivector. works as expected. It is obviously distributive over addition. And as every element of the algebra can be constructed from products and sums of vectors then all elements of the algebra transform the same way. The same is true of rotors, as

RpR* RqR* = RpR*RqR* = RpqR* = R(pq)R*, using the fact that RR* = R*R = 1

These are orthonormal transformations, but extended using geometric algebra. It even has an inner product for a formal definition, though I was not thinking of that. More that they are orthonormal in the sense of preserving angles which is easily understood in GA, where e.g. you have vectors, planes and you can measure the angles between them.--JohnBlackburne^words_deeds 03:59, 29 June 2016 (UTC)

You are implicitly assuming the interpretation of GA of a transformation as upon the 1-vectors, and by extension on multilinear combinations of vectors to the whole algebra, and a linear transformation on the space of vectors has n² dimensions. We have not assumed GA as the context, and in Clifford algebra generally no such interpretation would apply. The request is "I did want something that would work for all the elements of the Clifford algebra." We still need to define what is meant by a linear mapping from the Clifford algebra onto itself. A general linear transformation of this type has 2²ⁿ dimensions. My original observation remains. —Quondum 06:30, 29 June 2016 (UTC)

I thought that a linear transformation f on elements of a Clifford algebra was well defined, and that it had to satisfy the property that $f(x\wedge y)=f(x)\wedge f(y)$ for vectors x and y, and so on for trivectors and beyond. That's what I'm after.--Leon (talk) 07:40, 29 June 2016 (UTC)

That does resolve the question. But no, the product with any fixed element of the algebra is an example of a linear transformation on the algebra (it satisfies all the axioms of R-linearity), but does not in general meet this criterion that you've given now. What you are referring to is called an 'outermorphism' by Dorst et al., defined in §4.2 of their book Geometric Algebra for Computer Science, and is the term I said I'd have to dig out. They define it as, in effect, the linear transformations on the 1-vector space extended in a consistent fashion to the whole algebra. BenRG and JohnBlackburne evidently automatically assumed that this as what you meant, and I was pointing out that your question, as worded, did not imply this. —Quondum 13:42, 29 June 2016 (UTC)

So, I assume that your original question should read: How can outermorphisms in a Clifford algebra be represented using the geometric product? There is no doubt extensive literature on this, and I can consult the text I referred to. The conjugations RZR^† form a subset of the outermorphisms (R being a versor and Z being an arbitrary element of the algebra). A general outermorphism cannot be expressed so simply, but I suspect that it can be expressed much like BenRG suggested (now struck out): a weighted sum of such conjugations. Since every outermorphism f has the property that f(1) = 1, we necessarily have in his suggestion that $\sum _{i}k_{i}=1$. I'll look into whether this is all there is to it shortly. The answer to this would be a worthwhile addition to the article Outermorphism. —Quondum 17:16, 29 June 2016 (UTC)

That is certainly what I want! Thanks.--Leon (talk) 17:35, 29 June 2016 (UTC)

The reference does not give any representation in terms of the algebra for a general outermorphism; it only gives examples (such as projections, rotations, reflections, scaling). A little bit of algebra shows that a weighted sum of outermorphisms is almost never an outermorphism. The outermorphisms of projection and rotation can be expressed using operations of the algebra (assuming that the exterior product is permitted), but these expressions are pretty different. Between this and the lack of a solution in the text, I am pretty pessimistic about there being a general expression that does not leverage operations such as the grade projection operator or other "fancy" operations. —Quondum 04:26, 30 June 2016 (UTC)

I may still be missing something, but I think a weighted sum of conjugations is hopeless, because (in my notation) T(1) = 1 implies $\sum _{i}k_{i}R^{\dagger }R=1$, and I think that implies $z^{\dagger }z=T(z)^{\dagger }T(z)$ in general (or at least for vectors), so you can't express a transformation that generalizes T(v) = 2v, for example. That's why I struck it out.

With grade projection, you should be able to write $T(z)=\sum _{r}\sum _{i}k_{i}^{r}R_{i}\langle z\rangle _{r}R_{i}^{-1}$. I guess that isn't too bad, but I'm not sure it meets the requirements of the question. -- BenRG (talk) 07:26, 30 June 2016 (UTC)

BenRG, it doesn't, but your argument about transformations does lead me to suspect that you cannot express an outermorphism in terms of the geometric product.--Leon (talk) 07:41, 30 June 2016 (UTC)

[removed not-so-useful stuff by me]

Do we mean, by "express an outermorphism in terms of the geometric product", something specifically of the form $T(Z)=\sum _{i}Q_{i}ZR_{i}$, for an arbitrary multivector $Z$, and constant multivectors $Q_{i}$ and $R_{i}$? —Quondum 19:46, 30 June 2016 (UTC)

Yes.--Leon (talk) 07:44, 1 July 2016 (UTC)

Then we can get partway to a definitive answer: "It is sometimes possible, but not always". Classification of Clifford algebras is helpful here.

There are some real Clifford algebras where this is possible, e.g. Cl_0,0 = R, Cl_1,0 = R⊕R, Cl_2,0 = Cl_1,1 = M₂(R), Cl_0,2 = H, Cl_0,3 = H⊕H. How I get these examples is that I can construct expressions of the given form that project out each of the individual dimensions of the full algebra, which allows the building of an arbitrary linear transform of the entire algebra of 2ⁿ dimensions, and the outermorphisms are a subset of these. Similarly, Cl_1,0 = R⊕R (which complexifies to the same algebra as does Cl_0,1) has idempotent elements that allow us to project out the two dimensions and scale them independently, even though the algebra is commutative. An interesting case is Cl_0,2 = H, where we can produce a projection operator P₁(x) = (x − ixi − jxj − kxk)/4 of the given form that maps a+ib+jc+kd ↦ a, and similarly for each of the other dimensions, e.g. P_i(x) = −iP₁(ix), and can then build any outermorphism as a linear combination of these. It is interesting to note that here the projection mechanism used relies not on idempotent elements (there are none that are nontrivial), but on noncommutativity. Matrices are easily decomposed into their components using the given operations (the Q_i and R_i are matrices with zero elements except for a single 1 on the diagonal), which gives us all algebras classified as M_n(R) and M_n(R)⊕M_n(R) and by the projections given above on H, also M_n(H) and M_n(H)⊕M_n(H) .

There are some real Clifford algebras where it is not possible (e.g. Cl_0,1 = C and Cl_1,0 = R⊕R). In this case, we know that there exists no algebraic map z ↦ z (complex conjugation), and therefore no algebraic expression exists for the nonidentity outermorphisms, which are dilations a+ib ↦ a+ikb, k≠1. I think that it should not be difficult to show that any with a C or ⊕ in its classification does not permit expression of arbitrary outermorphisms in the given form.

That seems to be a comprehensive answer (but needs checking) to exactly which real Clifford algebras permit it (many of them – those over real spaces of even dimensionality), and gives the "how" (if one understands the isomorphisms). This probably lends itself to generalization to Clifford algebras over other fields. —Quondum 22:16, 1 July 2016 (UTC)

A further thought: if you are free to choose the signature of the quadratic form on the vector space, then it is always possible. —Quondum 22:27, 1 July 2016 (UTC)

(added after archiving:) I've struck out and inserted a few changes where I got something wrong above. —Quondum 20:19, 6 July 2016 (UTC)

a word for a string

What's the name of the shortest sequence that contains all possible subsequences of a given length from a given set of symbols? —Tamfang (talk) 23:25, 27 June 2016 (UTC)

When I put the words "shortest sequence that contains all possible subsequences of a given length from a given set of symbols" into my favorite search engine, the Wikipedia article De Bruijn sequence is one of the top 5 results. This may or may not be exactly what you want, depending on your prefered meaning of words like "contains" and "subsequences". --JBL (talk) 23:38, 27 June 2016 (UTC)

Thank you.

Resolved

—Tamfang (talk) 03:37, 28 June 2016 (UTC)

What's your favourite search engine, Tamfang? In my favourite SE I get: superpattern, followed by Longest common subsequence problem. --Hofhof (talk) 17:08, 29 June 2016 (UTC)

Me too; DuckDuckGo. —Tamfang (talk) 19:29, 29 June 2016 (UTC)