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

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?

• @Rodrigo I think the full stop at the end of the first paragraph was correct, and I believe it was a mistake to edit it to a question mark. It is a statement: the general idea of the question is "I know how to do it if you give me the matrix one column at a time; is there a way to do it also if you give it to me one row at a time?" – Federico Poloni Sep 18 '19 at 7:12
• @OP: do you know that you cannot immediately read off the nullspace of $A$ with a QR decomposition, right? You'd need something slightly different like a QRP (also known as rank-revealing QR). Otherwise, if you find an early diagonal zero in an intermediate step it's not clear how to continue. – Federico Poloni Sep 18 '19 at 7:14
• @FedericoPoloni You have infinitely more experience than I in mathematical writing. Please edit my edits until the punctuation is proper. – Rodrigo de Azevedo Sep 18 '19 at 8:07

## 1 Answer

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!