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


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

  • 1
    $\begingroup$ 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. $\endgroup$
    – apeman
    Jun 24, 2022 at 21:20
  • $\begingroup$ 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. $\endgroup$ Jun 24, 2022 at 22:18
  • 1
    $\begingroup$ @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.$$ $\endgroup$ Jun 25, 2022 at 1:38
  • $\begingroup$ Can the new expression be computed efficiently? It seems that the size of $P_k$ is not polynomial in $k$. $\endgroup$
    – apeman
    Jun 25, 2022 at 14:55
  • 1
    $\begingroup$ @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. $\endgroup$ Jun 25, 2022 at 16:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .