**Question:**
Let $P_\pi$ denote the matrix representation of permutation $\pi$. Consider a linear combination of all $n \times n$ permutation matrices
$$U := \sum_{\pi \in S_n} c_\pi P_\pi$$
where $c_\pi$ are arbitrary complex coefficients. When is the matrix $U$ unitary? It would be great to have a simple parametrization of all tuples of coefficients $(c_\pi : \pi \in S_n)$ for when this happens.

**Example:** In the $n = 2$ case there are only 2 permutations, so the matrix $U$ looks like this:
$$U = \begin{pmatrix} c_0 & c_1 \\ c_1 & c_0\end{pmatrix}$$
where the constants $c_i$ must obey
$$|c_0|^2 + |c_1|^2 = 1 \quad \text{and} \quad c_0 c_1^* + c_1 c_0^* = 0$$
for $U$ to be unitary. We can parametrize the solution of these equations as follows:
$$c_0 = e^{i\varphi} \cos t \quad c_1 = e^{i\varphi} i \sin t$$
for any $\varphi \in [0,2 \pi)$ and $t \in [0,\pi/2]$. It would be nice to have something similar for general $n$. For example, I can write down the equations for $n = 3$ but I don't know any nice way to parametrize the solutions.

**Note:** The only reference on this topic I could find is Orthogonal matrices as linear combinations of permulation matrices.