9
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
5
  • 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$
    – george
    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$
    – george
    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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.