Matrix right multiplication orbit invariant

One construction of such a $P$ is as follows:

Note that $N^T$ and $M^T$ (where $T$ denotes the transpose) have the same row-space. Thus, $N^T$ and $M^T$ can be row-reduced to the same form. In other words, there exist invertible matrices $R_1,R_2$ such that $$ R_1N^T = R_2M^T \implies\\ (R_1N^T)^T = (R_2M^T)^T \implies\\ NR_1^T = MR_2^T \implies\\ N = MR_2^T R_1^{-T}. $$ That is, it suffices to take $P = R_2^T R_1^{-T} = (R_1^{-1}R_2)^T$.

---

A more direct construction: let $v_1,\dots,v_k$ be a basis for the kernel of $N$, and extend this basis to $v_1,\dots,v_n$, a basis of $\Bbb R^n$. The vectors $Nv_{k+1},\dots,Nv_{n}$ form a basis for the image of $N$.

Let $w_1,\dots,w_k$ be a basis for the kernel of $M$. There exist vectors $w_{k+1},\dots,w_{n}$ such that $Mw_j = Nv_j$ for $j = k+1,\dots,n$, and the resulting set $w_1,\dots,w_n$ is a basis.

Select a matrix $P$ that satisfies $Pv_j = w_j$ for all $j$. Note that $P$ is invertible, and $MP v_j = Nv_j$ for all $j$, which means that $N = MP$.