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.

-
You can always (try to) solve the corresponding system of linear equations, but it's probably not the most efficient method. – Gregor Bruns Aug 28 '12 at 12:32
@GregorBruns - We get a system of $n^2$ linear equations and with $n^2$ variables, right ? – Belgi Aug 28 '12 at 12:36
yes, it's pretty huge. Of course, if you have symmetric or sparse matrices, it becomes more feasible. – Gregor Bruns Aug 28 '12 at 12:39
@GregorBruns: The system automatically decouples into $n$ independent system of $n$ equations in $n$ variables each. And the coefficient matrix of each of these $n$ independent systems is exactly $A$! – Henning Makholm Aug 28 '12 at 12:49
I had posted an answer and I deleted. I thought you were looking for solving an under determined system $Ax=b$, where $x$ and $b$ are vectors which is not the case in your problem. Anyways, there is a method called the Lagrange multipliers which is used to handle under determined system $Ax=b$. I do not know if it can be extended to your problem. Here is the reference. – Mhenni Benghorbal Aug 28 '12 at 13:48

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) \,,$$

-
I just realized that this solution is orthogonal to user8268s solution :) – N. S. Aug 28 '12 at 13:42
But this solution is better, +1. – Marc van Leeuwen Aug 28 '12 at 13:56

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$.

-

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.

-
Solving the problem as Henning Makholm indicates is probably easier than calculating $\mathrm{rank}(A)$ and $\mathrm{rank}(B)$. – Marc van Leeuwen Aug 28 '12 at 13:59
@MarcvanLeeuwen I did not anticipate anyone wanting to use the rank so precisely. I meant that it could be a simple indicator if one could see something about the rank immediately. For instance, if $B$ was obviously invertible, and $A$ had a zero row, or something along these lines. – rschwieb Aug 28 '12 at 14:03

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$.

-