The Birkhoff theorem for unitary matrices of prime-power dimension

DOI10.1016/J.LAA.2019.05.007MaRDI QIDQ2321347zbMATH OpenOpenAlexFDO

Authors Alexis De Vos, Stijn De Baerdemacker

Publication date 29 August 2019

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/1812.08833

zbMATH Keywords

Birkhoff theorempermutation matrixunitary matrix

Mathematics Subject Classification ID

Canonical forms, reductions, classification (15A21) Hermitian, skew-Hermitian, and related matrices (15B57)

Abstract: The unitary Birkhoff theorem states that any unitary matrix with all row sums and all column sums equal unity can be decomposed as a weighted sum of permutation matrices, such that both the sum of the weights and the sum of the squared moduli of the weights are equal to unity. If the dimension~$n$ of the unitary matrix equals a power of a prime $p$, i.e. if $n=p^w$, then the Birkhoff decomposition does not need all $n!$ possible permutation matrices, as the epicirculant permutation matrices suffice. This group of permutation matrices is isomorphic to the general affine group GA($w,p$) of order only $p^w(p^w-1)(p^w-p)\mathrm{...}(p^w-p^{w-1})llleft(p^{w}ight)!$.

Review text

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)\).

Recommendations

• The Birkhoff theorem for unitary matrices of prime dimension
• The Birkhoff theorem for unitary matrices of arbitrary dimensions
• The decomposition of an arbitrary \(2^w \times 2^w\) unitary matrix into signed permutation matrices
• Algebraic and geometric structures inside the Birkhoff polytope
• Sinkhorn normal form for unitary matrices

Cites work

• A classification of the maximal subgroups of the finite alternating and symmetric groups
• A Concise Guide to Complex Hadamard Matrices
• Birkhoff's polytope and unistochastic matrices, N=3 and N=4
• DIAGONALS OF DOUBLY STOCHASTIC MATRICES
• scientific article; zbMATH DE number 3305202 (Why is no real title available?)
• scientific article; zbMATH DE number 3095897 (Why is no real title available?)
• Notes on Birkhoff-von Neumann decomposition of doubly stochastic matrices
• Notes on the Birkhoff Algorithm for Doubly Stochastic Matrices
• Optimal synthesis of linear reversible circuits
• Quantum information. An introduction to basic theoretical concepts and experiments
• QUANTUM SOFTWARE REUSABILITY
• Reversible Computing
• Sets of Linearly Independent Permutation Matrices
• The Birkhoff theorem for unitary matrices of arbitrary dimensions
• The Birkhoff theorem for unitary matrices of prime dimension
• The NEGATOR as a basic building block for quantum circuits

Cited in

(5)

• The decomposition of an arbitrary \(2^w \times 2^w\) unitary matrix into signed permutation matrices
• The group of dyadic unitary matrices.
• The Birkhoff theorem for unitary matrices of arbitrary dimensions
• A Birkhoff Connection Between Quantum Circuits and Linear Classical Reversible Circuits
• The Birkhoff theorem for unitary matrices of prime dimension

This page was built for publication: The Birkhoff theorem for unitary matrices of prime-power dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2321347)