Factorization of banded permutations

Panova, Greta

doi:10.1090/S0002-9939-2012-11411-X

Factorization of banded permutations
HTML articles powered by AMS MathViewer

by Greta Panova PDF

Proc. Amer. Math. Soc. 140 (2012), 3805-3812 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