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")

Exact Birkhoff decomposition

# Load the package
using BirkhoffDecomposition

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

# Compute exact 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 in vector form as P*w

Approximate Birkhoff decomposition

The command birkdecomp(X,ε) obtains an ε-approximate Birkhoff decomposition of matrix X. In particular, the resulting decomposition Y = reshape(P*w,n,n) ensures that the Frobenious norm of X-Y is smaller than ε.

n  = 16; X = randomDoublyStochasticMatrix(n);
ε = 1e-2;
P, w = birkdecomp(X,ε);

Y = reshape(P*w,n,n);
sqrt(sum((X-Y).^2)) <= ε  # Frobenius norm

Cite

The algorithm implemented in the package is the Birkhoff+ presented in:

Valls, V., Iosifidis, G. and Tassiulas, L., 2021. Birkhoff’s Decomposition Revisited: Sparse Scheduling for High-Speed Circuit Switches. IEEE/ACM Transactions on Networking, 29(6), pp.2399-2412.

Acknowledgements

This work has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 795244.