# Efficient computation of scalar part in Clifford algebra

$$\DeclareMathOperator\Cl{Cl}$$Problem: Let $$\Cl(d)$$ be the Clifford algebra corresponding to the vector space $$\mathbb{R}^d$$ with the usual inner product. Given $$v_1, \dotsc, v_k \in \mathbb{R}^d$$, compute the scalar part of the product $$v_1 \dotsm v_k \in \Cl(d)$$ in an efficient way.

One (inefficient) approach would be to first write the $$v_j$$ in some (ordered) orthonormal basis $$\{e_i\}_{1 \leq i \leq d}$$, then expand and simplify the product using that $$e_i e_j = -e_j e_i$$ when $$i > j$$ and that $$e_i^2 = -1$$, and finally take the scalar part (constant term) of the result. The problem with this approach is that, when expanding the product, one gets a number of monomials that is exponential in $$d$$, since $$\Cl(d)$$ is of real dimension $$2^d$$ with basis given by ordered products of distinct $$e_i$$. (Note that in my case $$k$$ is allowed to be of the order of $$d$$.)

Since I am not interested in the full product of the $$v_j$$ but just on the scalar part of it, I wonder if there is an efficient algorithm for its computation. So far, I have tried using some of the well known identities that hold in $$\Cl(d)$$, and taking a look at some of the software for doing calculations in Clifford algebras but I couldn't find this exact functionality.

$$\newcommand\R{\mathbb R} \newcommand\inv{^{-1}} \newcommand\grade[1]{\langle#1\rangle} \newcommand\rev\widetilde \newcommand\conj[1]{#1^*} \DeclareMathOperator\Re{Re} \DeclareMathOperator\Spin{Spin}$$

Let $$V_k = v_1\cdots v_k$$ and $$|V_k| = |v_1|\cdots|v_k|$$.

When $$k$$ is odd, the scalar part $$\grade{V_k} = 0$$ since $$v_1\cdots v_k$$ has to be an odd multivector.

When $$k$$ is even, $$\frac{V_k}{|V_k|} \in \Spin(d)$$ and acts on $$\R^d$$ as a rotation through the action $$x \mapsto \frac{\rev V_kxV_k}{|V_k|^2}$$, where $$\rev V_k$$ is the reversal of $$V_k$$. We then have $$\grade{V_k} = \pm|V_K|\cos(\theta_1/2)\cdots\cos(\theta_m/2)$$ where $$m = \lfloor\frac n2\rfloor$$ and $$\theta_i$$ is the rotation angle within in $$i^{\text{th}}$$ plane (recalling that in $$d$$ dimensions $$m$$ rotations can happen independently in completely orthogonal planes). We are not able to determine the sign since $$-V_k$$ acts identically to $$V_k$$, a manifestation of the double cover $$\Spin(d) \to O(d)$$ having kernel $$\{\pm1\}$$.

The problem is reduced to computing the sign and $$|\cos(\theta_i/2)|$$.

One possibility for computing $$|\cos(\theta_i/2)|$$ is the following:

The product $$V_k$$ represents this rotation as a sequence of reflections, where e.g. $$x \mapsto \frac{-v_1xv_1}{v_1^2}$$ is the reflection of $$x$$ through the hyperplane orthogonal to $$v_1$$. We can then compute the action of $$V_k$$ on any $$x$$ by applying each reflection individually: \begin{aligned} x_1 &= \frac{-v_1xv_1}{v_1^2} = x - 2\frac{x\cdot v_1}{v_1^2}v_1, \\ x_2 &= \frac{-v_2x_1v_2}{v_2^2} = x_1 - 2\frac{x_1\cdot v_2}{v_2^2}v_2, \\ &\;\;\vdots \\ x = x_k &= \frac{-v_kx_{k-1}v_k}{v_k^2} = x_{k-1} - 2\frac{x_{k-1}\cdot v_k}{v_k^2}v_k. \end{aligned} \tag{*} Hence any basis $$\{e_i\}_{i=1}^d$$ of $$\R^d$$ may be chosen, the action of $$V_k$$ on this basis computed, and a matrix $$R$$ computed; explicitly $$R_{ij} = e_i\cdot\left(\frac{\rev V_ke_jV_k}{|V_k|^2}\right) = e_i\cdot(e_j)_k$$ where $$(e_j)_k$$ is the result of apply the above process ($$*$$) to $$e_j$$. The eigenvalues of $$R$$ are $$\lambda_1,\conj\lambda_1,\dotsc,\lambda_m,\conj\lambda_m, \underbrace{1,\cdots,1}_{d-2m\text{ times}},$$ where $$\conj\lambda_j$$ is complex conjugation and where we may take $$\lambda_j = \cos\theta_j + i\sin\theta_j$$. Note that $$d - 2m$$ is $$0$$ if $$d$$ is even and $$1$$ if $$d$$ is odd. Since $$|\cos(\theta/2)| = \sqrt{\frac12 + \frac12\cos\theta}$$, we arrive at $$\grade{V_k} = \pm|V_k|\prod_{j=1}^m\sqrt{\frac12 + \frac12\Re\lambda_j}.$$

• Thank you for your answer! When you say that $V_k/|V_k| \in Spin(d)$ "acts" I take it to mean "acts on $\mathbb{R}^d$". This action is the one that factors through the group morphism $Spin(d) \to O(d)$. Do I interpret you correctly? If that is the case, then I don't see how it is enough to look at how $V_k$ acts. Perhaps it is enough "up to a sign", given that $Spin(d) \to O(d)$ is a double-cover? For instance, it seems that your last expression is always positive, but the scalar part in the original question can be negative. Jun 24, 2022 at 21:20
• Yes, you're right about everything, and you're observation that you can't get the sign is definitely something I missed. I'll edit to include that. It's not obvious to me how you would determine the sign. Jun 24, 2022 at 22:18
• @luisl I have a conjecture which I've verified for $k=2,4,6$. Let $P_k$ be the set of all sets of all disjoint pairs $(i,j)$ with $i,j\in\{1,\dotsc,k\}$ and $i<j$. For $k=4$, $$P_4=\{\{(1,2),(3,4)\},\{(1,3),(2,4)\},\{(1,4),(2,3)\}\}.$$ Then $$\langle v_1\cdots v_k\rangle=\sum_{S\in P_k}\mathrm{sgn}(S)\prod_{(i,j)\in S}v_i\cdot v_j,$$ where $\mathrm{sgn}(S)$ is the sign of the permutation you get from "flattening" any ordering of $S$, e.g. $$\mathrm{sgn}(\{(1,3),(2,4)\})=\mathrm{sgn}(1,3,2,4)=-1.$$ Jun 25, 2022 at 1:38
• Can the new expression be computed efficiently? It seems that the size of $P_k$ is not polynomial in $k$. Jun 25, 2022 at 14:55
• @luisl I believe the size of $P_k$ is $$\frac1{(k/2)!}\binom k2\binom{k-2}2\cdots\binom22,$$ so no, not polynomial. I have to wonder if it can be massaged into some sort of determinant though. I don't know if you're aware, but when $v_1,\dotsc, v_{k/2}$ are mutually orthogonal and $v_{k/2+1},\dotsc,v_k$ are mutually orthogonal, then we have $$\langle v_1\cdots v_{k/2}v_{k/2+1}\cdots v_k\rangle=\det(V),$$ $$V_{ij}=v_{k/2+1-i}\cdot v_{k/2+j},\quad 1\leq i,j\leq k/2.$$ I imagine the fact that $\langle v_1\cdots v_k\rangle$ is invariant under cyclic permutation is somehow exploitable as well. Jun 25, 2022 at 16:02