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?

  • $\begingroup$ @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?" $\endgroup$ – Federico Poloni Sep 18 '19 at 7:12
  • $\begingroup$ @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. $\endgroup$ – Federico Poloni Sep 18 '19 at 7:14
  • $\begingroup$ @FedericoPoloni You have infinitely more experience than I in mathematical writing. Please edit my edits until the punctuation is proper. $\endgroup$ – Rodrigo de Azevedo Sep 18 '19 at 8:07

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!

| cite | improve this answer | |

Your Answer

