Factorization of banded permutations

DOI10.1090/S0002-9939-2012-11411-XMaRDI QIDQ2846735zbMATH OpenFDO

Authors Greta Panova

Publication date 3 September 2013

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1007.1760

zbMATH Keywords

banded permutationsbandwidth 1 permutationsmutually nonadjacent simple transpositions

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Factorization of matrices (15A23) Special matrices (15B99) Permutation groups (20B99) Numerical methods for discrete and fast Fourier transforms (65T50)

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.

Recommendations

• Permutations as Product of Parallel Transpositions
• Three steps on an open road
• Groups of banded matrices with banded inverses
• Banded matrices with banded inverses and A=LPU
• Factorization of banded lower triangular infinite matrices

Cites work

• Combinatorics of Coxeter Groups
• Fast transforms: banded matrices with banded inverses
• Groups of banded matrices with banded inverses
• Permutations as Product of Parallel Transpositions
• Proof of a conjecture of Burr, Grünbaum, and Sloane

Cited in

(5)

• The main diagonal of a permutation matrix
• The algebra of elimination
• Combining hook length formulas and BG-ranks for partitions via the Littlewood decomposition
• Three steps on an open road
• Inequivalent factorizations of permutations

This page was built for publication: Factorization of banded permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2846735)