Numerical Methods for Linear Matrix Equation

Question

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?

Answer 1

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]).

Answer 2

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