Row-based iterative algorithms for computing the kernel of a matrix

Question

Suppose $A$ is an $m \times n$ matrix in the form

$$A=\begin{pmatrix} — a_1 —\\ — a_2 —\\ \vdots \\ — a_m — \end{pmatrix}$$

where $a_i \in R^n$ is the $i$-th row of $A$. I know that it is possible to determine the nullspace of $A$ by QR decomposition. This decomposition can be obtained with the Gram-Schmidt process, which takes one column of $A$ into account at each step of the procedure.

I am looking for direct/fast iterative algorithms with low time complexity which can be utilized to compute the exact/approximate values for a set of vectors that spans the the nullspace (kernel) of $A$ by taking one row of $A$ into account at each step. Are there any?

Answer 1

Assume your matrix is real valued.

If we do $QR$ factorization of a matrix $A$, then $Q$ doesn't tell you anything about the kernel. It tells you about the range space of $A$. In fact the right-most columns of $Q$ -- corresponding to the zero rows of $R$ at the bottom -- span the complement of the range space of matrix $A$.

So, to find the kernel of $A$ you have to do $QR$ decomposition of $A^T$. Then you will get the basis vectors for the range of $A^T$ as well as basis for the complement of the range of $A^T$. Recall that complement of range of $A^T$ is the kernel of $A$.

So to find kernel of $A$ you will have to do $QR$ decomposition of $A^T$ which will automatically use the rows of matrix $A$! You don't need to do anything special!