I have an arbitrary product of 4-dimensional Pauli Matrices X and Z
$U_1=X^{n_1} Z^{n_2} X^{n_3} ... Z^{n_k}$
where $n_i \in \mathbb{N}$, and
$X = \begin{bmatrix} 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 0 \end{bmatrix}, Z = \begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & i & 0 & 0\\ 0 & 0 & -1 & 0\\ 0 & 0 & 0 & -i \end{bmatrix}$ with the property, $X^4=1$ and $Z^4=1$.
Can $U_1$ be written in the form:
$U_2=\sum_{l=0}^{3} \sum_{m=0}^{3} c_{l,m} X^l Z^m$
with $c_j\in\mathbb{C}$. That means, can an arbitrary product of X and Z matrices written as a sum with maximally 16 terms, where first all X matrices are written, and then all Z matrices?
For the two-dimensional case, i found that this can be done. In the 4-dimensional case, the commutation relations lead to much more nasty terms. Thank you!
I don't know if you need a constructive proof or an existence proof. The latter is easiest and since you didn't specify which I will go with that one. I will also do you one better and show that every $4\times4$ matrix has such representation.
First off note that $U_1$ is a $4\times4$ matrix since the product of two $4\times4$ matrices is itself a $4\times4$ matrix.
Next note that $\sum_{j=1} ^n e^{\frac{2\pi i}{n}j}=0$.
This leads us to the conclusion that each diagonal term can be set by: \begin{equation} \frac{1}{n} \sum_{k=0} ^n \sum_{j=0} ^n e^{-\frac{2 \pi i }{n}j k} d_{kk}Z^j \end{equation} where $d_{kk}$ are the $k$th diagonal term.
One can then start going through off diagonal terms by adding factors of $X$ and isolating the individual diagonal components using the method above. Since each power of $X$ goes through a different diagonal of the $n$ diagonals. It's pretty easy to see how this construction will take place.
If you need further breaking down of the problem I'll get back to it after work.
You'll also notice that this easily generalized to the $n\times n$ case.
It might be helpful to mention that $Z X = i X Z$. This generalizes to the $n\times n$ case $Z X=e^{\frac{2 \pi i}{n}}X Z$. This actually carries the implication that your required representation is likely too loose. It looks like it should be able to be represented as $c X^{\sum_l n_{2l+1}} Z^{\sum_l n_{2l}}$ for some complex $c$.