How do I know if a 4x4 unitary matrix is a tensor product of two 2x2 unitary matrices? Let's say I have a unitary matrix $U$, how do I know if $U$ is the resultant of a tensor product of two other unitary matrices $U_1$ and $U_2$ (dim$\geq$2), such that $U_1\otimes U_2=U$?
More specifically I am concerned with the almost trivial case of where the dimensions of $U_1$ and $U_2$ are 2x2 ($U$ is 4x4).
Do I necessarily need to find the basis where $U$ is block diagonal? Or do I need to fully diagonalize $U$ and find common factors? Are there any other strategies to verify without doing these?
I tried to find some direction, but I do not know what is the right term here, is it reducibility? separability?
 A: In the smallest interesting dimension you can use the exceptional morphism $\mathrm{SL}_2(\mathbb{C}) \times \mathrm{SL}_2(\mathbb{C}) \to \mathrm{SO}_4(\mathbb{C})$ obtained by viewing $\mathrm{SL}_2$ as a symplectic group, and using the fact that the tensor product of two vector spaces endowed with alternate forms is naturally endowed with a symmetric form. This morphism is onto and has kernel $\{(1,1),(-1,-1)\}$. I believe that the image of $\mathrm{SU}(2) \times \mathrm{SU}(2)$ is isomorphic to $\mathrm{SO}(4)$ (the compact Lie group). This may be deduced from $\mathrm{SU}(2) = \mathrm{SL}_2(\mathbb{C})^\sigma$ where $\sigma(g) = A \overline{g} A^{-1}$ and $A = \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix}$. Working out a basis of $\mathbb{C}^2 \otimes \mathbb{C}^2$ in which the image is the usual $\mathrm{SO}(4)$ is an exercise in Galois cohomology (for $\mathbb{C}/\mathbb{R}$). Choosing as basis of $\mathbb{C}^2 \otimes \mathbb{C}^2$ the family $(e_1 \otimes e_1, e_1 \otimes e_2, e_2 \otimes e_1, e_2 \otimes e_2)$ where $(e_1, e_2)$ is the standard basis of $\mathbb{C}^2$, I find that the image of the tensor product map $\mathrm{SU}(2) \times \mathrm{SU}(2) \to \mathrm{GL}_4(\mathbb{C})$ is $h \mathrm{SO}(4) h^{-1}$ where
$$ \mathrm{SO}(4) = \{ g \in \mathrm{SL}_4(\mathbb{R}) \,|\, g^T = g^{-1} \}$$
and
$$h = \begin{pmatrix} 1 & 0 & 0 & -i \\ 0 & i & 1 & 0 \\ 0 & i & -1 & 0 \\ 1 & 0 & 0 & i \end{pmatrix}.$$
So the image of $\mathrm{U}(2) \times \mathrm{U}(2)$ in $\mathrm{U}(4)$ is $\mathrm{U}(1) \cdot h \mathrm{SO}(4) h^{-1}$. To check if $g \in \mathrm{U}(4)$ is in the image, first find out if there exists $z \in \mathrm{U}(1)$ such that $z^{-1} h^{-1} g h$ has real entries (since $g \neq 0$ there is at most one such $z$ up to multiplication by $-1$), and if so check if $z^{-1} h^{-1} g h$ belongs to $\mathrm{SO}(4)$.
Edit: a few indications on how $h$ is found: $A \in \mathrm{SL}_2(\mathbb{C})$ corresponds to a $1$-cocycle $c: \mathrm{Gal}(\mathbb{C}/\mathbb{R}) \to \mathrm{PGL}_2(\mathbb{C})$ defined by $c(1) = 1$ and $c(\overline{\cdot}) = A$ (well, its image in $\mathrm{PGL}_2(\mathbb{C})$) because we have $A \overline{A} = A^2 = -1 \in \ker(\mathrm{SL}_2(\mathbb{C}) \to \mathrm{PGL}_2(\mathbb{C}))$. Similarly $A \otimes A \in \mathrm{SO}_4(\mathbb{C})$ (with the choice of basis above, this $\mathrm{SO}_4$ is the one for the symmetric matrix $S = \begin{pmatrix} & & & 1 \\ & & -1 & \\ & -1 & & \\ 1 & & & \end{pmatrix}$, which also happens to be $A \otimes A$) defines a $1$-cocycle $c': \mathrm{Gal}(\mathbb{C}/\mathbb{R}) \to \mathrm{SO}_4(\mathbb{C})$. Now by Hilbert 90 we know that any $1$-cocycle $\mathrm{Gal}(\mathbb{C}/\mathbb{R}) \to \mathrm{GL}_4(\mathbb{C})$ is a coboundary, in other words $A \otimes A$ may be written as $h \overline{h}^{-1}$ for some $h \in \mathrm{GL}_4(\mathbb{C})$. For the explicit computation we can use the standard proof of Hilbert 90: $x$ may be chosen of the form $\sum_{\tau \in \mathrm{Gal}(\mathbb{C}/\mathbb{R})} c'(\tau) \tau(a)$ for "generic" $a \in \mathrm{GL}_4(\mathbb{C})$. In fact we can make the computation slightly simpler by replacing $A \otimes A$ by $\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ because $A$ is made up of this $2 \times 2$ matrix and its opposite. Finally, translating the above (split) $\mathrm{SO}_4$ for $S$ via the change of basis corresponding to $h$, we find the "usual" special orthogonal group for the symmetric matrix $I_4$.
A: Here's how you do it while dropping "unitary." You can actually vectorize all the matrices and treat this as a question about vectors: given a vector in $\mathbb{C}^{16}$, how do you know if it's the tensor product of two vectors in $\mathbb{C}^4$?
More abstractly, let's consider two vector spaces $V, W$ and ask when an element of the tensor product $V \otimes W$ is a tensor product $v \otimes w$. These are known as pure tensors. The answer turns out to be quite nice and can be written in coordinates as follows: if $\{ v_i \}$ is a basis of $V$ and $\{ w_j \}$ is a basis of $W$, and we write an element of $V \otimes W$ as $\sum a_{ij} v_i \otimes w_j$, then this element is a pure tensor iff all $2 \times 2$ minors of the matrix $a_{ij}$ vanish, so
$$a_{ij} a_{k \ell} - a_{i \ell} a_{kj} = 0$$
for all $i, j, k, \ell$. These are the homogeneous equations cutting out the Segre embedding of $\mathbb{P}(V) \times \mathbb{P}(W)$ into $\mathbb{P}(V \otimes W)$.
To see this abstractly, we can assume WLOG that $V$ and $W$ are finite-dimensional. Then an element of $V \otimes W$ is the same thing as a linear map $V^{\ast} \to W$, and the condition that it's a pure tensor is the same as the condition that this linear map has rank at most $1$. And it's a general fact that a matrix has rank less than $k$ iff its $k \times k$ minors vanish; see, for example, this answer.
So this condition can be used to determine whether $U$ is a tensor product of two matrices. These matrices may not be unitary, but I think you should be able to check whether they are by taking partial traces as Kenneth says in the comments (unless by bad luck one of the traces happens to be zero).
