Is the product of two unitary Householder matrices necessarily of finite order?

Question

Let $\mathbf A$ and $\mathbf B$ be two unitary Householder matrices. They do not necessarily commute. Is $\mathbf{AB}$ necessarily of finite order (i.e. $\exists$ $n\in \Bbb N$ s.t. $(\mathbf{AB})^n = \mathbb I$)?

If not, under what conditions on $\mathbf {A}$ and $\mathbf{B}$ would $\mathbf{AB}$ definitely be of finite order?

Note: This question arose in the context of Grover's algorithm. In that case $\mathbf{A} = U_s$ and $\mathbf{B} = U_\omega$. I want to know whether $(U_sU_\omega)^r|s\rangle$ necessarily coincides with $|s\rangle$ after a certain number of iterations $r$.

Answer 1

The matrices $$ A=\begin{bmatrix} 0 & -1 \\ -1 & 0 \end{bmatrix} \qquad B=\begin{bmatrix} 1 & 0 \\ -2 & 1 \end{bmatrix} $$ are Householder, but the eigenvalues of $AB$ are $-1\pm\sqrt{2}$.

Answer 2

Consider two arbitrary householder transformations $S_\psi\equiv I-2 P_\psi$ and $S_\phi\equiv I-2 P_\phi$, where $P_\psi,P_\phi$ are projectors onto the (not necessarily orthogonal) normalised vectors $\psi,\phi$. Define the unitary $U\equiv S_\psi S_\phi$. Then, $$ U =I-2(P_\psi+P_\phi)+4 P_\psi P_\phi. $$ Define the vector $\phi_\perp$ as the projection of $\psi$ onto the space orthogonal to $\phi$: $\phi_\perp\equiv N(1-P_\phi) \psi$, with $N$ normalisation constant. Let $V$ be the two-dimensional subspace generated by $\phi$ and $\phi_\perp$: $\mathcal V\equiv\operatorname{span}(\phi,\phi_\perp)$. Clearly, $\psi\in\mathcal V$, and $Uv=v$ for any $v\notin\mathcal V$.

On the other hand, we know that $U$ is unitary, being it a product of two unitaries. It follows that $U$ splits as $$U=I_{\mathcal V_\perp}\oplus U_{\mathcal V},$$ where $I_{\mathcal V_\perp}$ is the identity matrix in $\mathcal V_\perp$, and $U_{\mathcal V}$ is an $\mathrm{SU}(2)$ rotation in $\mathcal V$ (the fact that it has unit determinant follows from it being a product of two reflections, which have each determinant equal to $-1$).

This reduces the question to when is an $\mathrm{SU}(2)$ matrix idempotent? Let then $A$ be an arbitrary SU(2) matrix. The eigenvalues of $A$ must then be of the form $e^{\pm i\theta}$ for some $\theta\in\mathbb R$. Then, $A^r$ has eigenvalues $e^{\pm ir\theta}$. To have $A^r=I$ we need an $r\in\mathbb N$ such that $r\theta=2\pi k$ for some integer $k$. This is only possible if $\theta=2\pi k/r$, that is, when $\theta$ is a rational multiple of $2\pi$. When this is the case, we can write $\theta=2\pi p/q$ for $p,q$ coprime integers, and then $e^{\pm ir\theta}=1$ for $r=q$.

Going back to Householder transformations, the requirement that $U$ must be idempotent translates into the requirement that the angle of the corresponding SU(2) transformation must be in $2\pi\mathbb Q$. We now only need to find the connection between the angle (equivalently, the eigenvalues) of this SU(2) transformation, and the initial vectors $\phi,\psi$, which can be shown to be $\theta=2\arccos|\langle\psi,\phi\rangle|$. See also this related answer on quantumcomputing.SE for more explicit calculations.