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.

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). Any such prime is necessarily in any generating set (up to permuting lines and columns).

Exercise : 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.