My Math Forum  

Go Back   My Math Forum > College Math Forum > Linear Algebra

Linear Algebra Linear Algebra Math Forum


Reply
 
LinkBack Thread Tools Display Modes
November 17th, 2018, 08:54 AM   #1
Newbie
 
Joined: Nov 2018
From: France

Posts: 8
Thanks: 0

Row reduced echelon form and its meaning

Hey.

I have the following question to solve:

* Given a matrix A that is size m x n and m>n.
Let R be the RREF that we get by Gaussian elimination of A.
Prove that the system equation Ax=0 has only one solution iff in every column of R there is a leading element.

I have some answer of intuition so I'm not really sure,
Let's assume that we had R with some free variable, and we know(?) that any free variable has a degree of freedom which means that it yields infinite number of solutions.

Now, I am not sure again about the establishment of this proof and to what extent it's accurate. Moreover, I am not if it proves the point of iff (equivalence).

Another similar question, but I have no idea what it means:

* Given a matrix A that is size m x n and m>n.
Let R be the RREF that we get by gaussian elimination of A.
Prove that for every the system equation Ax=b has a solution iff R doesn't have zero rows.

Thank you!
CStudent is offline  
 
November 17th, 2018, 08:58 PM   #2
Newbie
 
Joined: Nov 2018
From: France

Posts: 8
Thanks: 0

Rows of zeros
CStudent is offline  
January 27th, 2019, 06:16 PM   #3
Newbie
 
Joined: Jan 2019
From: Adelaide Australia

Posts: 3
Thanks: 0

Hi CStudent,

I'll try to help you approach this in a way that you can feel confident that it has been proven.

The first thing to notice is the abbreviation "iff" which means "if and only if".

Let the statement J be "Ax=0 has only one solution".

Let the statement K be "In every column of R there is a leading element".

Then your question requires us to prove that "J iff K".

To do this, we need to prove two things:
  1. If J, then K.
  2. If K, then J.

This is what is meant technically when we say "if and only if".


==========
PART 1
==========

So let's start with the first part. Assume that J is true, and let's now try to show that K will also be true.

J is true, so that means that the system of equations represented by Ax=0 has only one solution. To show that B is true, we'll use a common proof technique called "Proof by Contradiction". Basically it means that we want to show that B is true, so we'll assume that it is NOT true, and then show that it leads to an impossibility. When we get to that point of impossibility, we'll know that it was caused by our faulty assumption that B is false. So we'll have to conclude that in fact B is true.

So, let's now assume that B is false. This would imply that there is some column of R that does not have a leading element. In other words, R would have a row of zeros. Suppose that it's index i for which no row has a leading entry in column i.

Column i corresponds to variable x_i. Therefore x_i is a free variable, meaning that we can set it to any value that we like. This is usually expressed as something like Let x_i = t, where t is a real number. Then use the RREF matrix R, we could then back-substitute that value of t and solve for the other variables. Since we can use any real number t, it means that we can come up with infinitely many solutions to the system of equations. But this should not be possible, because we started off with the assumption that Ax=0 has only one solution. So we are forced to conclude that our assumption that B is false is actually wrong. Therefore B must be true.

So overall, we've just shown that "If A, then B."

==========
PART 2
==========

Now we're going to the second part, which is to prove that "If B, then A".

So assume that B is true, i.e. that in every column of R, there is a leading entry.

It follows that the extended matrix [A|0] would have been reduced to [I|0], where I is the identity matrix, possibly with additional zero rows at the bottom. The solution implied by R is therefore, x_1 = 0, x_2 = 0 etc. (all variables equal to zero).

So the question is, can we conclude that Ax=0 has only 1 solution?

We know that it has a solution (i.e. all variables equal to zero). But can there be any others?

Assume that there exists another solution B = (b_1, ..., b_n) where for some index i, b_i is not zero.

Each of the elementary row operations performed during the row reduction process corresponds directly to manipulating the original equations in the variables x_1, ..., x_n. Since the B is a solution to the original system of equations, B will also be a solution to the system of equations obtained after each elementary row operation. Hence, B is also a solution to the system of equations corresponding to RREF form, Rx=0. But we've seen that R contains I. So it must be that 1*x_i = 0 from the matrix equation Rx=0. So it must be that 1 * b_i = 0. But b_i is not zero. So again we get a contradiction.

It follows that our assumption that there exists another distinct solution is incorrect.

So we conclude that Ax=0 has a unique solution.

Finally, having proved part 1 and part 2, we've proven the original statement.


I hope this helps add some formal structure to the intuitions you've had about the problem.

Cheers,

Last edited by skipjack; February 4th, 2019 at 12:05 AM.
RichardEmt is offline  
Reply

  My Math Forum > College Math Forum > Linear Algebra

Tags
echelon, form, meaning, reduced, row



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Reduced row echelon form interpretation king.oslo Linear Algebra 2 April 6th, 2014 08:54 AM
How did get this reduced echelon form of A matrix? artiny Linear Algebra 2 October 18th, 2013 10:02 AM
How do I get this into reduced row echelon form? PhizKid Linear Algebra 2 September 9th, 2013 11:54 PM
reduced row echelon form remeday86 Linear Algebra 1 June 22nd, 2010 07:10 PM
Reduced row echelon form of a matrix yyttr4 Linear Algebra 0 June 3rd, 2010 03:41 PM





Copyright © 2019 My Math Forum. All rights reserved.