The Birkhoff theorem for unitary matrices of prime-power dimension (Q2321347)

A well-known theorem of Birkhoff states that every doubly stochastic \(n\times n\) matrix is a convex linear combination of permutation matrices. The authors consider a kind of analogue of this theorem for unitary matrices. Let \(\mathrm{XU}(n)\ \)be the group of \(n\times n\) unitary matrices with all row and column sums equal to \(1\) (equivalently, \(e:=(1,1,\dots,1)\) and \(e^{T}\) are left and right eigenvectors for eigenvalue \(1\)). Let \(G\) be a finite subgroup of \(\mathrm{XU}(n)\). If \(X\in \mathrm{XU}(n)\) and \(X=\sum_{g\in G}c_{g}g\) for some scalar \(c_{g}\) then necessarily \(\sum c_{g}=1\). In [Int. J. Found. Comput. Sci. 14, No. 5, 777--796 (2003; Zbl 1101.68584)], \textit{A. Klappenecker} and \textit{M. Rötteler} use group representations to show that it is also possible to choose the \(c_{g}\) such that \(\sum\left\vert c_{g}\right\vert ^{2}=1\); they are interested in minimising the size of \(G\) and the number of nonzero \(c_{g}\) with this property in order to simplify construction of quantum circuits. The authors of the present paper note that if \(G\) consists of permutation matrices then \(G\) spans all of \(\mathrm{XU}(n)\) if and only if \(G\) is a \(2\)-transitive permutation group of degree \(n\). When \(n=p^{w}\) is a prime power and \(G\) is a group of permutation matrices isomorphic to the affine group \(\mathrm{GA}(w,p)\cong\) \(p^{w}:\mathrm{GL}(w,p)\), they investigate further ways to reduce the number of nonzero coefficients \(c_{g}\) necessary to represent \(X\). In the case where \(n\) is a prime power, this choice of \(G\) gives a more economical representation of the elements of \(\mathrm{XU}(n)\).