Question

Hi,
I need an algorithm to solve the following general equations:
a1x+b1y+c1z=0
a2x+b2y+c2z=0
a3x+b3y+c3z=0
I can't use Cramer's rule because Dx=Dy=Dz=0.
I've looked at Matrix Row Operations but can't see how to apply that to the three simultaneous equations stated above.
Any ideas?

Answer 1

creating a formula for that is going to look ridiculous >.< if you need a method, row reduction is best, but applying it straight to variables will just create a mess.

Answer 2

You can use the determinant of the matrix to tell if its even worth carrying out row operations though. If your determinant isnt equal to 0, then the only solution to that system is x = 0, y = 0, z = 0. If it is equal to zero, you will have some non-trivial solutions to that system, and you should start carrying out row operations.

Answer 3

Not sure that I fully understand. Here's a concrete example:

x + 2y + z = 0
6x -y = 0
-x -2y - z = 0

This has a solution x=1, y=6, z=-13. Yet d1=d2=d3=0 so Dx=Dy=Dz=0. I think the determinant you suggest is:

| 1 2 1 |
| 6 -1 0 | = nonzero yet there are real solutions for x, y, z
|-1 -2 -1|

Answer 4

Thew determinant of that matrix is 0, the last row is the first one times (-1), so that matrix can be row reduced to:
1 2 1
6 -1 0
0 0 0
Whenever there is an all zero row or column, the determinant is 0

Answer 5

So because the determinant is 0, you know there has to be some other solutions other than x = y = z = 0, so you can reduce the matrix further to figure out what they are. Are you comfortable reducing matrices? or should we go through this one?

Answer 6

To develop an algorithm (code), you need constraints on the coefficients.

Answer 7

It's called row reduction or Gaussian elimination.

Answer 8

It might be a little tricky to implement the algorithm, but its certainly possible. Not only that but I'm sure you can find the code out there since its a very common task.

Answer 9

I'm comfortable with the principles of reducing matrices. I just need to confirm my start point and end goal. The example I've read demonstrates matrix reduction for a 2 variable + 2 equation system. I'm trying to apply this example to a 3 variable + 3 equation system. I *think* my start point is something called an augmented matrix (just spotted the "Equation" button so I hope this displays correctly):

\[\left[\begin{matrix}1 & 2&1&0\\6&-1&0&0\\ -1 & -2&-1&0\end{matrix}\right]\]

...and I *think* my end goal is:

\[\left[\begin{matrix}1 & 0&0&x\\0&1&0&y\\ 0 & 0&1&z\end{matrix}\right]\]

...where x, y, z are the solutions to my system. If you can confirm these ideas then I'll spend an hour working through this concrete problem to convince myself that I undetrstand the process.

Answer 10

The thing is, if the determinant of the matrix is 0, then its not even possible to get the matrix in that form (the identity matrix).

Answer 11

Gaussian elimination is an algorithm. It describes a method for reaching the desired goal. Basically the strategy is to get leading 1s in each row using row operations.

Answer 12

http://en.wikipedia.org/wiki/Gaussian_elimination

Answer 13

if you had a system like you wrote in your problem (Ax = 0), and you are able to use Row Reduction to get the matrix A to be
1 0 0
0 1 0
0 0 1
Then the only solution has to be x = 0, y = 0, z = 0.

Answer 14

joemath that's clear just by the very nature of bijective transformations.

Answer 15

Recall that a bijective (one to one and onto) transformation has only a trivial null space.

Answer 16

yes, i know that <.< lol , im trying to explain it.

Answer 17

Hi joemath314159 and Alcemista. These are great answers but they are contradictory. Joemath suggests the system can't be solved by row reduction and Alchemista is suggesting an algorithm. I've found a paper which describes the algorithm well enough for me to follow:

www.math.hmc.edu/calculus/tutorials/linearsystems/linearsystems.pdf

Question is, can I apply this to my original general-purpose problem where d1=d2=d3=0 or do I need to find a different algorithm? Note that a1,a2,a3,b1,b2,b3,c1,c2,c3 will always be real (but any one f them might might be zero) and I need to solve the general purpose definition many times for different measurements taken from a real-world system.

Answer 18

Yes I'm saying it can be solved when there is a solution of course.

Answer 19

Remember that systems of equations are not always consistent. There are cases when no solution exists.

Answer 20

The algorithm will help you find a solution, or it will be obvious from the result of the algorithm that no solution exists if none exist.

Answer 21

or that infinitely many solutions exist (as in your example)

Answer 22

for this matrix:
1 2 1
6 -1 0
-1 -2 -1
any multiple of your answer will work, x= -1, y = -6, z = 13
x = 2, y = 12, z = 26 works, so on and so forth.

Answer 23

Seems I chose a poor example. Your answers have given me sufficient confidence to pursue matrix row reduction implemented using a Gaussian Elimination algorithm. Thank you both for your patience and help. Now I'll try to click on the correct reward buttons for each of you.

Answer 24

Think I'll update my previous statement based on joemath314159 observing that "any multiple of your answer will work"...that's because solving the three simultaneous equations are ultimately solving an Eigenvector problem.

Answer 25

No, that is something altogether different.

Answer 26

If there is a nontrivial nullspace there will be an infinite number of solutions which will take the form of a line, plane, etc. depending on the dimension of the solution space.

Answer 27

But for something to be an eigenvector the image of the vector must be the same with the only difference being the scalar. This scalar is the eigenvalue.