Let $Mat_n(F_q)$ be the semigroup of $n \times n$ matrices over the finite field containing $q$ elements. Is it true that for every $ A \in Mat_n(F_q)$ there is an $X \in Mat_n(F_q)$ such that $AXA=A$?
If I have an arbitrary $ A \in Mat_n(F_q)$ can you construct a specific $X \in Mat_n(F_q)$ that is an inverse of $A$ , i.e., an $X$ such that $AXA=A$?
If $A$ is invertible then there is exactly one such $X$, but otherwise how many inverses does a given singular matrix have?
Yes, this is true in general for matrices over a field $\Bbb F$. Pick a basis $b^1,\cdots, b^{\operatorname{rk}A}$ of $\operatorname{col}A$ and complete it to a basis $b^1,\cdots, b^n$ of $\Bbb F^n$. Then, fix $u^1,\cdots, u^{\operatorname{rk}A}$ such that $Au^j=b^j$ for all $j\le \operatorname{rk}A$. For any choice of $n$ vectors $v^1,\cdots, v^n$ such that $v_j\in\ker A$ for all $i\le \operatorname{rk}A$, the matrix $X$ such that $$Xb^j=\begin{cases}u^j+v^j&\text{if }j\le\operatorname{rk}A\\ v^j&\text{if }j>\operatorname{rk}A\end{cases}$$ satisfies $AXA=A$ (because $AXv=v$ for all $v\in\operatorname{col}A$). This provides an injection of $(\ker A)^{\operatorname{rk}A}\times (\Bbb F^n)^{n-\operatorname{rk}A}$ into the set of solutions to the equation $\{X\in M_n(\Bbb F)\,:\, AXA=A\}$.
The injection above is surjective, because if $AYA=A$, then by using the previous construction on the vectors $$v^j=\begin{cases}Yb^j-u^j&\text{if }j\le \operatorname{rk}A\\ Yb^j&\text{if }j>\operatorname{rk}A\end{cases}$$
we obtain $X=Y$. The only thing to prove is that $Yb^j-u^j\in\ker A$. But that's obvious becasue $b^j=Au^j$, therefore $$A(Yb^j-u^j)=A(YAu^j-u^j)=(AYA-A)u^j=0$$
This proves in particular that, for a finite field, $$\lvert \{X\in M_n(\Bbb F)\,:\, AXA=A\}\rvert=\lvert \Bbb F\rvert^{(\dim\ker A)\operatorname{rk}A+n(n-\operatorname{rk}A)}=\lvert \Bbb F\rvert^{n^2-(\operatorname{rk}A)^2}.$$