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.

  • 4
    $\begingroup$ 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? $\endgroup$ Commented Mar 8, 2015 at 22:06

1 Answer 1


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.

  • 3
    $\begingroup$ This argument also shows that every unitary transformation with $v$ as an eigenvector can be written as a linear combination of permutation matrices. $\endgroup$ Commented Mar 8, 2015 at 22:48
  • $\begingroup$ @SeanEberhard : Yes, thanks, I have incorporated your commment into my answer now. $\endgroup$ Commented Mar 8, 2015 at 23:26
  • 1
    $\begingroup$ 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$. $\endgroup$ Commented Mar 9, 2015 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.