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.