THE COMPLEXITY OF THE QUATERNION PRODUCT*

Thomas D. Howell

Jean-Claude Lafon^{1}**

TR 75-245

June 1975^{2}

Department of Computer Science, Cornell University, Ithaca, N.Y.

* This research was supported in part by the National Science Foundation Graduate Fellowship and the Office of Naval Research Grant N00014-67-A-0077-0021. ** Universite Scientifique et Medicale de Grenoble, Tour des Mathematiques, B.P. 53, 38041 Grenoble, France.

Abstract:

Let X and Y be two quaternions over an arbitrary ring. Eight multiplications are necessary and sufficient for computing the product XY. If the ring is assumed to be commutative, at least seven multiplications are still necessary and eight are sufficient.

1. Introduction

Real quaternions are elements of the division ring over the reals generated by the elements i, j, k satisfying i^{2} = j^{2} = k^{2} = −1, ij = −ji = k, jk = −kj = i and ki = −ik = j. If x_{n}, y_{n} ∈ R for n = 1, 2, 3, 4, then X = x_{1} + x_{2}i + x_{3} j + x_{4}k and Y = y_{1} + y_{2}i + y_{3} j + y_{4}k are quaternions and their product is:

XY = (x_{1}y_{1} − x_{2}y_{2} − x_{3}y_{3} − x_{4}y_{4})
+ (x_{1}y_{2} + x_{2}y_{1} + x_{3}y_{4} − x_{4}y_{3}) i
+ (x_{1}y_{3} − x_{2}y_{4} + x_{3}y_{1} + x_{4}y_{2}) j
+ (x_{1}y_{4} + x_{2}y_{3} − x_{3}y_{2} + x_{4}y_{1}) k

Real quaternions satisfy N(X) ≡ x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2} > 0 if X ≠ 0 and N(XY) = N(X) N(Y). They are important because of their usefulness in calculations arising in physics and mathematics.

1Now at the University of Nice (jcl@mimosa.unice.fr)

2Retyped and converted to TeX from a TIFF G4 600dpi scanned image of the original obtained from the Cornell Computer Science WWW site (also now stored at http://home.pipeline.com/~hbaker1/quaternion/cornellcstr75-245.tar.gz), November, 1995, by Henry G. Baker (hbaker1@pipeline.com), and posted on the Internet (http://home.pipeline.com/~hbaker1/quaternion/cornellcstr75-245.dvi.gz and .ps.gz)

with the permission of Jean-Claude Lafon.

Although real quaternions are most often used, the quaternion product as defined above can be computed when the x_{n}’s and y_{n}’s are elements of an arbitrary ring. We are interested in the complexity of this computation. The complexity of an algorithm is measured by the number of ring multiplications it requires. The obvious algorithm for computing the quaternion product uses 16 multiplications. The complexity of the quaternion product is the complexity of the least complex algorithm computing it.

Two cases must be considered when discussing the complexity of quaternion multiplication over a ring, the general case and the commutative case. The general case considers only those algorithms which correctly compute the quaternion product over any ring.

The commutative case allows, in addition to these, algorithms which work only in commutative rings. Commutative algorithms are important because the real numbers are commutative. Clearly the complexity of the quaternion product, or any computation, in the commutative case is not greater than the complexity of the same computation in the general case.

The problem of determining the complexity of the quaternion product is a special case of the problem of determining the complexity of a set of bilinear forms. A number of other special cases appear in the literature. For example, Strassen [1] shows that seven multiplications are sufficient for the product of 2 × 2 matrices. Hopcroft and Kerr [2] and Winograd [3] show that seven multiplications are also necessary in the general and commutative cases, respectively. Fiduccia [4] mentions that ten multiplications are sufficient for the quaternion product. It has been shown by de Groote that ten are necessary and sufficient to compute the quaternion products XY and Y X simultaneously. The complexity of arbitrary sets of bilinear forms has been studied by Gastinel [6] and Musinski [7], but useful results are known only for sets of size one or two.

The purpose of this paper is to show that eight multiplications are necessary and sufficient for the quaternion product in the general case, and that at least seven multiplications are necessary in the commutative case.

2. Model of Computation

The following definitions make precise the notion of an algorithm and its complexity.

Definition. Let F be a field and {x_{1}, x_{2}, ..., x_{n}} be a set of indeterminates. An algorithm is a finite sequence of steps, α = {α_{1}, α_{2}, ..., α_{s}}, where each step, α_{i}, is of one of three forms:

(i) g_{i} ← x_{j}, 1 ≤ j ≤ n (ii) g_{i} ← a, a ∈ F (iii) g_{i} ← g_{j}θg_{k}, j < i, k < i and θ ∈ {+, −, ×}.

Note that each g_{i} is an element of F [x_{1}, ..., x_{n}], the ring of polynomials in x_{1}, ..., x_{n} with coefficients from F. An algorithm α is said to compute a set E ⊆ F [x_{1}, ..., x_{n}] if E ⊆ {g_{1}, ..., g_{s}}.

Definition. The complexity of an algorithm is equal to the number of steps of the form g_{i} ← g_{j} × g_{k} where g_{j} ∉ F and g_{k} ∉ F. Such steps are called active multiplications. The x_{i}’s are the input data to the algorithm. Only multiplications which

depend on the data are counted. Multiplications by scalars (elements of F) are ignored.

The complexity of a computation may depend on the choice of F, the field of scalars. For example, x_{1}^{2} + x_{2}^{2} requires two active multiplications when F is the reals. When F is the complex numbers, x_{1}^{2} + x_{2}^{2} = (x_{1} + ix_{2})(x_{1} − ix_{2}) requires just one active multiplication. Throughout this paper F is assumed to satisfy the following condition: For all a, b, c, d, ∈ F

a^{2} + b^{2} + c^{2} + d^{2} = 0 if and only if a = b = c = d = 0.  (∗)

The reals and the rationals satisfy (*), but the complex numbers and all finite fields do not. A counterexample will show that our theorems do not hold when F is the complexes.

3. Tensor Rank

Let {M_{k}}_{k=1}^{p} be a set of m × n matrices over F. Let x^{t} = [x_{1}, ..., x_{m}] and y^{t} = [y_{1}, ..., y_{n}] be the vectors of indeterminates. Let f_{k} be the bilinear form represented by M_{k} : f_{k} = x^{t}M_{k}y for k = 1, ..., p. The following theorem is known [8], [9]. Theorem 1. If α is an algorithm of complexity q computing f_{1}, ..., f_{p} in the general case (commutativity is not assumed) then there is an algorithm α′ of complexity q computing f_{1}, ..., f_{p} in which all active multiplications are the form (u_{ℓ}^{t}x) · (v_{ℓ}^{t}y) where u_{ℓ} ∈ F^{m}, v_{ℓ} ∈ F^{n} for ℓ = 1, 2, ..., q. Then

[ \begin{matrix}f_{1} \\ f_{2} \\ . \\ . \\ . \\ f_{p} \end{matrix} ] = W [ \begin{matrix}(u_{1}^{t}x) · (v_{1}^{t}y) \\ (u_{2}^{t}x) · (v_{2}^{t}y) \\ · \\ · \\ · \\ (u_{q}^{t}x) · (v_{q}^{t}y) \end{matrix} ]

where W is a p × q matrix over F.

Let z^{t} = [z_{1}, ..., z_{p}] be another vector of indeterminates.

The trilinear form

T = ∑_{k=1}^{p} f_{k}z_{k} = ∑_{i,j,k} m_{ijk} x_{i} y_{j} z_{k}

is represented by M = (m_{ijk})_{i=1}^{m} _{j=1}^{n} _{k=1}^{p} ∈ F^{m} ⊗ F^{n} ⊗ F^{p}. Note that m_{ijk} is the i, j element of M_{k}.

Definition. The tensor rank of the set {M_{k}}_{k=1}^{p} (or simply of M) is the smallest integer q for which

M = ∑_{ℓ=1}^{q} u_{ℓ} ⊗ v_{ℓ} ⊗ w_{ℓ}

where u_{ℓ} ∈ F^{m}, v_{ℓ} ∈ F^{n}, w_{ℓ} ∈ F^{p} for ℓ = 1, ..., q, and ⊗ denotes tensor product (outer product). When p = 1, the tensor rank of the set {M_{1}} is equal to the rank of the

matrix M_{1}. The next theorem shows the importance of tensor rank. Theorem 2. The tensor rank of the set {M_{k}}_{k=1}^{p} is equal to the minimum number of active multiplications required to compute the bilinear forms f_{k} = x^{t}M_{k}y, k = 1, ..., p, in the general case. Proof: Assume q active multiplications suffice. By Theorem 1

f_{k} = ∑_{ℓ=1}^{q} w_{kℓ}(u_{ℓ}^{t}x)(v_{ℓ}^{t}y).

Let w_{ℓ}^{t} = [w_{1ℓ}, ..., w_{pℓ}]. Then

T = ∑_{i,j,k} m_{ijk} x_{i} y_{j} z_{k} = ∑_{k=1}^{p} f_{k}z_{k} = ∑_{ℓ=1}^{q}(u_{ℓ}^{t}x)(v_{ℓ}^{t}y)(w_{ℓ}^{t}z),

which implies

M = ∑_{ℓ=1}^{q} u_{ℓ} ⊗ v_{ℓ} ⊗ w_{ℓ}.

Hence the tensor rank of M is at most q. The reverse argument shows that if the tensor rank of M is q then q active multiplications suffice to compute f_{1}, ..., f_{p}.

It will often be more convenient to represent the three-dimensional object M in two dimensions as M(z) = ∑_{k=1}^{p} M_{k}z_{k}. Then Theorem 2 says that the complexity of the set of bilinear forms f_{1}, ..., f_{p} is equal to the smallest q such that

M(z) = ∑_{ℓ=1}^{q} u_{ℓ} ⊗ v_{ℓ}(w_{ℓ}^{t}z) = ∑_{ℓ=1}^{q} u_{ℓ}v_{ℓ}^{t}(w_{ℓ}^{t}z) ([10]).

Thus, q is the minimum number of rank-one matrices (depending on z) into which M(z) can be decomposed. This will be referred to as the tensor rank of M(z).

Example. Let M_{1} = [ \begin{matrix}1 & 0 \\ 0 & −1 \end{matrix} ] , M_{2} = [ \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ]. Then

M(z) = [ \begin{matrix}z_{1} & z_{2} \\ z_{2} & −z_{1} \end{matrix} ]
=  [ \begin{matrix}z_{2} & z_{2} \\ z_{2} & z_{2} \end{matrix} ]  +  [ \begin{matrix}z_{1} − z_{2} & 0 \\ 0 & 0 \end{matrix} ]  +  [ \begin{matrix}0 & 0 \\ 0 & −z_{1} − z_{2} \end{matrix} ]
= [ \begin{matrix}1 \\ 1 \end{matrix} ] [ 1 1 ] (z_{2}) + [ \begin{matrix}1 \\ 0 \end{matrix} ] [ 1 0 ] (z_{1} − z_{2}) + [ \begin{matrix}0 \\ 1 \end{matrix} ] [ 0 1 ] (−z_{1} − z_{2})

hence the tensor rank of M(z) is at most three.

\begin{aligned}T & = (x_{1}y_{1} − x_{2}y_{2})z_{1} + (x_{1}y_{2} + x_{2}y_{1})z_{2} \\ & = (x_{1} + x_{2})(y_{1} + y_{2})z_{2} + x_{1}y_{1}(z_{1} − z_{2}) + x_{2}y_{2}(−z_{1} − z_{2}) \end{aligned}

This leads to

[ \begin{matrix}x_{1}y_{1} − x_{2}y_{2} \\ x_{1}y_{2} + x_{2}y_{1} \end{matrix} ] = [ \begin{matrix}0 & 1 & −1 \\ 1 & −1 & −1 \end{matrix} ] [ \begin{matrix}(x_{1} + x_{2}) · (y_{1} + y_{2}) \\ x_{1} · y_{1} \\ x_{2} · y_{2} \end{matrix} ]

which is of the form given in Theorem 1.

For the general case, Theorem 2 has characterized the complexity of a set of bilinear forms in terms of the tensor rank of the coefficients. The same can be done for the commutative case.

Let M(z) be as above. Theorem 3. The commutative complexity of the bilinear forms f_{1}, ..., f_{p} is equal to the minimum possible tensor rank of N(z) where

N(z) + N(z)^{t} = [ \begin{matrix}0 & M(z) \\ M(z)^{t} & 0 \end{matrix} ] .

This follows from a theorem analogous to Theorem 1, which states that in the commutative case there is a minimal complexity algorithm in which the active multiplications have the form (u_{ℓ}^{t}x + v_{ℓ}^{t}y)(ũ_{ℓ}^{t}x + ṽ_{ℓ}^{t}y) where u_{ℓ}, ũ_{ℓ} ∈ R^{m} and v_{ℓ}, ṽ_{ℓ} ∈ R^{n}. See Lafon [9] for a proof.

Note that the choice

N(z) = [ \begin{matrix}0 & M(z) \\ 0 & 0 \end{matrix} ]

is possible, hence the commutative complexity is not greater than the general complexity of a set of bilinear forms.

4. Upper Bound

In this section an algorithm will be given which computes the quaternion product in the general case using eight active multiplications.

The quaternion product consists of four bilinear forms:

\begin{aligned}f_{1} & = x^{t}M_{1}y = x_{1}y_{1} − x_{2}y_{2} − x_{3}y_{3} − x_{4}y_{4} \\ f_{2} & = x^{t}M_{2}y = x_{1}y_{2} + x_{2}y_{1} + x_{3}y_{4} − x_{4}y_{3} \\ f_{3} & = x^{t}M_{3}y = x_{1}y_{3} − x_{2}y_{4} + x_{3}y_{1} + x_{4}y_{2} \\ f_{4} & = x^{t}M_{4}y = x_{1}y_{4} + x_{2}y_{3} − x_{3}y_{2} + x_{4}y_{1} \end{aligned}

By the results of section 3, the desired algorithm corresponds to a decomposition of M(z) as a sum of eight rank-one matrices, where

N(z) = ∑_{k=1}^{4} M_{k}z_{k} = [ \begin{matrix}z_{1} & z_{2} & z_{3} & z_{4} \\ z_{2} & −z_{1} & z_{4} & −z_{3} \\ z_{3} & −z_{4} & −z_{1} & z_{2} \\ z_{4} & z_{3} & −z_{2} & −z_{1} \end{matrix} ] .

First, write M(z) = M′(z) + M′′(z) where

\begin{aligned}M′(z) & = [ \begin{matrix}−z_{1} & z_{2} & z_{3} & z_{4} \\ z_{2} & −z_{1} & z_{4} & z_{3} \\ z_{3} & z_{4} & −z_{1} & z_{2} \\ z_{4} & z_{3} & z_{2} & −z_{1} \end{matrix} ] \\ M′′(z) & = 2 [ \begin{matrix}z_{1} & 0 & 0 & 0 \\ 0 & 0 & 0 & −z_{3} \\ 0 & −z_{4} & 0 & 0 \\ 0 & 0 & −z_{2} & 0 \end{matrix} ] \end{aligned}

Obviously, M′′(z) is representable as a sum of four rank-one matrices. So is M′(z):

4M′(z) =

(−z_{1}+z_{2}+z_{3}+z_{4}) [ \begin{matrix}1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{matrix} ]+(−z_{1}+z_{2}−z_{3}−z_{4}) [ \begin{matrix}1 & 1 & −1 & −1 \\ 1 & 1 & −1 & −1 \\ −1 & −1 & 1 & 1 \\ −1 & −1 & 1 & 1 \end{matrix} ] +

(−z_{1}−z_{2}+z_{3}−z_{4}) [ \begin{matrix}1 & −1 & 1 & −1 \\ −1 & 1 & −1 & 1 \\ 1 & −1 & 1 & −1 \\ −1 & 1 & −1 & 1 \end{matrix} ]+(−z_{1}−z_{2}−z_{3}+z_{4}) [ \begin{matrix}1 & −1 & −1 & 1 \\ −1 & 1 & 1 & −1 \\ −1 & 1 & 1 & −1 \\ 1 & −1 & −1 & 1 \end{matrix} ]

The corresponding algorithm is :

[I] = x_{1}y_{1}  [II] = x_{4}y_{3}  [III] = x_{2}y_{4}  [IV] = x_{3}y_{2}

[V] = (x_{1} + x_{2} + x_{3} + x_{4})(y_{1} + y_{2} + y_{3} + y_{4})
[VI] = (x_{1} + x_{2} − x_{3} − x_{4})(y_{1} + y_{2} − y_{3} − y_{4})
[VII] = (x_{1} − x_{2} + x_{3} − x_{4})(y_{1} − y_{2} + y_{3} − y_{4})
[VIII] = (x_{1} − x_{2} − x_{3} + x_{4})(y_{1} − y_{2} − y_{3} + y_{4})
f_{1} = 2[I] − \frac{[V] + [VI] + [VII] + [VIII]}{4}
f_{2} = −2[II] + \frac{[V] + [VI] − [VII] − [VIII]}{4}
f_{3} = −2[III] + \frac{[V] − [VI] + [VII] − [VIII]}{4}
f_{4} = −2[IV] + \frac{[V] − [VI] − [VII] + [VIII]}{4}

This shows that the complexity of the quaternion product is at most eight in both the general case and the commutative case.

5. Transformations

An algorithm computing the bilinear forms, S = {x^{t}M_{k}y : k = 1, ..., p}, can often be transformed into a new algorithm computing the same forms by substituting for each x_{i} a linear combination of the x_{i}’s and for each y_{j} a linear combination of the y_{j}’s and then taking new linear combinations of the resulting active multiplications.

Definition. Let A, B, and C be nonsingular matrices over F of order m, n and p, respectively. The ordered triple, (A, B, C), is a transformation on the set S if it leaves the trilinear form representing S invariant:

∑_{i,j,k} m_{ijk}(Ax)_{i}(By)_{j}(Cz)_{k} = ∑_{i,j,k} m_{ijk} x_{i} y_{j} z_{k}.

The transformations on a given set of forms form a group under composition. Given an algorithm computing S and a transformation, (A, B, C), a new

algorithm of the same complexity can be formed by first computing x′ = Ax and y′ = By using no active multiplications. The original algorithm applied to x′ and y′ computes the coefficients f′ = [f′_{1}, ..., f′_{p}]^{t} of z′ = Cz in the expression ∑_{i,j,k} m_{ijk} x′_{i} y′_{j} z′_{k}. The desired forms, S, which are the coefficients, f = [f_{1}, ..., f_{p}], of z are recovered by computing f^{′t}C = f^{t} using no active multiplications. Example.

Let

A = [ \begin{matrix}1 & 1 & 0 & 0 \\ −1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & −1 & 0 \end{matrix} ]  B = [ \begin{matrix}1 & 1 & 0 & 0 \\ −1 & 1 & 0 & 0 \\ 0 & 0 & 1 & −1 \\ 0 & 0 & 1 & 1 \end{matrix} ]  C = \frac{1}{4}AB

The reader can verify by direct computation that (A, B, C) is a transformation on the quaternion product. When applied to the algorithm of section 4, it yields the following algorithm:

[I] = (x_{1} + x_{2})(y_{1} + y_{2})  [V] = (x_{2} + x_{4})(y_{2} + y_{3})
[II] = (x_{4} − x_{3})(y_{3} − y_{4})  [VI] = (x_{2} − x_{4})(y_{2} − y_{3})
[III] = (x_{2} − x_{1})(y_{3} + y_{4})  [VII] = (x_{1} + x_{3})(y_{1} − y_{4})
[IV] = (x_{3} + x_{4})(y_{2} − y_{1})  [VIII] = (x_{1} − x_{3})(y_{1} + y_{4})
f_{1} = [II] + \frac{−[V] − [VI] + [VII] + [VIII]}{2}
f_{2} = [I] − \frac{[V] + [VI] + [VII] + [VIII]}{2}
f_{3} = −[III] + \frac{[V] − [VI] + [VII] − [VIII]}{2}
f_{4} = −[IV] + \frac{[V] − [VI] − [VII] + [VIII]}{2}

6. Lower Bound : General Case

The purpose of this section is to prove the following theorem. Theorem 4. Any algorithm which computes the quaternion product over arbitrary rings using scalars from F requires at least eight active multiplications.

Recall the assumption (*) about F: for all a, b, c, d, ∈ F, a^{2} +b^{2} +c^{2} +d^{2} = 0 if and only if a = b = c = d = 0. The proof will use this assumption in several places. Two lemmas contain most of the proof. Lemma 1. If there is an algorithm which computes the quaternion product using q active multiplications, then there is also an algorithm of the same complexity in which one active multiplication is by x_{1} and another is by y_{1}. Proof. Let a_{1}, a_{2}, a_{3}, a_{4} be elements of F, not all zero. Let d(a) = a_{1}^{2} + a_{2}^{2} + a_{3}^{2} + a_{4}^{2} ≠ 0 and

A = 1/d(a) [ \begin{matrix}a_{1} & −a_{2} & −a_{3} & −a_{4} \\ a_{2} & a_{1} & −a_{4} & a_{3} \\ a_{3} & a_{4} & a_{1} & −a_{2} \\ a_{4} & −a_{3} & a_{2} & a_{1} \end{matrix} ]

Let I be the 4 × 4 identity matrix. A direct computation shows that T_{A} = (A, I, d(a)A) is a transformation on the quaternion product.

If there is an algorithm computing the quaternion product using q active multiplications, then by Theorem 1 there is also one of the form

W [ \begin{matrix}(u_{1}^{t}x) · (v_{1}^{t}y) \\ . \\ . \\ . \\ (u_{q}^{t}x) · (v_{q}^{t}y) \end{matrix} ] = [ \begin{matrix}f_{1} \\ f_{2} \\ f_{3} \\ f_{4} \end{matrix} ]

.

Call this algorithm α. Note that no u_{i} or v_{i} can be the zero vector, otherwise the corresponding multiplication would not be active.

Let u_{1}^{T} = [ u_{11} u_{21} u_{31} u_{41} ]. Then the transformation T_{A} with [ a_{1} a_{2} a_{3} a_{4} ] = [ u_{11} u_{21} u_{31} u_{41} ] when applied to α produces a new algorithm α′ in which the first multiplication is u_{1}^{t}(Ax) · v_{1}^{t}(Iy) = x_{1} · v_{1}^{t}y.

Similarly, T_{B} = (I, B, d(b)B) is a transformation if

B = 1/d(b) [ \begin{matrix}b_{1} & −b_{2} & −b_{3} & −b_{4} \\ b_{2} & b_{1} & b_{4} & −b_{3} \\ b_{3} & −b_{4} & b_{1} & b_{2} \\ b_{4} & b_{3} & −b_{2} & b_{1} \end{matrix} ]

and b_{1}, b_{2}, b_{3}, b_{4} ∈ F are not all zero. When [ b_{1} b_{2} b_{3} b_{4} ] = v_{2}^{t}, T_{B} transforms α′ into α′′ in which the first two multiplications are x_{1} · v_{1}^{′t}y and u_{2}^{′t}x · y_{1}, where v_{1}^{′t} = v_{1}^{t}B and u_{2}^{′t} = u_{2}^{t}A. Lemma 2. Any algorithm which computes the quaternion product of x_{2}i + x_{3} j + x_{4}k and y_{2}i + y_{3} j + y_{4}k in the general case, using scalars from F requires at least six active multiplications. Proof. The trilinear form T′ associated with this computation is:

\begin{aligned}T′ & = (−x_{2}y_{2} − x_{3}y_{3} − x_{4}y_{4})z_{1} + (x_{3}y_{4} − x_{4}y_{3})z_{2} \\ & + (−x_{2}y_{4} + x_{4}y_{2})z_{3} + (x_{2}y_{3} − x_{3}y_{2})z_{4} \end{aligned}

By Theorem 2, the least number of active multiplications needed to compute this product is equal to the tensor rank of the matrix

M′(z) = [ \begin{matrix}−z_{1} & z_{4} & −z_{3} \\ −z_{4} & −z_{1} & z_{2} \\ z_{3} & −z_{2} & −z_{1} \end{matrix} ]

As the determinant of this matrix is equal to −z_{1}(z_{1}^{2} + z_{2}^{2} + z_{3}^{2} + z_{4}^{2}), M′(z) is of rank three if z_{1} ≠ 0.

Let q be the tensor rank of M′(z). M′(z) = ∑_{ℓ=1}^{q} u_{ℓ}v_{ℓ}^{t}(w_{ℓ}^{t}z), u_{ℓ} ∈ F^{3}, v_{ℓ} ∈ F^{3}, w_{ℓ} ∈ F^{4}. There must exist four linearly independent vectors among the w_{ℓ}, (ℓ = 1, ..., q), as M′(z) depends on four independent parameters. Assume w_{1}, w_{2}, w_{3}, w_{4} are linearly independent. There exists z^{∘} with z_{1}^{∘} ≠ 0 such that:

w_{1}^{t}z^{∘} = 0,  w_{2}^{t}z^{∘} = 0,  w_{3}^{t}z^{∘} = 0.

For this choice of z^{∘},

M′(z^{∘}) = ∑_{ℓ=4}^{q} u_{ℓ}v_{ℓ}^{t}(w_{ℓ}^{t}z^{∘})

Since z_{1}^{∘} ≠ 0, M′(z^{∘}) is of rank three and therefore 3 ≤ q − 3 which implies q ≥ 6. Proof of Theorem 4. Suppose that there is an algorithm computing the quaternion product with only 7 active multiplications. By Lemma 1 there is another algorithm requiring only 7 in which one active multiplication is by x_{1} and one is by y_{1}. Setting x_{1} = y_{1} = 0 in this algorithm produces a new algorithm computing the product of x_{2}i + x_{3} j + x_{4}k and y_{2}i + y_{3} j + y_{4}k with only 5 active multiplications. By Lemma 4 this is impossible.

The algorithms given in sections 4 and 5 attain the lower bound given by Theorem 4. Thus, the complexity of the quaternion product in the general case is exactly eight. Combined with Theorem 2 this fact can be restated in the following way: Corollary. The tensor rank of

M(z) = [ \begin{matrix}z_{1} & z_{2} & z_{3} & z_{4} \\ z_{2} & −z_{1} & z_{4} & −z_{3} \\ z_{3} & −z_{4} & −z_{1} & z_{2} \\ z_{4} & z_{3} & −z_{2} & −z_{1} \end{matrix} ]

is eight.

7. Lower Bound : Commutative Case

Theorem 5. Any algorithm which computes the quaternion product over commutative rings using scalars from F requires at least seven active multiplications. Proof. Let q be the minimum number of active multiplications required. Theorem 3 states that q is the minimum tensor rank of any N(z) satisfying

N(z) + N(z)^{t} = [ \begin{matrix}0 & M(z) \\ M(z)^{t} & 0 \end{matrix} ] .  (1)

(M(z) is defined in section 4). Then we can write

N(z) = ∑_{ℓ=1}^{q} u_{ℓ}v_{ℓ}^{t}(w_{ℓ}^{t}z), u_{ℓ} ∈ F^{8}, v_{ℓ} ∈ F^{8}, w_{ℓ} ∈ F^{4} for ℓ = 1, ..., q. (2)

The matrix N(z) depends on four independent parameters z_{1}, ..., z_{4} (from (1)). Therefore we must have four vectors w_{ℓ} linearly independent in the expression (2) for N(z). Assume w_{1}, w_{2}, w_{3} and w_{4} are linearly independent. The components of z can be assigned values from F to satisfy the following system of equations:

w_{1}^{t}z = 0,  w_{2}^{t}z = 0,  w_{3}^{t} = 0.

Let z^{∘} ∈ F^{4} be a nontrivial solution of this system (z^{∘} ≠ 0):

z^{∘}^{t} = [ z_{1}^{∘} z_{2}^{∘} z_{3}^{∘} z_{4}^{∘}] .

For this choice of z,

N(z^{∘}) = ∑_{ℓ=4}^{q} u_{ℓ}v_{ℓ}^{t}(w_{ℓ}^{t}z^{∘}).

N(z^{∘}) is expressed as a linear combination of q −3 rank-one matrices, therefore

Rank(N(z^{∘})) ≤ q − 3.

But we have also:

N(z^{∘}) + N(z^{∘})^{t} = [ \begin{matrix}0 & M(z^{∘}) \\ M(z^{∘})^{t} & 0 \end{matrix} ] .

A brief calculation shows that

det(M(z^{∘})) = −((z_{1}^{∘})^{2} + (z_{2}^{∘})^{2} + (z_{3}^{∘})^{2} + (z_{4}^{∘})^{2})^{2}.

From the fact that z^{∘} is an element of F^{4} not equal to zero and assumption (*), we deduce that det(M(z^{∘})) ≠ 0, and therefore

Rank(N(z^{∘}) + N(z^{∘})^{t}) = 8.

But Rank(N(z^{∘}) + N(z^{∘})^{t}) ≤ 2 Rank(N(z^{∘})) ≤ 2(q − 3), so 8 ≤ 2(q − 3) implies q ≥ 7.

8. A Counterexample

The proofs of the lower bounds in both the general and commutative cases depend on the assumption (*) that the equation, a^{2} + b^{2} + c^{2} + d^{2} = 0, has no nontrivial solutions in F. For example, (*) does not hold if F is the complex numbers. The following example will show that Theorem 4 is not true with this choice of F.

With the real quaternion X = x_{1} + x_{2}i + x_{3} j + x_{4}k we can associate the following 2 × 2 complex matrix.

[ \begin{matrix}X_{1} & X_{2} \\ −X̄_{2} & X̄_{1} \end{matrix} ] X_{1} = x_{1} + x_{2}i, X_{2} = x_{3} + x_{4}i

This mapping is an isomorphism between quaternions and the set of matrices of this type. The product of two quaternions can be viewed as the product of two such complex matrices. From the result of Strassen [1], this product can be performed in seven complex multiplications (in fact, six complex and one real multiplication).^{3}

The same construction yields an algorithm for multiplying quaternions over an arbitrary ring with seven “complex” multiplications, where a “complex” multiplication means the construction of (x_{1}y_{1} − x_{2}y_{2}) + (x_{1}y_{2} + x_{2}y_{1})i from x_{1} + x_{2}i and y_{1} + y_{2}i, and x_{1}, x_{2}, y_{1} and y_{2} are ring elements.

9. Conclusion

For the general case the complexity of the quaternion product is exactly eight. For the commutative case the complexity is either seven or eight. No algorithm is known which uses commutativity to advantage in computing the quaternion product. Such an algorithm or a proof that none exists would eliminate the gap between the upper and lower bounds in the commutative case.

It has recently come to the authors’ attention that some of the results reported here have been previously obtained. The upper bound of section 4 appears in Dobkin [11]. The lower bound for the general case has been proven by de Groote [12].

References

[1] Strassen, V., Gaussian elimination is not optimal, Numer. Math., 13 (1969), 354–356.

[2] Hopcroft, J.E., and L.R. Kerr, On minimizing the number of multiplications necessary for matrix multiplication, SIAM J. Appl. Math., 20 (1971), 30–35.

[3] Winograd, S., On multiplication of 2 × 2 matrices, Linear Algebra and its Applications, 4 (1971), 381-388.

[4] Fiduccia, C.M., On obtaining upper bounds on the complexity of matrix multiplication, Complexity of Computer Computations, Plenum Press, New York, 1972, 3–40.

[5] de Groote, H.F., On the complexity of quaternion multiplication, Tägung über algorithmen und komplexitätstheorie, Oberwolfach, (November 1974).

3Editor’s note: This isomorphism between real quaternions and the pair X_{1}, X_{2} of complex numbers in the first row of the matrix also shows that the real quaternion product requires at most 4 complex multiplications. The top row of the result is obtained with 4 complex multiplications: X_{1}Y_{1} −X_{2}Ȳ_{2}, X_{1}Y_{2} +X_{2}Ȳ_{1}. The bottom row of the result matrix requires no additional multiplications, because it can be obtained from the top row by trivial operations.

[6] Gastinel, N., On the simultaneous calculation of a set of bilinear forms, Gatlinburg V Symposium on Numerical Algebra, (June 1972).

[7] Musinski, J., Determining the complexity of matrix multiplication and other bilinear forms, Ph.D. Thesis, Cornell University, (May 1973).

[8] Aho, A.V., J.E. Hopcroft, and J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison Wesley, Reading, Mass., 1974, 446.

[9] Lafon, J.C., Optimum computation of p bilinear forms, (to appear in Journal of Linear Algebra), (1973).

[10] Strassen, V., Vermeidung von divisionen, Crelle Journal für die Reine und Angewante Mathematik, (1973).

[11] Dobkin, D., On the arithmetic complexity of a class of arithmetic computations, Ph.D. Thesis, Harvard University, 1973.

[12] de Groote, H.F., On the computational complexity of quaternion multiplication, preprint, 1975.