BirkhoffDecomposition.jl is a Julia package for decomposing a doubly stochastic matrix as the sum of permutation matrices.

Installation: julia> import Pkg; Pkg.add("BirkhoffDecomposition")

If the above fails, try: julia> import Pkg; Pkg.add("https://github.com/vvalls/BirkhoffDecomposition.jl")

Quick Example

Let us compute a Birkhoff decomposition.

# First load the BirkhoffDecomposition package
using BirkhoffDecomposition

# Generate a random doubly stochastic matrix (n is the dimension)
n  = 3;             
X  = randomDoublyStochasticMatrix(n);

# Find decomposition
P, w = birkdecomp(X);

The output of birkdecomp(X) is an array P of n*n permutation matrices and w a vector of weights. We can now write the doubly stochastic matrix X as sum(P.*w) = P[1]*w[1] + P[2]*w[2] + ... + P[k]*w[k]