Journal Article

Algorithms for symmetric Birkhoff-von Neumann decomposition of symmetric doubly stochastic matrices

Cohen, Jérémy E., Uçar, Bora, Lesens, Damien

2025

Overview

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 [Padberg and Wolsey, Math. Program., 29 (1984); Vazirani, 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, andreport 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. La décomposition de Birkhoff–von Neumann (BvN) écrit une matrice bistochastique comme une combinaison convexe de matrices de permutation. Nous étudions la décomposition BvN pour des matrices symétriques bistochastiques, en imposant que les matrices de permutation de la décomposition soient aussi symétriques. Cette décomposition est appelée et n'est pas toujours possible. Deux travaux théoriques précurseurs ont établis les conditions sous lesquelles la décomposition est possible pour les matrices d'adjacence d'une classe spéciale de graphes pondérés non-orientés. En s'appuyant sur ces deux travaux, nous proposons un algorithme pratique pour la même classe de matrices.Nous présentons aussi une transformation qui convertit une matrice symétrique bistochastique donnée, ayant possiblement des entrées diagonales non nulles, en la matrice d'adjacence d'un graphe non-orienté. Cette matrice d'adjacence du graphe obtenu admet une décomposition si et seulement si la matrice originale en admet une aussi. Cette transformation et l'aspect pratique de notre algorithme nous permet de proposer la première implémentation d'un algorithme pour la décomposition BvN symétrique de matrices bistochastiques.Munis de cette implémentation, nous expérimentons la décomposition de matrices symétriques bistochastiques en combinaison convexe de matrices de permutation symétriques.Nos expériences indiquent que l'algorithme proposé est aussi efficace que les meilleurs algorithmes connus pour la décomposition BvN classique.

• Publisher: Society for Industrial and Applied Mathematics
• Subject: Combinatorics / Computer Science / Data Structures and Algorithms / Mathematics