5
$\begingroup$

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.

$\endgroup$
  • $\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 Apr 20 at 7:14
  • 1
    $\begingroup$ See also the discussion (question, answer, and comments) here. $\endgroup$ – wim Apr 20 at 7:58
  • 1
    $\begingroup$ I would try the inverse iteration in this case. $\endgroup$ – wim Apr 20 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$ – Federico Poloni Apr 21 at 12:18
  • $\begingroup$ @FedericoPoloni Yes, that's right. I overlooked that. $\endgroup$ – wim Apr 22 at 8:21
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

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

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.