Computing any element of the null space of a singular matrix

Question

Given a singular matrix $A$, what is the fastest method to find a single non-zero solution to $Ax=0$?

Note that we are not looking for the whole kernel, we just want any non-zero vector in it. I know we can use SVD to find eigenvectors, but that seems much too complicated.

Answer 1

If it is known all the eigen values are positive, than a numerical brute force iterative method of the form

$x_{t+1} = (1-c\mathbf{A})x_t$

where $c$ equals $1/\lambda_0$ where $\lambda_0$ is the dominant eigenvalue of $\mathbf{A}$ can be used. Expressing this more generally

$x_{t+n} = (1-c\mathbf{A})^nx_t$

where $n$ represents the $n^{th}$ iteration.

A back of the envelope calculation shows how this works. Consider the eigenvalue decomposition of $\mathbf{A}$,

$\mathbf{A}x_m = \lambda_m x_m$

inserting this equation into the one above results in

$x_{m,t+n} = (1-c \lambda_m)^nx_{m,t}$.

When $x_{m,t}$ is a non zero eigenvector, then the prefactor $(1-c \lambda_m)$ is less than 1 and $q^n$ for q in the range of $-1<q<1$ goes to zero as $n$ approaches infinity. The prefactor $(1-c \lambda_m)$ for the null space, however, evaluates to 1 and does not decrease with iterations. Note that convergence to a single eigen vector is not guaranteed since the null space may be degenerate.

But as was mentioned in the comments, null space packages use SVD under the hood.

Answer 2

You said fastest way, I assume you mean calculation operations, as opposed to code run time - not sure if there is an optimized routine for the algorithm I describe.

You can use row reduction (Gaussian Elimination) with pivoting. See Strang's Linear Algebra textbook (Section 3.2 in 3rd ed) or Gaussian Elimination. It will fail because your matrix is singular. Keep doing it and you will be able to solve for x by backward substitution.

Example:

2 2 3
2 2 1
1 1 5

After subtracting 1.0 times first row from 2nd row, and 0.5 from 3rd row:

1 1 1.5
0 0 -2
0 0 3.5    

Can't get a 1 in 2nd row, 2nd col, even with row exchanges, so you are done. A solution by back substitution is x=[-1 1 0].

You could solve this in MATLAB with null(A) or A\b, but you are right, this is way more calculation than needed.