Why would a solution not exist for an overdetermined system?

[saminny]

Hi,
I have a confusion regarding solving an overdetermined system of equations. Consider M equations and N unknowns. If M > N, then the system is overdetermined. Now since when expressed in matrix form, the column rank is N (in other words N degrees of freedom), the N equations must be linear dependent and reducible to a set of equations <= M. So there would be a unique solution. Then why would a solution not exist for an overdetermined system. I can see from geometry that for in two dimensions, a solution might not exist for parallel lines or three lines, but can't see it from a formal point of view because of linear dependence between them.

A follow up question would be what would take to solve an overdetermined system?

Relevant links:
http://en.wikipedia.org/wiki/Overdetermined_systemIf someone could please explain, it would be very helpful.

thank you,

Sam

 

[Mark44]

Hi,
I have a confusion regarding solving an overdetermined system of equations. Consider M equations and N unknowns. If M > N, then the system is overdetermined. Now since when expressed in matrix form, the column rank is N (in other words N degrees of freedom), the N equations

I thought it was M equations.

must be linear dependent and reducible to a set of equations <= M. So there would be a unique solution. Then why would a solution not exist for an overdetermined system. I can see from geometry that for in two dimensions, a solution might not exist for parallel lines or three lines, but can't see it from a formal point of view because of linear dependence between them.

A follow up question would be what would take to solve an overdetermined system?

Relevant links:
http://en.wikipedia.org/wiki/Overdetermined_system


If someone could please explain, it would be very helpful.

thank you,

Sam

It depends on the system. Here's a simple example.

x + y = 2
2x + 2y = 4
x - y = 0

This system has a unique solution, x = 1, y = 1. In this problem, the 2nd equation is a multiple of the 1st equation (and the 1st equation is a different multiple of the 2nd). If I were to represent this system by an augmented matrix, I could add (-2) times the first row to the 2nd row to get a row of zeroes. The other two rows are not multiples of each other, so I could find the unique solution to the system.

If I had more equations in more unknowns, I would look for equations that were linear combinations of the other equations (most likely by working with an augmented matrix, rather than the equations themselves). I would discard any that I found. (In the matrix, these would be rows of zeroes.) If I still ended up with more equations than variables, there would not be a solution. If I ended up with fewer equations than variables, there would be an infinite number of solutions. If I ended up with the same number of equations as variables, there would be a unique solution.

 

[saminny]

Note there are m equations and n unknowns and m > n.

Lets take an example of a 2D system. Suppose we have 3 equations. So we have 2 unknowns and 3 equations. Now since they all lie in x-y plane, one of those lines can be expressed as a linear combination of the other two and hence can be eliminated using gaussian elimination. So we should always be left with 2 equations and 2 unknowns right? So if these 2 remaining lines intersect in a point, then a solution should be possible.

But this example shows otherwise:

2x1 + x2 = − 1
− 3x1 + x2 = − 2
− x1 + x2 = 1

Any thoughts?

 

[Petr Mugver]

Let A be tha matrix of coefficients and N be the vector of inhomogeneous terms, and let (A|N) the matrix obtained by putting A and N in a same matrix. Then

1) A solution exists if and only if rank(A) = rank(A|N). The solutions form an affine space of dimension = (colums of A - rank(A)).

2) If rank(A) < rank(A|N) then there are no solutions.

3) rank(A) > rank(A|N) is not possible.

 

[Office_Shredder]

Note there are m equations and n unknowns and m > n.

Lets take an example of a 2D system. Suppose we have 3 equations. So we have 2 unknowns and 3 equations. Now since they all lie in x-y plane, one of those lines can be expressed as a linear combination of the other two and hence can be eliminated using gaussian elimination. So we should always be left with 2 equations and 2 unknowns right? So if these 2 remaining lines intersect in a point, then a solution should be possible.

Sort of. Let's look at an example

x+y=2
x-y=0
3x+y=2

You can't treat the lines defined by these equations as vectors. We can consider the x+y=2 to be a vector (1,1), x-y=0 to be a vector (1,-1) and 3x+y=2 to be a vector (1,2) just taking the coefficients of the x and y entries. These would be the rows of the matrix A you're looking at when solving $$Ax=b$$ This would allow us to add a linear combination of the first and the second equation to the third equation to get the left hand side equal to zero. But this says nothing about the right hand side.

For this example we have 2(x+y)+(x-y)=3x+y so we take 2 times the first equation and add it to the second equation to get

3x+y=4

and subtract that from the third equation to get

0=2

This is the procedure you're doing to reduce the rank of A. Performing row operations is like changing the basis of the codomain, so you have to do the same changes to b also. In this case we're still left with an inconsistent set of equations.

If you want to think about it in terms of the augmented matrix (A|b), then when you put it in row echelon form, you have an inconsistent set of equations when the final non-zero row has an entry only in the rightmost column

 

[saminny]

Sort of. Let's look at an example

x+y=2
x-y=0
3x+y=2

You can't treat the lines defined by these equations as vectors. We can consider the x+y=2 to be a vector (1,1), x-y=0 to be a vector (1,-1) and 3x+y=2 to be a vector (1,2) just taking the coefficients of the x and y entries. These would be the rows of the matrix A you're looking at when solving $$Ax=b$$ This would allow us to add a linear combination of the first and the second equation to the third equation to get the left hand side equal to zero. But this says nothing about the right hand side.

Thanks for the explanation. I am having trouble understanding the cartesian equations. When you change the right hand side of the equation, it changes x-intercept or y-intercept. But the line is still a vector. How does that affect the solution? The same thing applies to my lack of understanding of linear independence. 4c1 + 3c2 = 0 implies vectors c1 and c2 are linearly dependent. Why does 4c1 + 3c2 = 2 implies they are linearly independent as c2 can still be expressed in terms of c1. So, to summarize I am unable to foresee how the right hand side is affecting things.

 

[Mark44]

Thanks for the explanation. I am having trouble understanding the cartesian equations. When you change the right hand side of the equation, it changes x-intercept or y-intercept.

No, changing the constants on the right changes the point of intersection. An x-intercept is a point where a line or curve crosses the x-axis; a y-intercept is a point where a line or curve crosses the y-axis.

But the line is still a vector.

A line (and more specifically, the equation of a line) is different from a vector. A vector can be parallel or antiparallel to a line.

How does that affect the solution? The same thing applies to my lack of understanding of linear independence. 4c1 + 3c2 = 0 implies vectors c1 and c2 are linearly dependent.

Yes, but we're talking about equations of lines, such as 4x + 3y = 0, where x and y are NOT vectors: they are scalar quantities.

Why does 4c1 + 3c2 = 2 implies they are linearly independent as c2 can still be expressed in terms of c1. So, to summarize I am unable to foresee how the right hand side is affecting things.

Let's look at the example I gave back in post #2. Here is the system as an augmented matrix.
$$\left[ \begin{array}{cc|c} 1 & 1 & 2\\2 & 2 & 4\\1 & -1 & 0\end{array}\right]$$

The augmented matrix is a way to write the following matrix equation more compactly.
$$\left[ \begin{array}{cc} 1 & 1 \\2 & 2 \\1 & -1 \end{array}\right] \left[ \begin{array}{c} x \\ y \end{array}\right] = \left[ \begin{array}{c} 2 \\ 4 \\ 0 \end{array}\right]$$

This matrix equation can be written symbolically as Ax = b, where A is the 3 x 2 matrix, x is the column vector <x, y>, and b is the column vector <2, 4, 0>.

Each row of A can be interpreted as a vector in R². Since there are three rows, it's not possible for the rows to be linearly independent. If you row-reduce this matrix, one of two things will happen: either you get a single row of zeroes or you get two rows of zeroes. If you end up with just one row of zeroes, there will be a unique solution, provided that the constant in the same row in b is also zero. (The row reduction necessarily needs to be done in an augmented matrix, so the entries in b will most likely be changed.)

If you end up with two rows of zeroes, there will be an infinite number of solutions, provided that the two constants in the same rows in b are also zero.

If you put different values in the b vector, you will be affecting whether the matrix equation has solutions or not, particularly when you put nonzero values in b in any position for which there is a row of zeroes in the reduced matrix for A.

In my example, the unique solution is x = 1, y = 1.

If I change the vector b as shown below (<2, 4, 0> is now <2, 5, 0>), the equation now has no solution.

$$\left[ \begin{array}{cc} 1 & 1 \\2 & 2 \\1 & -1 \end{array}\right] \left[ \begin{array}{c} x \\ y \end{array}\right] = \left[ \begin{array}{c} 2 \\ 5 \\ 0 \end{array}\right]$$

As an augmented matrix, the equation above looks like this.
$$\left[ \begin{array}{cc|c} 1 & 1 & 2\\2 & 2 & 5\\1 & -1 & 0\end{array}\right]$$

By row reduction, we get this equivalent augmented matrix:
$$\left[ \begin{array}{cc|c} 1 & 0 & 1\\0 & 0 & 1\\0 & 1 & 1\end{array}\right]$$


If we rewrite the augmented matrix as a system of equations, they are
x = 1
0x + 0y = 1
y = 1

It should be obvious that this system has no solutions.