# How do I solve Ax = 0?

I am performing orthogonal distance regression on a set of points to find the best fit plane. I am using the method described on this page http://www.infogoaround.org/JBook/LSQ_Plane.html

The problem is that I end up with a linear homogenous system of the form:

Ax = 0

And I don't know a good computational way to solve this. (The author of the webpage says it is just an eigenvalue problem, but that looks nothing like an eigenvalue problem to me.)

A is a symmetric 3x3 matrix. I am writing some code to solve this (custom system so I can't use matrix libraries) and I'm not sure the best way to do it.

I would think there is a better/easier/more efficient method than Gauss-Jordan, but I don't know what that would be.

SVD seems to be promising, but the Wikipedia page makes it seem too intimidating to program!

Thanks

-
Could you make explicit what $A$ is? If it is $3\times 3$, then solving the system should be fairly easy. – Pedro Tamaroff Oct 4 '12 at 1:47
Are you looking for all x that solve this? you know x=0 is one solution right? – Bitwise Oct 4 '12 at 1:56
A = {{Σ xi xi, Σ xi yi, Σ xi zi}, {Σ yi xi, Σ yi yi, Σ yi zi}, {Σ zi xi, Σ zi yi, Σ zi, zi}} for a set of n coordinates {xi, yi, zi} – Nick Oct 4 '12 at 1:57
@Bitwise, I mention at the top of my post that I am trying to find a best-fit plane for a collection of points. So I'm afraid the trivial solution won't help me. – Nick Oct 4 '12 at 1:58
X is in the span of eigenvectors which are associated with 0 eigenvalues. – Tpofofn Oct 4 '12 at 1:59

To regard the question about how is this an eigenvalue question:

Consider $B=\{e_{1},e_{2},e_{3}\}$ the standard basis of $\mathbb{R}^{3}$ and define $T:\mathbb{R}^{3}\to\mathbb{R}^{3}$ by $T(v):=Av$

You are looking for $ker(T)$ by definition.

Since $A$ is symmetric it is also diagonisable, if $v_{1},v_{2},v_{3}$ are independent eigenvector of $A$ then in the basis $B'=\{v_{1},v_{2},v_{3}\}$ you get the system $Dx=0$ where $D=diag(\lambda_{1},\lambda_{2},\lambda_{3})$ where $\lambda_{i}$ are the eigenvalues of $A$. Of course this system is very easy to solve.

You can always go back and write the solutions you found as a linear combination of the elements of $B$ (you can build a $3\times3$ matrix that takes vector written as linear combination of elements of $B'$ and gives you the vector written as linear combination of elements of $B$).

This also gives an algorithm (though I don't know about efficacy) , note that there is a closed formula to calculate the roots of a polynomial of degree $3$, but I think calculating the corresponding eigenvectors is as difficult as solveing the original question so I won't try this method.

-
@Peter - thanks, I should not trust Lyx corrections anymore – Belgi Oct 4 '12 at 2:02
No problem. I had missed an "o", though. – Pedro Tamaroff Oct 4 '12 at 2:18
I don't get how this helps. Isn't the only solution to Dx = 0 the trivial solution (0, 0, 0), which would be (0, 0, 0) in basis B as well? The goal is to find a nontrivial solution. – Andy Sep 22 '15 at 13:53

I am the author of the mentioned article at infogoaround.org. You can solve the eigen pair problem via the power method. If you still want the solution, let me know. I can send you a C program to solve the dominant eigen pair.

-