Product of two complex numbers in less than 3 multiplications

Question

Can someone break this down for me? Why can't it be done in two multiplications?

The Multiplication of Complex Numbers

If the number of multiplications required for a computation is regarded as a measure of its difficulty and these computations are performed using complex numbers, it is natural to ask how many real multiplications are necessary to evaluate the real and imaginary parts of a complex product. The natural way of forming a complex product requires four real multiplications. It may, however, be done in three but not in two multiplications.

(a+bi)(c+di) = (ac-bd) + (ad+bc)i

a(c+d) - d(a+b) = ac - bd
 (1)      (2)

a(c+d) + c(b-a) = ad + bc
          (3)

Theorem - The evaluation of the product of two complex numbers requires three real multiplications, even if multiplication by real constants is not counted.

Sketch of proof Since neither the real nor the complex part of a complex multiplication can be determined in one real multiplication , if this calculation can be done in two multiplications it will be done, for some choice of C_i, W_i, X_i, Y_i and Z_i in the following manner.

ac - bd = C₁(W₁a+X₁b+Y₁c+Z₁d)
            (W₂a+X₂b+Y₂c+Z₂d)
        + C₂(W₃a+X₃b+Y₃c+Z₃d)
            (W₄a+X₄b+Y₄c+Z₄d)
ad + bc = C₃(W₁a+X₁b+Y₁c+Z₁d)
            (W₂a+X₂b+Y₂c+Z₂d)
        + C₄(W₃a+X₃b+Y₃c+Z₃d)
            (W₄a+X₄b+Y₄c+Z₄d)

This leads to 20 non-linear equations in the 20 unknowns, C_i, W_i, X_i, Y_i and Z_i where (i = 1,2,3,4), which have no real solution and hence there is no way to perform a complex multiplication in two real multiplications

Source:

Munro, Ian. "40-44." http://dl.acm.org/. Proc. of Proceedings of the Third Annual ACM Symposium on Theory of Computing, Ohio, Shaker Heights. Ed. Michael A. Harrison, Ranan B. Banerji, and Jeffrey D. Ullman. Acm, 03 May 1971. Web. 26 Nov. 2016. http://dl.acm.org/citation.cfm?doid=800157.805036.

Answer 1

So, the theorem being proved here is basically, "Even if you can do as many additions, subtractions, and multiplications-by-predetermined-constants as you like, you can't compute ac−bd and ad+bc without doing at least three multiplications-of-two-non-predetermined-quantities."

(Note: henceforth, I will abbreviate "multiplication(s) of two non-predetermined quantities" as "MNPQ(s)".)

The proof begins by pointing out that you certainly can't compute either one of { ac−bd, ad+bc } with just a single MNPQ. So the only way you could compute both of them with just two MNPQs would be if you can somehow "share" those MNPQs, using both of their results in both of { ac−bd, ad+bc }.

The proof relies on the unstated premise, by the way, that if all you've got are additions, subtractions, and multiplications-by-predetermined-constants, then ultimately anything you do will just amount to a linear combination of your inputs. (Do you see why?) So the two MNPQs will both be multiplications of linear combinations of { a, b, c, d }, and the way that you "share" their results will be for { ac−bd, ad+bc } to be two different linear combinations of the results of those MNPQs. (A complete proof would require a more thorough argument regarding the possibility that the result of one MNPQ might be an argument to the other, as well as the possibility that the final linear combinations incorporate not just the results of the MNPQs but also { a, b, c, d }; but this is labeled just "sketch of proof", so I guess it doesn't have to worry about such things.)

If you accept that premise, then we can write the two MNPQs as (W₁a+X₁b+Y₁c+Z₁d)·(W₂a+X₂b+Y₂c+Z₂d) and (W₃a+X₃b+Y₃c+Z₃d)·(W₄a+X₄b+Y₄c+Z₄d), and their two linear combinations (ac−bd and ad+bc) as C₁(MNPQ)₁+C₂(MNPQ)₂ and C₃(MNPQ)₃+C₄(MNPQ)₄. If you then multiply everything through, you get a system of equations to solve — the unknowns to solve for being the magical constants W₁, X₂, C₃, etc. — except that, as it turns out, this system of equations actually has no solution. Therefore, no set of magical constants will enable this approach, therefore this approach is impossible, therefore you need to perform at least three MNPQs in order to compute both ac−bd and ad+bc.

Answer 2

The proof is by contradiction.

Assume that we can evaluate the multiplication of two complex number by 2 real multiplications, then you are required to evaluate ac-bd and ad+bc using 2 multiplications.

It should have the manner posted by you where both evaluations consist of the exactly same two multiplications with different real constant coefficients C1, C2, C3, C4 where Xi, Yi, Zi, Wi should be real numbers as well.

Since the coefficients of a^2, b^2, c^2, d^2, ab, ac, ad, bc, bd, cd should match in the two equations, we have 20 non-linear equations with 20 unknowns. For example, C1*W1*W2 + C2*W3*W4 = 0 for a^2 in the first evaluation of ac-bd. This proof further claims that the system does not have real solutions and therefore the assumption does not hold.