Factoring Permutation Matrices Into a Product of Tridiagonal Matrices

Michael Daniel Samson, Martianus Frederic Ezerman

Gilbert Strang posited that a permutation matrix of bandwidth $w$ can be written as a product of $N<2w$ permutation matrices of bandwidth 1. A proof employing a greedy ``parallel…