Factorization of banded permutations
Solves a combinatorial conjecture about permutation factorization, relevant to matrix theory and linear algebra.
The paper proves that any banded permutation of bandwidth w can be factored into at most 2w-1 permutations of bandwidth 1, confirming a conjecture by Gilbert Strang. The result extends to infinite and cyclically banded permutations.
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.