# 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.

• Linear combinations of permutation matrices are the same thing as constant line-sum matrices (that is, matrices where all the row sums and all the column sums are equal), so we can rephrase the question as, which unitary matrices are constant line-sum? – Gerry Myerson Mar 8 '15 at 22:06

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.
• This argument also shows that every unitary transformation with $v$ as an eigenvector can be written as a linear combination of permutation matrices. – Sean Eberhard Mar 8 '15 at 22:48
• More generally, suppose $\rho : G \rightarrow\mathrm{GL}(V)$ is a unitary representation of a finite group $G$, and that $V = V_1\oplus\cdots\oplus V_r$ is a direct sum of non-isomorphic irreducible representations where $\dim V_i = n_i$. Then a block matrix with blocks of sizes $n_1,\ldots,n_r$ is a linear combination of $\rho(g)$ for $g \in G$, so a matrix $U$ is such a linear combination if and only if $U(V_i) \subseteq V_i$ for each $i$. In the special case when $U$ is unitary and $r=2$, it's enough that $U(V_1) \subseteq V_1$, since then $U(V_2)=U(V_1^\perp) = U(V_1)^\perp=V_1^\perp=V_2$. – Mark Wildon Mar 9 '15 at 13:33