Proving Impossible: Equivalent Homogeneous Systems of Linear Equations

[coderdave]

A question at the end of a chapter in a book I'm reading asked me to prove something which I'm thinking is a mistake because it seems to be impossible to prove.

'Prove that if two homogeneous systems of linear equations in two unknowns have the same solutions, then they are equivalent.'

The book defines equivalence to be 'two systems of linear equations are equivalent if each equation in each system is a linear combination of the equations in the other system'.

I can think of two systems which share the same solution (the trivial solution) that are not equivalent. That is the second system of homogeneous linear equations are not a combination of the first system of homogeneous linear equations but they both share the same solution.

system 1,
x - y = 0
2x + y = 0

system 2,
3x + y = 0
x + y = 0

Am I right in believing that their question is malformed or am I wrong in believing that you can not get x + y as a linear combination of c1(x - y) + c2(2x + y).

Thank you,
-= Dave

 

[JoanBraidy]

A question at the end of a chapter in a book I'm reading asked me to prove something which I'm thinking is a mistake because it seems to be impossible to prove.

'Prove that if two homogeneous systems of linear equations in two unknowns have the same solutions, then they are equivalent.'

The book defines equivalence to be 'two systems of linear equations are equivalent if each equation in each system is a linear combination of the equations in the other system'.

I can think of two systems which share the same solution (the trivial solution) that are not equivalent. That is the second system of homogeneous linear equations are not a combination of the first system of homogeneous linear equations but they both share the same solution.

system 1,
x - y = 0
2x + y = 0

system 2,
3x + y = 0
x + y = 0

Am I right in believing that their question is malformed or am I wrong in believing that you can not get x + y as a linear combination of c1(x - y) + c2(2x + y).

Thank you,
-= Dave

itd be best to see what's going on geometrically ...a system of 2 linear equations in 2 variables represents 2 lines through the origin

 

[Martin Rattigan]

...
Am I right in believing that their question is malformed or am I wrong in believing that you can not get x + y as a linear combination of c1(x - y) + c2(2x + y).
...
-= Dave

The latter. $x+y=(-\frac{1}{3})(x-y)+(\frac{2}{3})(2x+y)$.

 

[coderdave]

The latter. $x+y=(-\frac{1}{3})(x-y)+(\frac{2}{3})(2x+y)$.

Thank you Martin. I spent a long time thinking about how to represent x + y as a linear combination of those two and couldn't figure it out. Now that I see the answer its pretty obvious.

Is there a systematic approach to figuring it out or did you just do it in your head.

Thank you,
-= Dave

 

[Hurkyl]

Is there a systematic approach to figuring it out or did you just do it in your head.

Just solve the equation

x+y = c₁(x-y) + c₂(2x+y)​

for c₁ and c₂.

(It may help to collect all of the x's together and all of the y's together)



P.S. it may be interesting to rewrite everything in terms of matrices and vectors.

 

[coderdave]

Just solve the equation

x+y = c₁(x-y) + c₂(2x+y)​

for c₁ and c₂.

(It may help to collect all of the x's together and all of the y's together)

P.S. it may be interesting to rewrite everything in terms of matrices and vectors.

Thanks. In fact, after I wrote this post I went to lunch and I couldn't stop thinking about it and came up with the solution on a napkin. I formulated in terms of vector and matrices and solved for it.

Now that I know how to solve for it I just have to figure out how to prove it.

Thanks very much!
-= Dave

 

[alice22]

Don't want to sound stupid but is not x=y=0 the solution? :)

 

[Klockan3]

Am I right in believing that their question is malformed?

No, you are wrong.

The solution space are all vectors orthogonal to each row vector, which means that the row vectors must span the orthogonal complement to the solution space. This in turn means that for anyone solution space each set of row vectors can produce each other set of row vectors for equivalent equations.

I put a small proof in spoiler white above.

 

[HallsofIvy]

Don't want to sound stupid but is not x=y=0 the solution? :)

x= y= 0 is a solution to any homogeneous set of equations but if the determinant of the coefficient matrix is 0, the set of all solutions is a subspace of \(\displaystyle R^n\).

 

[alice22]

x= y= 0 is a solution to any homogeneous set of equations but if the determinant of the coefficient matrix is 0, the set of all solutions is a subspace of \(\displaystyle R^n\).

No it isn't, x + y = 4

does not have a solution of x=y=0.

What is this matrix? I see no matrix.

 

[Klockan3]

No it isn't, x + y = 4

That is not a homogeneous equation.

 

[alice22]

That is not a homogeneous equation.

Why not?
Whats wrong with it?
Homogeneous has loads of different meanings in wikipedia, can you explain what you mean by it in simple (laymans) terms?

 

[Klockan3]

Why not?
Whats wrong with it?
Homogeneous has loads of different meanings in wikipedia, can you explain what you mean by it in simple (laymans) terms?

Try checking the relevant maths page?
http://en.wikipedia.org/wiki/System_of_linear_equations#Homogeneous_systems

Now I don't really know your background so maybe you haven't studied linear algebra, then I would have taken a bit more time explaining things.

 

[uart]

Don't want to sound stupid but is not x=y=0 the solution? :)

Yes Alice that is totally correct for both of the examples given by the OP. Both of the examples given are "full rank" so the only solution is zero.

x + y = 4 does not have a solution of x=y=0

Homogenious in this sense simply means that the RHS is the zero vector, so a better example would be x + y = 0. Now we see that x=y=0 is still a solution, but it is no longer the only solution.