If I have a matrix in RREF is there a quick way of pulling out vectors which are not in the span of the row vectors of A?

76 Views Asked by At

Say I am looking for the kernel of a linear function $\mathcal{l}_A$: $\mathbb{R}^n $->$\mathbb{R}^m$ given by the $n \times m$ matrix A. Then say A is row-equivalent to some matrix B in RREF.

Is there a quick way of pulling out the vectors which cannot be expressed as a linear combination of the row vectors in B? therefore giving me a basis for Null(A).

1

There are 1 best solutions below

0
On BEST ANSWER

This is more of a long comment. Let row $1,\dots,r$ of $B$ be the non-zero rows and $j_1,\dots,j_r$ be the columns containing their leading $1$'s. Then each vector $x$ in the null space $N$ of $A$ is given by \begin{align} x_{j_i}=-\sum_{j\neq j_1,\dots,j_r}B_{i,j}x_j \end{align} for all $i=1,\dots,r$, where $x_j$ can be chosen arbitrarily for $j\neq j_1,\dots,j_r$. So one choice of a basis for $N$ consists of vectors given by setting $x_j=0$ for all but one such $j$. For example: Suppose that \begin{align} B=\begin{bmatrix} 1&0&-1&0&-3&-6\\ 0&1&-2&0&-4&-7\\ 0&0&0&1&-5&-8\\ 0&0&0&0&0&0 \end{bmatrix}\,. \end{align} Then columns $3$, $5$ and $6$ correspond to the arbitrarily chosen $x_j$, and $N$ is spanned by \begin{align} {u_1}^T&=\begin{bmatrix}1&2&1&0&0&0\end{bmatrix}\,, \\ {u_2}^T&=\begin{bmatrix}3&4&0&5&1&0\end{bmatrix}\,, \\ {u_1}^T&=\begin{bmatrix}6&7&0&8&0&1\end{bmatrix}\,. \end{align} The point is that these vectors are determined by reading off entries of $B$. That should be quick enough.