  We prove that the permutations of $\{1,\dots, n\}$ having an increasing
(resp., decreasing) subsequence of length $n-r$ index a subset of the set of
all $r$th Kronecker powers of $n \times n$ permutation matrices which is a
basis for the linear span of that set. Thanks to a known Schur--Weyl duality,
this gives a new basis for the centralizer algebra of the partition algebra
acting on the $r$th tensor power of a vector space. We give some related
results on the set of doubly stochastic matrices in that algebra.
