3
$\begingroup$

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.

  • 0
    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](http://people.csail.mit.edu/bkph/articles/Pseudo_Inverse.pdf).2012-08-28

4 Answers 4

2

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

  • 0
    But this solution is better, +1.2012-08-28
5

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

4

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.

  • 0
    @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.2012-08-28
2

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