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?
Numerical Methods for Linear Matrix Equation
-
0The maximum number of columns of $B$ is the dimension of the nullspace of $A$, which is less than $n$ unless $A=0$. – 2012-07-19
2 Answers
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]).
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$.