Efficient computation of scalar part in Clifford algebra

Question

$\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.

Answer 1

$ \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}. $$