# Efficient projection of a vector onto matrix kernel

Given an $$m \times n$$ matrix $$A$$ and a vector $$x\in\mathbb R^n$$, with $$m, what's an efficient way of computing the projection of $$x$$ onto the kernel of $$A$$?

One part of the fundamental theorem of linear algebra is that the kernel/nullspace of $$\mathbf A$$ is orthogonal to the range of $$\mathbf A^T$$. By applying the $$\mathbf Q \mathbf R$$ decomposition to $$\mathbf A^T$$, you can generate the orthogonal projector $$\mathbf P = \mathbf I - \mathbf Q \mathbf Q^T$$. The vector $$\mathbf P \mathbf x$$ is what you're looking for. A brief matlab demo follows:

clear all
close all

% Form random A and x.
m = 23;
n = 39;
A = rand(m,n);
x = rand(n,1);

% Find Q = span(A')
[Q,~] = qr(A',0);

% Decompose x = Qx + Px
Qx = Q*(Q'*x);
Px = x-Qx;
norm_Px = norm(Px)
norm_Qx = norm(Qx)
error_x = norm(x-Px-Qx)

% Verify Px is in nullspace of A.
error_APx = norm(A*Px)


If $$\mathbf A$$ is too large but has exploitable structure (sparsity? some kind of H-matrix like rank-deficiency?), you might be better off using using randomized sampling / Krylov ideas, instead of dense $$\mathbf Q \mathbf R$$ decomposition.

• Good answer! Only one remark: this method only works when that $A$ has full row rank. Otherwise one needs to use the first factor of a rank-revealing decomposition (QRP or SVD). Jul 9 '20 at 6:50
• @FedericoPoloni Can you expand? I'm not sure what you mean by "rank-revealing decomposition" Sep 9 at 22:42
• @becko Some decompositions give you numerically stable information on the rank of a matrix; among them QRP and SVD. QR is not one of them. There is a discussion of this in the Golub-Van Loan book, for instance. Sep 10 at 7:17
• @FedericoPoloni But why is this relevant in this context? Why does the above answer fail when $A$ is not full rank? Sep 10 at 7:19
• @becko It's easy to construct examples where it fails; for instance taking A = [1 0; 0 0] and a QR decomposition with $Q = I$; then $P=0$ is wrong. Sep 10 at 9:19