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.