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.

  • $\begingroup$ I am a bit rusty, does finding the biggest eigenvalue help? I think one just multiplied the matrix with itself to find it, or something similarly easy. $\endgroup$
    – Emil
    Commented Apr 20, 2019 at 7:14
  • 1
    $\begingroup$ See also the discussion (question, answer, and comments) here. $\endgroup$
    – wim
    Commented Apr 20, 2019 at 7:58
  • 1
    $\begingroup$ I would try the inverse iteration in this case. $\endgroup$
    – wim
    Commented Apr 20, 2019 at 8:14
  • 3
    $\begingroup$ @wim To compute one iteration of the inverse iteration, you have to solve a linear system. Whatever factorization you are using to solve it, it will already give you a vector in the kernel. $\endgroup$ Commented Apr 21, 2019 at 12:18
  • $\begingroup$ @FedericoPoloni Yes, that's right. I overlooked that. $\endgroup$
    – wim
    Commented Apr 22, 2019 at 8:21

2 Answers 2


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.


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.


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.

  • 2
    $\begingroup$ null(A) uses the SVD, by the way. $\endgroup$ Commented Apr 23, 2019 at 21:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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