Permutations as Product of Parallel Transpositions
It was conjectured that a permutation matrix with bandwidth b can be written as a product of no more than 2b−1 permutation matrices of bandwidth 1. In this note, two proofs are given to affirm the conjecture.
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics
2012
|
| Online Access: | http://hdl.handle.net/1721.1/68631 https://orcid.org/0000-0001-7473-9287 |
| _version_ | 1811094576520232960 |
|---|---|
| author | Albert, Chase Li, Chi-Kwong Strang, Gilbert Yu, Gexin |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Albert, Chase Li, Chi-Kwong Strang, Gilbert Yu, Gexin |
| author_sort | Albert, Chase |
| collection | MIT |
| description | It was conjectured that a permutation matrix with bandwidth b can be written as a product of no more than 2b−1 permutation matrices of bandwidth 1. In this note, two proofs are given to affirm the conjecture. |
| first_indexed | 2024-09-23T16:02:16Z |
| format | Article |
| id | mit-1721.1/68631 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:02:16Z |
| publishDate | 2012 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | mit-1721.1/686312022-10-02T05:51:43Z Permutations as Product of Parallel Transpositions Albert, Chase Li, Chi-Kwong Strang, Gilbert Yu, Gexin Massachusetts Institute of Technology. Department of Mathematics Strang, Gilbert Strang, Gilbert It was conjectured that a permutation matrix with bandwidth b can be written as a product of no more than 2b−1 permutation matrices of bandwidth 1. In this note, two proofs are given to affirm the conjecture. National Science Foundation (U.S.) (NSF grant DMS-0914670) National Science Foundation (U.S.) (NSF grant DMS-0852452) 2012-01-23T16:54:12Z 2012-01-23T16:54:12Z 2011-09 2011-07 Article http://purl.org/eprint/type/JournalArticle 0895-4801 1095-7146 http://hdl.handle.net/1721.1/68631 Albert, Chase et al. “Permutations as Product of Parallel Transpositions.” SIAM Journal on Discrete Mathematics 25.3 (2011): 1412.© 2011 Society for Industrial and Applied Mathematics. https://orcid.org/0000-0001-7473-9287 en_US http://dx.doi.org/10.1137/100807478 SIAM Journal on Discrete Mathematics Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial and Applied Mathematics SIAM |
| spellingShingle | Albert, Chase Li, Chi-Kwong Strang, Gilbert Yu, Gexin Permutations as Product of Parallel Transpositions |
| title | Permutations as Product of Parallel Transpositions |
| title_full | Permutations as Product of Parallel Transpositions |
| title_fullStr | Permutations as Product of Parallel Transpositions |
| title_full_unstemmed | Permutations as Product of Parallel Transpositions |
| title_short | Permutations as Product of Parallel Transpositions |
| title_sort | permutations as product of parallel transpositions |
| url | http://hdl.handle.net/1721.1/68631 https://orcid.org/0000-0001-7473-9287 |
| work_keys_str_mv | AT albertchase permutationsasproductofparalleltranspositions AT lichikwong permutationsasproductofparalleltranspositions AT stranggilbert permutationsasproductofparalleltranspositions AT yugexin permutationsasproductofparalleltranspositions |