Algorithms for Symmetric Birkhoff–von Neumann Decomposition of Symmetric Doubly Stochastic Matrices

Abstract. The classical Birkhoff–von Neumann (BvN) decomposition expresses a given doubly stochastic matrix as a convex combination of permutation matrices. We investigate the BvN decomposition of symmetric doubly stochastic matrices where the permutation matrices in the decomposition are also symmetric, called symBvN decomposition. This decomposition is not always possible. Two pioneering theoretical works [M. W. Padberg and L. A. Wolsey, Math. Programming, 29 (1984), pp. 1–14; V. V. Vazirani, An Extension of the Birkhoff–von Neumann Theorem to Non-Bipartite Graphs, preprint, arXiv:2010.05984, 2020] establish the conditions under which such a decomposition is possible using graph terminology. We propose a practical algorithm by combining these two works. A simple transformation converts any given symmetric doubly stochastic matrix, with possibly nonzero diagonal elements, to be the adjacency matrix of an edge-weighted undirected graph. The adjacency matrix of the resulting graph admits a symBvN decomposition if and only if the given matrix does so. The practicality of the proposed algorithm allows us to implement it, release its source code, and report the first set of experiments ever performed for the symBvN decomposition. Our experiments suggest that the proposed algorithm is as effective as the state-of-the-art algorithms for the classical BvN decomposition. Reproducibility of computational results. This paper has been awarded the “SIAM Reproducibility Badge: Code and data available” as a recognition that the authors have followed reproducibility principles valued by SIMAX and the scientific computing community. Code and data that allow readers to reproduce the results in this paper are available at https://gitlab.inria.fr/bora-ucar/symBvN . [Formula: see text]