Is matrix "adjoint-squaring" faster than general matrix multiplication?

Question

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$?

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.)