5
$\begingroup$

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?

$\endgroup$
  • $\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
0
$\begingroup$

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 | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.