Solutions to $\mathbf{AX}=\mathbf{B}$ Let $\mathbf{A},\mathbf{B}$ be $n\times n$ matrices over a field $\mathbb{F}$.
How can we find if there exist a $n\times n$ matrix $\mathbf X$ s.t. $\mathbf{AX}=\mathbf{B}$? (and how can we find $\mathbf X$ if it exists?)
Note: if $|\mathbf A|\neq 0$ then it's easy since $\mathbf{X}=\mathbf{A}^{-1}\mathbf{B}$, but I stumbled on a problem where my $\mathbf A$ is not invertible.
 A: In principle you can (try to) solve it for one column of $B$ (and $X$) at a time.
In practice you can save time by doing Gauss-Jordan elimination on $[\,A\,|\,B\,]$ once and for all. If the leading $1$ coefficients of every nonzero row in the row echelon form are all in the $A$ part, you can read possible rows for $X$ off the $B$ side of the reduced row echelon form. Otherwise there is no solution.
If $A$ is not invertible, there will be either no solution for $X$ or infinitely many, since you can add an arbitrary vector from the kernel of $A$ to every column of $X$ without changing the value of $AX$.
A: In general I think this problem will be as difficult as solving the system of linear equations, but there are a few observations you can make.
The statement that $AX=B$ is just saying that $B$ is in the cyclic right ideal of $M_n(\mathbb{F})$ generated by $A$.
Secondly, if $\mathrm{rank}(A)<\mathrm{rank}(B)$, then you have no hope of finding a solution, since the rank of $AX$ is no greater than that of $A$.
If you have additional requirements on $A$ and $B$ that might make this easier, you might write them up in another question. Using $A$ and $B$ in general is a pretty vague (although I admit natural) question.
A: existence of $X$ is equivalent to: for every (row) vector $u$, $uA=0$ implies $uB=0$. You can therefore find a basis of the space of solutions of $uA=0$ and verify whether every element of the basis satisfies $uB=0$.
A: Here is a simple characterization, but you cannot probably get away from row reducing.
The equation is consistent if and only if $Ax=c_i$ has solution for each column $c_i$ of $B$.
This is equivalent to $c_i \in Col(A)$, which leads to the following:
$$AX=B \, \mbox{ has solution} \, \Leftrightarrow Col(B) \subset Col(A) \,,$$
