**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](http://dx.doi.org/10.1016/0024-3795(75)90040-3).



When is a linear combination of permutation matrices unitary?
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.


