The best known algorithm(s) for matrix multiplication of $n$-dimensional matrices take $O(n^{2.37})$ time. However, that's for matrices with totally independent contents. When the two matrices are related to each other in some known way, it's sometimes possible to get a speedup. For example, computing $U \cdot V$ is quite easy if you're promised that $V = U^{-1}$.

I was wondering if knowing $V = U^\dagger$, i.e. that $V$ is the conjugate transpose of $U$, allowed for asymptotically faster matrix multiplication.

Can the special case $U \cdot U^\dagger$ be computed asymptotically more quickly than the general case $U \cdot V$?


1 Answer 1


It's not faster (asymptotically). You can reduce general matrix multiplication down to three "adjoint-squarings".

Suppose we're given an adjoint-squaring function $\mathfrak{F}$ where $\mathfrak{F}(M) = M \cdot M^\dagger$. Consider that:

$\mathfrak{F}(A + B) = (A+B) \cdot (A+B)^\dagger = AA^\dagger + BB^\dagger + A B^\dagger + B A^\dagger$

$\mathfrak{F}(A - B) = AA^\dagger + BB^\dagger - A B^\dagger - B A^\dagger$

$\mathfrak{F}(A + i B) = AA^\dagger + BB^\dagger - i A B^\dagger + i B A^\dagger$

Thinking in terms of the basis $[x, y, z, t] \rightarrow x AA^\dagger + y BB^\dagger + z A B^\dagger + t B A^\dagger$, those three adjoint-squarings give us $p=[1, 1, 1, 1]$ and $q=[1,1,-1,-1]$ and $r=[1,1,-i,i]$ respectively. From that we want to recover the product $[0,0,1,0] \rightarrow AB^\dagger$. A bit of work will show that the linear combination $\frac{1-i}{4}p - \frac{1+i}{4}q + \frac{i}{2} r$ is exactly what we need.

Therefore we can compute the product $U \cdot V$ via $\mathfrak{F}$ by evaluating:

$$U \cdot V = \frac{1-i}{4} \mathfrak{F}(U + V^\dagger) - \frac{1+i}{4} \mathfrak{F}(U - V^\dagger) + \frac{i}{2} \mathfrak{F}(U + i V^\dagger)$$

Since the most expensive step of this reduction is the adjoint-squaring (it's certainly not the adding, conjugating, transposing, subtracting, or scaling), and the adjoint-squaring function $\mathfrak{F}$ is only used a constant number of times (3 times), general multiplication is no more asymptotically expensive than adjoint-squaring.

(Related: Is matrix squaring asymptotically faster? Nope. With a much simpler proof.)

  • $\begingroup$ Is this an answer you post claiming it is correct, or do you want feedback as to whether it is correct? (Just checking your intentions, I have not read the answer.) $\endgroup$
    – Raphael
    Commented Jan 19, 2016 at 15:13
  • 1
    $\begingroup$ @Raphael It should be correct. I figured it out as part self-answering another question, realized it should be separate, and split it off. $\endgroup$ Commented Jan 19, 2016 at 16:04

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.