Factorization of banded permutations

2010/07/11 by Panova, Greta
#05A05 #15B99 #20B99 (Primary) 15A23 #65T50 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics #Group Theory (math.GR) #Numerical Analysis (math.NA)

paper · doi:10.48550/arxiv.1007.1760

Abstract

We consider the factorization of permutations into bandwidth 1 permutations, which are products of mutually nonadjacent simple transpositions. We exhibit an upper bound on the minimal number of such factors and thus prove a conjecture of Gilbert Strang: a banded permutation of bandwidth w can be represented as the product of at most 2w-1 permutations of bandwidth 1. An analogous result holds also for infinite and cyclically banded permutations.

Related

• Factoring Permutation Matrices Into a Product of Tridiagonal Matrices
• Factorization of permutations
• Factoring Pattern-Free Permutations into Separable ones
• The minimal degree of permutation representations of finite groups
• Bijections and symmetries for the factorizations of the long cycle