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.

How can I solve (numerically) the linear equation $AB=0$. where $A\in\mathbb{R}^{n\times n}$ and $B\in\mathbb{R}^{n\times m}$? How much is the computational cost?

share|improve this question
1  
Solve for what? Do you want to find one solution, or all solutions? –  Chris Taylor Jul 19 '12 at 10:42
    
Yeah, sorry.. the matrix B is the unknown matrix while the matrix A is known. I need just a solution B. –  user1241138 Jul 19 '12 at 10:47
3  
$B=0^{n\times m}$ costs nothing, it's free! –  draks ... Jul 19 '12 at 10:58
    
of course B not $0$. In particular i would like $$B = \left[ \matrix{ {I_n} \cr X \cr} \right]$$ with $X\in \mathbb{R}^{m\times n}$ –  user1241138 Jul 19 '12 at 11:12
    
Your dimensions don't match up. You said that B is nxm, but you now seem to be asking for it to be (n+m)xn. –  Chris Taylor Jul 19 '12 at 11:24

2 Answers 2

up vote 1 down vote accepted

You may treat $B$ one column at a time: \begin{equation} B = \Bigg[b_1\;\;b_2\;\;\ldots\;\;b_m\Bigg] \end{equation} where the $b_i$ are column vectors of length $n$ (and there are $m$ of them).

If $A$ is invertible, it spans $\mathbb{R}^n$ and the only solution is $B=0$. Otherwise you are looking for vectors $b_i$ in the nullspace of $A$. Suppose $A$ has rank $r$ (number of independent columns). Then dim N($A$) = n-r. This means that there are $n-r$ independent vectors that give $Ax=0$; these x's form a basis for N($A$). So every matrix $B$ whose columns are linear combinations of these x's will give $AB=0$.

As for computational cost, the effort is in finding a basis for N($A$). Usually this is an operation of order $O(n^2)$.

Reducing $A$ to it's echelon form, the columns which do not look like the identity matrix will contain the basis for the nullspace (in MATLAB this is rref(A) and in Mathematica it is RowReduce[A]).

share|improve this answer

I find it helpful to reformulate the equation with the help of the Kronecker Product: With the vectorization operator $\mathrm{vec}$ which stacks all columns of a matrix into a large vector it holds that $$ \mathrm{vec}(ABC) = (C^T\otimes A)\mathrm{vec}(B) $$ and this allows you to reformulate $AB=0$ as a usual linear system for $B$.

share|improve this answer
    
+1 for Kronecker! –  draks ... Jul 19 '12 at 15:38

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.