Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
@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

4 Answers 4

up vote 2 down vote accepted

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

share|improve this answer
    
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$.

share|improve this answer

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.

share|improve this answer
    
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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.