# Numerical Methods for Linear Matrix Equation

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?

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

You may treat $B$ one column at a time: $$B = \Bigg[b_1\;\;b_2\;\;\ldots\;\;b_m\Bigg]$$ 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]).

-

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

-
+1 for Kronecker! –  draks ... Jul 19 '12 at 15:38