Sign in to follow this  

Linear system solving

This topic is 4085 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Solving a system of linear equations is fairly easy: there are algorithms for determining if a solution exists, if it is unique, and what it is. I'm having a problem that is a little bit more specific than that. I have a system which is not necessarily inversible. I can determine pretty easily if it has a solution, so I'll assume from now on that a solution x = (x1...xn) exists. Note that there is potentially an infinite number of solutions different from this one. What I want to do is find a solution x, and determine a set of coordinates (xi...xj) which will be the same for every other solution to the system. As an example:
0 = x + y + z
0 = x

 (0,0,0) is a solution
 for every solution, x = 0
What kind of algorithm can provide this kind of functionality with reasonable time complexity?

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
What I want to do is find a solution x, and determine a set of coordinates (xi...xj) which will be the same for every other solution to the system. As an example:


It doesn't always work like that.
In general, your set of solutions is some subspace(*) of the entire space. Eg. a plane in a 3D space - but not necesarilly paralel to any axis.

(*) It is a subspace if 0n is a solution, otherwise it is a subspace + some offset (this offset being one of the solutions).

Share this post


Link to post
Share on other sites
Quote:
Original post by deffer
It doesn't always work like that.
In general, your set of solutions is some subspace(*) of the entire space. Eg. a plane in a 3D space - but not necesarilly paralel to any axis.


I know. However, I have good reason to believe that this will be the case quite often (there are big empty blocks inside the matrix, which almost nearly isolate subsystems).

Basically, any solution can be written as Xι = C + Vι, where Vι is in Ker B and BC = Y. I'm looking for C and for the zero-coordinates of ∀ ι Vι.

Share this post


Link to post
Share on other sites
Alright, after working on the rest of my program, I found out I can settle on a simpler version of this: I don't need to find a solution X, I only need to find the coordinates of X that are shared between all solutions.

Share this post


Link to post
Share on other sites
The null-space is the key to finding the complete solution to the system. The basic idea is that with a system Ax = b, when the rows/columns are linearly independent you have a single solution to Ax = 0, which is x = 0. When the rows/columns aren't linearly independent (which is the case for all non-square matrices), there are an infinite number of solutions Ax = 0. Now express Ax = b as Ax + Ay = b + 0, or A(x + y) = b + 0, such that Ax = b and Ay = 0. It becomes clear that you need to find both x (which is called particular solution) and y (which is the null-space) and add them together to completely solve the system. With an invertible matrix, the null-space is R0 and y = 0, and the y term is omitted because it's implied. But in a system where the null-space is a positive dimension, it can't be omitted because it contains more than just the zero vector.

I won't go into the whole process of finding the full solution since it's rather lengthy to explain and there are shortcuts in the algorithm you can use if all you need are the common coordinates. What you first want to do is take your system A, and put it into reduced row echelon form. So:

| 1 1 1 | becomes | 1 0 0 |
| 1 0 0 | | 0 1 1 |

Now look for all rows with a 1 followed (and preceded) by all 0's. The coordinates corresponding to those row are common to all solutions. This concurs with your observation that x is the same for all solutions, however this method doen't actually tell you what x is other than that it's common. You can find this value, however, if you reduce the augmented matrix | A b |. Then the last column will tell you what that actual value of the common coordinate is. Note that the augmented matrix reduction is also how you could find a suitable particular solution.

Share this post


Link to post
Share on other sites

This topic is 4085 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this