In fact, there are infinitely many "primes" in this monoid $M$, i.e. elements $a$ such that any decomposition $a=bc$ has b or c invertible in $M$ (hence a permutation matrix). For example, if $n=3$, 
$\begin{pmatrix} 1 & m & m \\\  m & 1+m^2 & 0 \\\ m & 0 & 1+m^2+m^4 \end{pmatrix}$ with $m\geq1$  is an infinite family of (inequivalent) primes.