Factorization of banded permutations
HTML articles powered by AMS MathViewer
- by Greta Panova
- Proc. Amer. Math. Soc. 140 (2012), 3805-3812
- DOI: https://doi.org/10.1090/S0002-9939-2012-11411-X
- Published electronically: March 19, 2012
- PDF | Request permission
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.References
- Chase Albert, Chi-Kwong Li, Gilbert Strang, and Gexin Yu, Permutations as product of parallel transpositions, SIAM J. Discrete Math. 25 (2011), no. 3, 1412–1417. MR 2837606, DOI 10.1137/100807478
- Anders Björner and Francesco Brenti, Combinatorics of Coxeter groups, Graduate Texts in Mathematics, vol. 231, Springer, New York, 2005. MR 2133266
- Martianus Frederic Ezerman and Michael Daniel Samson, Factoring Permutation Matrices into a Product of Tridiagonal Matrices (2010), available at arXiv:1007.3467.
- Jacob E. Goodman, Proof of a conjecture of Burr, Grünbaum, and Sloane, Discrete Math. 32 (1980), no. 1, 27–35. MR 588905, DOI 10.1016/0012-365X(80)90096-5
- Gilbert Strang, Fast transforms: banded matrices with banded inverses, Proc. Natl. Acad. Sci. USA 107 (2010), no. 28, 12413–12416. MR 2670987, DOI 10.1073/pnas.1005493107
- Gilbert Strang, Groups of banded matrices with banded inverses, Proc. Amer. Math. Soc. 139 (2011), no. 12, 4255–4264. MR 2823071, DOI 10.1090/S0002-9939-2011-10959-6
Bibliographic Information
- Greta Panova
- Affiliation: Department of Mathematics, Harvard University, Cambridge, Massachusetts 02138
- Address at time of publication: Department of Mathematics, University of California Los Angeles, Los Angeles, California 90095
- MR Author ID: 964307
- Email: greta.panova@gmail.com
- Received by editor(s): December 24, 2010
- Received by editor(s) in revised form: May 6, 2011
- Published electronically: March 19, 2012
- Communicated by: Jim Haglund
- © Copyright 2012 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 140 (2012), 3805-3812
- MSC (2010): Primary 05A05, 20B99; Secondary 15A23, 15B99, 65T50
- DOI: https://doi.org/10.1090/S0002-9939-2012-11411-X
- MathSciNet review: 2944721