# Algorithm to decompose a sparse unitary matrix into a Kronecker product of smaller unitary matricies

Given some sparse unitary square matrix $A$ ($dim=2^n$ if it matters), is there an algorithm to decompose $A$ into a Kronecker/tensor product of smaller unitary matrices? In other words: decompose unitary $A$ into $$A=U_1 \otimes U_2 \otimes ... \otimes U_k$$ where each $U_i$ is individually unitary and $\otimes$ denotes the Kronecker product.

I know that in general, the inverse of a Kronecker product is not unique and may not even exist, but if it does, all I would care about is a single tensor decomposition, not an exhaustive list. It wouldn't matter to me what the individual phases are for example.

Edit: I assumed the matrix was a Kronecker product, but in the case that it isn't, is there a way to check?

Edit 2: I found a resource here describing a general outline on how to do the inverse Kronecker product and how to check if it is a Kronecker product in the first place. It looks like the problem can be solved in polynomial time. If however, I demand unitary matrices, is there a similar scheme?

• Not all matrices can be written as Kronecker products at all; it is a very special property similar to being low rank. What do you have in mind? Could you write a formula? Mar 17 '16 at 7:20
• Good point, I was considering general operators on Hilbert tensor product spaces (like in Quantum systems). There the unitary matrices are regularly kronecker products. So the zeroth order step would be to check whether the matrix is a kronecker product. Mar 17 '16 at 22:26
• I found a resource here outline how to check and do the inverse kronecker for a general matrix. In the case of Quantum systems, these matricies need to be unitary, so can is there another scheme that can guarantee that? Mar 17 '16 at 22:38

After some thought, I realized the condition of being unitary is essentially irrelevant to the problem. This is because of the mixed-product and inverse identities of the Kronecker product. So given a unitary $A$, we have: $$A^{-1}=A^{\dagger} \implies U_1^{-1}\otimes...\otimes U_k^{-1}=U_1^{\dagger}\otimes...\otimes U_k^{\dagger}$$

$$AA^{\dagger}=AA^{-1}=I=U_1 U_1^{\dagger} \otimes ... \otimes U_k U_k^{\dagger}$$ Where $I$ is the identity matrix.

This last line implies that each individual $U_j U_j^{\dagger}=aI$ for some complex $a$. To make $U_j$ unitary is then just a matter of scaling by a constant.

This means that the inverse Kronecker product for a unitary matrix is automatically unitary up to a constant scaling factor. So to perform this inverse product, one just needs to follow the solution outlined by karahane in the math stackexchange here. A possible followup question would be whether one can get a piece-by-piece unitary nearest Kronecker product approximation. To be self-contained, the academic references for the solution are given below:

Golub G, Van Loan C. Matrix Computations, The John Hopkins University Pres. 1996

Van Loan C., Pitsianis N., Approximation with Kronecker Products, Cornell University, Ithaca, NY, 1992

Genton MG. Separable approximations of space–time covariance matrices. Environmetrics 2007; 18:681–695.