nLab Birkhoff-von Neumann theorem



The Birkhoff-von Neumann theorem

Given a permutation σS n\sigma \in S_n, the permutation matrix that is associated with σ\sigma is the n×nn \times n matrix P σ(j,k)P_{\sigma}(j,k), where 1j,kn1 \le j,k \le n, whose entries are given by

P σ(j,k)={1 ifσ(j)=k 0 otherwise.P_{\sigma}(j,k)= \left \{ \begin{aligned} 1 & if \sigma (j)=k \\ 0 & otherwise. \end{aligned} \right.

An n×nn \times n doubly stochastic matrix DD is a square matrix whose elements are real and whose rows and columns sum to unity. Given such a matrix, there exist nonnegative weights {w σ:σS n}\{w_{\sigma}:\sigma \in S_n\} such that

σS nw σ=1\sum_{\sigma \in S_n} w_{\sigma}=1 and σS nw σP σ=D\sum_{\sigma \in S_n} w_{\sigma} P_{\sigma}=D.

The set of such matrices of order nn is said to form the convex hull of permutation matrices of the same order where the latter are the vertices (extreme points) of the former.

Quantum extensions

In the quantum context, doubly stochastic matrices become doubly stochastic channels, i.e. completely positive maps preserving both the trace and the identity. Quantum mechanically we understand the permutations to be the unitarily implemented channels. That is, we expect doubly stochastic quantum channels to be convex combinations of unitary channels (that is channels that can be represented by some combination of unitary transformations). Unfortunately it is well-known that some quantum channels cannotcannot be written that way.

However, large tensor powers of a channel may be easier to represent in this way, because one need not use only product unitaries in the decomposition. Thus one proposed solution to the problem is to denote, for any doubly stochastic channel TT, by d B(T)d_{B}(T) the Birkhoff defect, defined as the cb-norm distance from TT to the convex hull of the unitarily implemented channels. Then the key is to determine whether d B(T n)d_{B}(T^{\otimes n}) goes to zero as nn\to\infty.


  • Liviu Paunescu, Florin Radulescu, A generalisation to Birkhoff - von Neumann theorem (arXiv:1506.01685)

Last revised on September 13, 2018 at 08:23:06. See the history of this page for a list of all contributions to it.