When is a linear combination of permutation matrices unitary? 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.
 A: I think this can be done(in principle) in general. The $n \times n$ permutation matrices span a $\mathbb{C}$-vector space of dimension $1 + (n-1)^{2}$ since the natural permutation representation of $S_{n}$ is the sum of the trivial representation and an irreducible representation of degree $n-1.$ It is necessary for $\sum_{\pi} c_{\pi} P_{\pi}$ to be unitary that $\sum_{\pi} c_{\pi} \in S^{1}$ (just consider the effect on the vector $v$ with every component $\frac{1}{\sqrt{n}}).$  The non-trivial irreducible character comes from the action of $S_{n}$ on $v^{\perp}$, and for the moment it isn't clear me how to give a concise description to characterize which linear combinations of permutation matrices act as a unitary transformation on $v^{\perp}.$ Note that this is not really an issue when $n =2.$
Later edit: Thanks to Sean Eberhard's comment, it becomes clear that the unitary matrices which are linear combinations of permutation matrices are precisely those unitary matrices which have the vector $v$ above as an eigenvector- any unitary matrix which has $v$ as an eigenvector necessarily leaves $v^{\perp}$ invariant, so any linear combination of permutation matrices both has $v$ has an eigenvector and leaves $v^{\perp}$ invariant.
By a dimension count, the space of matrices which leave both span($v$)and $v^{\perp}$ invariant, which has dimension $1 + (n-1)^{2}$, is precisely the span of the permutation matrices. In conclusion, the unitary matrices which are linear combinations of permutation matrices are precisely the unitary matrices which have $v$ as an eigenvector.
