$M$ is a rectangular matrix (which is not square)..
I want to find a rectangular matrix $M$ such that $M^Tv\neq 0$ for every $v$ with $v\neq 0$.
Is there a general way to determine a possible $M$?
Or is there at least a way how to check for a matrix $M$ that $M^Tv\neq 0$ holds for every $v$ with $v\neq 0$?
I was thinking that it would be possible if $M$ is of full rank but it doesn't.
This is not possible if the number of columns $c$ in $M$ is less than the rank $r$ of $p$. For, if $A$ and $p$ are $n\times n$ and $M$ has $c$ columns, the rank of $M^T$ is then at most $c$ and the nullity of $M^T$ is thus at least $n-c$. If $c<r$, then $(n-c)+r>n$. Hence the null space of $M^T$ has a nonzero intersection with the column space of $Ap$, i.e., there exists a nonzero vector $v$ such that $M^TApv=0$.
When $c\ge r$, you may use elementary column operations, Gram-Schmidt orthogonalisation or singular value decomposition to determine a basis $\{x_1,x_2,\ldots,x_r\}$ of the column space of $P$. Put these basis vectors together to form a matrix $X\in\mathbb R^{n\times r}$. Pick any matrix $M\in\mathbb R^{n\times c}$ whose column space contains the column space of $p$, such as $M=\pmatrix{X&0_{n\times(c-r)}}$ or $M=XY$ for any matrix $Y\in\mathbb R^{r\times c}$ with full row rank.
For any vector $v\in\mathbb R^n$, since the column space of $p$ lies inside the column space of $M$, we have $pv=Mw$ for some vector $w\in\mathbb R^c$. If $pv\ne0$, then $w^TM^TApv=(pv)^TA(pv)>0$. Hence $M^TApv\ne0$.