Characterizing families of $p^2$ orthogonal $p \times p$ unitaries?

Suppose I walk up with $2$-by-$2$ unitary matrices $U_1,U_2,U_3,U_4 \in \mathbb{C}^{2 \times 2}$ with the property that $\mathrm{Tr}(U_i U_j^\dagger) = 0$ for all $i \neq j$. One can show that there exists unitaries $V,W$ and constants $\alpha_1,\alpha_2,\alpha_3,\alpha_4 \in \mathbb{C}$ such that $$\alpha_1 VU_1W^\dagger = I \qquad \alpha_2 VU_2W^\dagger = \sigma_Z \qquad \alpha_3 VU_3 W^\dagger = \sigma_X \qquad \alpha_4 VU_4 W^\dagger = \sigma_Y$$ where $I$ is the identity matrix, and $\sigma_X,\sigma_Y,\sigma_Z$ are the Pauli matrices. (Proof sketch: first, one can assume without loss of generality that $U_1 = I$, by first premultiplying all $U_i$'s by $U_1^\dagger$. Then, $\mathrm{Tr}(U_2) = 0$ implies that its eigenvalues are of the form $\{ e^{i \theta}, -e^{i \theta} \}$. We can set $\alpha_2 = e^{-i\theta}$. The $V$ matrix transforms between the standard basis and the eigenbasis of $U_2 U_1^\dagger$, and thus we get $\alpha_2 V U_2 U_1^\dagger V^\dagger = \sigma_Z$. Set $W = V U_1$. We can continue in this manner for $U_3$ and $U_4$ to obtain the desired statement.)

I'm wondering about the generalization of this. Let $p$ be prime, and suppose there are $p^2$ unitary matrices $\{ U_i \}$ acting on $\mathbb{C}^{p}$ that satisfying $\mathrm{Tr}(U_iU_j^\dagger) = 0$ for all $i \neq j$. Is it true that there exist $V,W$ and constants $\alpha_i$ such that $\{ \alpha_i V U_i W^\dagger\}$ is equal to the so-called generalized Pauli matrices over $\mathbb{F}_p$?

What you wrote in your first paragraph is not true, at least not as written. Since unitary conjugation preserves algebraic properties, if you have $U_1,U_2,U_3,U_4$ as stated, you need to have $U_1=I$, $U_2^2=U_3^2=U_4^2=I$, and $-iU_2U_3U_4=I$. But here are four unitaries that are orthonormal as requested, but satisfy none of the aforementioned properties: $$U_1=\frac1{\sqrt2}\,\begin{bmatrix} -1&1\\1&1\end{bmatrix} ,\ \ \ U_2=\frac1{\sqrt2}\,\begin{bmatrix} 1&-1\\1&1\end{bmatrix} ,\ \ \ U_3=\frac1{\sqrt2}\,\begin{bmatrix} 1&1\\-1&1\end{bmatrix} ,\ \ \ U_4=\frac1{\sqrt2}\,\begin{bmatrix} 1&1\\1&-1\end{bmatrix} ,\ \ \$$
• Ah, good point! One should allow to multiplication times constants. For the ensemble you presented, one can first premultiply everyone by $U_1^\dagger$ so that the first matrix is identity. The rest then become: $U_2 U_1^\dagger = -\sigma_Z$, $U_3 U_1^\dagger = \sigma_X$, and $U_4 U_1^\dagger = i \sigma_Y$. Thus the solution would be $W = U_1$, $V = I$, $\alpha_2 = -1$, $\alpha_3 = 1$, and $\alpha_4 = i$. – Henry Yuen Feb 7 '18 at 19:00