Proving matrices equation when all the matrices in it may not be invertible I'm reviewing linear algebra for my exams this year, and I just encountered this problem.
For an arbitrary matrix, $\boldsymbol{A} \in \mathcal{R}^{m \times n}$, prove there must be a unique matrix $\boldsymbol{P} \in \mathcal{R}^{n \times m}$ matching the following 4 equations.
$$
APA = A \\
PAP = P \\
(AP)^T = AP \\
(PA)^T = PA
$$
Things will be easy if $A$ is invertible, but when $A$ is not invertible I have no ideas how to do it.

The matrix $A$ induces a decomposition $\ker A\oplus(\ker A)^\perp$ in the domain and $\mathrm{im}A\oplus(\mathrm{im}A)^\perp$ in the codomain. The core of the matrix is the square matrix $U:(\ker A)^\perp\to\mathrm{im}A, x\mapsto Ax$.
Since $AP$ is to act as an 'left-identity' on $A$ we have to define $Px=U^{-1}x$ for $x\in \mathrm{im}A$. Similarly $PA$ acts as right-identity for $A$, so $Px=0$ for $x\in(\mathrm{im}A)^\perp$.
Thus $P=\begin{pmatrix}U^{-1}&0\\0&0\end{pmatrix}$ with respect to bases for the above spaces. Then $AP$ and $PA$ are idempotent symmetric matrices. The definitions for $Px$ are forced, so this makes $P$ unique.
Edit: If you prefer using algebra only: Every matrix can be written as $Q^*UR$ where $Q,R$ are projection matrices of the type $[I,O]$. Note that $QQ^*=I$, $RR^*=I$. The equation $APA=A$ implies $Q^*URPQ^*UR=Q^*UR$; so multiplying by $Q$ and $R^*$ gives $RPQ^*=U^{-1}$.
Edit: Example to illustrate the above. Take $$A=\begin{pmatrix}-1&-1&2&3\\0&0&1&1\\2&2&1&-1\end{pmatrix}.$$ Its nullspace or kernel consists of the plane spanned by the vectors $u_3=(1,-1,0,0)$, $u_4(0,1,-1,1)$. Take the perpendicular space $(\ker A)^\perp$ spanned by, say, $u_1=(1,1,1,0)$, $u_2=(0,0,1,1)$. The image space $\mathrm{im}A$ is the plane spanned by $v_1=Au_3=(0,1,5)$ and $v_2=Au_4=(5,2,0)$. Its perpendicular space is spanned by $v_3=(2,-5,1)$ (using cross product). So the matrix of $A$ using the basis $u_i$ for the domain and $v_j$ for the codomain looks like $$\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&0&0\end{pmatrix}$$ So the required matrix $P=\begin{pmatrix}1&0&0\\0&1&0\\0&0&0\\0&0&0\end{pmatrix}$ with respect to the same bases in reverse. Hence $P=\frac{1}{150}\begin{pmatrix}-2 & 5 & 29 \\
 -2 & 5 & 29 \\
 24 & 15 & 27 \\
 26 & 10 & -2 \\\end{pmatrix}$ with respect to the standard bases. You can check that this matrix has the desired properties.
The proof is based on the rank-nullity formula, in essence. The dimension of $(\ker A)^\perp=\dim V_1-\mathrm{nullity}(A)=\mathrm{rank}(A)=\dim(\mathrm{im}A)$. Hence every matrix $A:V_1\to V_2$ can be decomposed into three parts, where the first part $R:V_1\to(\ker A)^\perp$ is a projection, the second $U:(\ker A)^\perp\to\mathrm{im}(A)$ is invertible (I called this the core but it is not a standard name), and the third $Q^*:\mathrm{im}(A)\to V_2$ is the embedding of the image subspace into the codomain.
