@ymar I created this room here, so that we don't spam the main chat on TeX.SX

Let me repost the links:

Link 1: mathdl.maa.org/images/cms_upload/Yuster19807.pdf

Link 2: cs.uleth.ca/~holzmann/notes/reduceduniq.pdf

Hello!!

hey!

We could use this room on the network for discussing Math. :)

Why not. :)

So what would you like to discuss?

The magic proof, may be?

Sure. I think I understand it now more or less

See, the consistency of a system is known only by looking at its Row-Echelon form, right?

wait a minute, a call

@ymar or, OK, convince me about the last two paragraphs. :)

@ymar Sure, take time. :)

OK, I'm back. Geez, it was my crazy grandma. Now I'm even more tired.

@ymar Oh... sad to hear that from you. Aren't grannies understanding?

Well, not this one. This one is demanding and paranoid.

Never mind, let's get back to the proof.

Do you understand what I am objecting to?

Not exactly. Could you say it again?

I am asking how is he using the consistency of system of equations to conclude that $r = s$

These systems are equivalent. This is clear right?

Yes... because, elementary row operations preserve row space... Is this right to say?

R and S are both equivalent to the original matrix. So they are equivalent. R' and S' are R and S with the same columns deleted, and deleting columns doesn't change equivalence.

(because if we can change R to S by row operations, the same operations will change R' to S')

OK...

Is it not clear?

I am not fully sure.

OK. The original matrix is not named in the proof. Let's name it M.

(Don't we also want the equivalence of systems that R' and S' represent?)

The equivalence of the systems is equivalent to the equivalence of the augmented matrices!

So, we should prove that as a theorem... right?

I guess so. :)

Damn, still a newbie. :) (That is, I am still a newbie.)

No, you're right. Let's think about it then.

Notice that row operations on the augmented matrix correspond to (1) adding a scaled equation to another equation and (2) scaling an equation by a non-zero number

and (3) exchanging the position of the equations too... :)

Yup.

Oh and all elementary operations are reversible by an elementary operation of the same kind!!

They are. And the same is true of the operations on equations.

So, if a tuple is a solution to the original system, it is a solution to the system obtained by elementary row operations, obviously.

And, conversely, because the operations are after all reversible.

Yes. So what have we proved?

Two row-equivalent matrices correspond to systems that are equivalent (≡ that have same solutions).

Yes. And what about the converse? (If two systems are equivalent, then their augmented matrices are too.)

Haven't we proved the converse also?

by using the reversible argument?

We kind of have. If you're sure you understand, we can move on. :)

OK. I'll write this clearly in brief:

1) Suppose you have a system $\Lambda$ of equations. Let $\Lambda$ also denote the augumented matrix. Suppose you have another equivalent system $\Lambda'$ whose matrix is $\Lambda'$. Since, the systems are equivalent, they should have been obtained by a combination of (1), (2) and (3) above. But that results in row-equivalent matrix.

Yes, but there's a small problem here.

Oh, is it this one: "Since, the systems are equivalent, they should have been obtained by a combination of (1), (2) and (3) above"?

Yep.

This needs a proof.

Yes, sure... I was sort of having that feeling.

I can't come up with a proof. :(

Let me think.

So what we have here is this. We have two equations: $A_1x=b_1$ and $A_2x=b_2$ such that the spaces of solutions of these equations are equal.

Yes. Right.

We need to show that there is a finite sequence of elementary matrices $P_1,\ldots,P_n$ such that $A_1=P_n\ldots P_1 A_2$ and $b_1=P_n\ldots P_1 b_2$

Yes... true...

Can we reduce the problem to the case of $b_1=b_2=0$?

Yes... multiply each row by its inverse and subtract first row from each row....

oh, but this will make 1st row to 1... how to get that also to be 0?

I'm thinking more of a substitution. I'm not seeing it clearly, but I'm almost sure it must work.

but are we saying that every system is row equivalent to a homogeneous system? This looks remarkable (and looks also true because a homogeneous system can have all the three possibilities for its solution space...)

It's certainly not true!

how?

scratches his head

Take this system: x=1. (One equation, one unknown.) The space of solutions isn't a vector space!

The solutions of a homogenous system always form a vector space.

And this is only an affine space.

Oh, yeah...

But, we cannot reduce our case then, no?

I think we should be able to do that.

Look

x=1 is equvalent to 2x=2, right?

Yes.

But this equivalence is equivalent to the equivalence of these two equations:

y=0 and 2y=0

where y=x-1

So, you're doing column operations on the matrix, no?

Well, problem is I'm not sure what I'm doing, but I'm sure what I'm doing is right.

I'm making a subsitution.

Hey, no, I am not able to believe this...

Believe what?

that substitution is going to give you row equivalent matrices...

We're not yet talking about the equivalence of matrices, but the equivalence of systems.

Making a subsitution like this doesn't change the equivalence of systems, that's what I'm getting at.

Let's try what it does.

Again, we have $A_1x=b_1$ and $A_2x=b_2$.

Ok. So, if you're substituting for a variable $t$, $t-1$...

To emulate the trivial example above, we have to find a way to move the first equation to zero.

For now, the solutions to the equation form an affine space. We want to make it a vector space.

Ok... I agree.

By some kind of translation.

(Welcome @egreg. To ymar: Enrico is an Algebraist; so he might be able to help us.)

Let's hope so because my imagination is lacking

@ymar Oh, and doing translation will give the same solutions.

Not the same! Translated solutions!

No, I mean translated solutions are the same!

Like in the example above. Compare x=1 and y=0, for x-1=y.

I mean, it's CLEAR from "the solutions to the equation form an affine space. We want to make it a vector space".

@ymar Yes...

OK, so now just need to find the translation.

So, "you have an affine space represented by a couple of equations. Now, translate it and assume that its a vector space represented by doing the translation..."

That's what we are saying no ^^?

What I know about this is that you do only "forward elimination", the final matrix is not unique. But if you do also "backwards elimination", the final matrix is unique. Since elementary row operations are performed by matrix multiplication, if two systems have the same final matrix, they can be obtained by elementary row operations from one another.

@egreg Yes, but we're stuck at trying to prove that if two systems of equations are equivalent then their augmented matrices are too.

@ymar If two systems have the same solution set their reduced matrix must be equal.

@egreg I don't follow what you mean by "forward" and "backward"?

That's what we're trying to prove!

(Eventually)

@kan to obtain the reduced echelon form, you first do the forward elimination to obtain any echelon form, and then the backward elimination to obtain the reduced form

@ymar Oh, OK. Just the names for those processes....

Gee, wait a minute.

Do we need what we are trying to prove?

@ymar Huh? What? Don't we?

Well, in the proof, I think the author uses the easy implication, which we've already proved...

Oh, then, use egreg's argument to finish?

Let's make things explicit because it's gotten messy.

In the proof, we have to matrices R and S that are equivalent by definition.

We delete the same columns in R and S to obtain R' and S'.

Then R' and S' are also obviously equivalent, because deleting the same columns doesn't change equivalence. We've said why.

Now, we've already proved that then the systems of equations that R' and S' represent are also equivalent. This is easy.

Yes... true.

@ymar Be careful: you can delete only "non dominant columns", not those where pivots are found; it's implicit in Holzmann's argument.

Hmm... Why can't I delete any columns? Won't the same row operations work in the case of R' and S' as in the case of R and S anyway?

Exactly my thoughts. I was just afraid to ask.

Since those columns are not used to decide which row operations to perform, the elimination runs in the same way when you delete them.

Yes, deleting the columns with pivots may spoil the row echelon form, but I don't think it'll spoil the equivalence.

Consider the one row matrix [1 2 2]: if you remove the first column, the echelon form becomes [1 1]; if you remove the second column the echelon form is [1 2].

Yes, but this is not the problem. [1 2 2] is equivalent to [2 4 4]. I have to delete the same columns in the first and in the second. If I delete the first ones, I'll get [2 2] and [4 4] which are still equivalent.

This is what I was saying.

In general, if I have any two equivalent matrices A and B, in a reduced echelon form or not, if I delete the same columns in A and B, then the resulting matrices will still be equivalent.

@ymar Look at the proof: it goes by removing non dominant columns, so the first part is the identity (with zero rows added below). The dominant columns are determined by the property that they are linearly independent from the columns on their left.

Well that's true.

(Only he doesn't say he doesn't remove any dominant columns -- a priori, he may remove some that are to the right of the first column in which the two matrices differ.)

Well, I have a couple of questions at this stage:

@ymar Dominant columns are determined a priori and their final form is always a column of the identity. So the two reduced matrices can possibly differ only in a non dominant column

- the resulting matrices R' and S' are in rref but he is not using them any where. Is he?

@egreg I am having slight problems with last sentence:

Consider the matrix:

[1 2 0]

[0 0 1]

@kan Where's the problem? The second column is non dominant, because it is a linear combination of columns at its left.

Doesn't the last statement mean all the set of all columns to the left of a dominant column form a linearly independent set?

@kan No, of course. Any set of pivot (dominant) columns is linearly independent.

@egreg Because they are columns of the Identity matrix, is that right?

@kan In the final form, yes. And row operations don't change linear dependence relations. It's the theorem I'll prove next Tuesday in class.

Ooh. OK.

(If only my Linear Algebra teacher proved these things...)

@egreg yes, that's true. I think it's a bit of a moot point. He still considers the case where the first column in which they differ is dominant (these are the matrices to the right), but it's clearly impossible (and so he says).

Anyway, I think we agree now that the systems of equations represented by R' and S' are equivalent.

@ymar I'd say explicitly in the proof that the two matrices can differ only in a non dominant column, because dominant ones are predetermined. The case is indeed considered. But I wouldn't use that fact.

I do. Just to confirm, what is the outcome of removing same columns (pivot or not) from two row equivalent matrices?

@egreg the fact about inconsistency of systems?

@egreg He says this: R'= something or something else. The something else is a matrix in which the last column is dominant. But the last column in R' is by definition the first column in R in which R differs from S.

@kan Yes.

@kan The outcome is always two new equivalent matrices.

@ymar Ah! Clears up a lot of my brain space.

@egreg Actually, I sort of felt that...

(In the sense, the uniqueness of rref forms the basis of the fact that a system is either consistent or inconsistent and if it is consistent, it has either unique solution or infinitely many... )

if I am not misunderstanding...

@kan we still need to show what you objected to originally.

That if the two systems are equivalent, then r'=s'.

@kan The uniqueness is not necessary to prove that. What you need is the existence of the reduced form.

Yes... true... @ymar.

But this is clear, isn't it?

@egreg you need existence to show that consistency... but how do you know that a system which is consistent will not become inconsistent if you picked some other rref?

@kan Row operations don't change the solution set.

@egreg Oh, yes, that rescues. So, the "rank" of two rref's are the same is an easy consequence. What we are trying to show is their physical equality, now...

Am I right?

@ymar may I ask what are we talking about?

@kan this

@ymar Clear intuitively, you mean? Weren't we stuck at the same point before?

No! We had a much more complicated situation then. Now the equations are as simple as they get.

@kan Not really. One has to prove also that when A = FB, where F is invertible, any linear relation holding between columns of B holds also for the corresponding columns of A; but this is easy.

@ymar I am not seeing... please forgive my ignorance. I am seriously thinking along.

Two systems are equivalent.

R' and S' matrices obtained as explained by Holzmann.

Do you see that the zero rows don't matter?

They translate to 0=0 as equations.

@kan Actually the proof is about one system.

You can just as well omit them. But then you get $I_nx=r'$ and $I_nx=s'$.

@egreg True. I am just incapable of comprehending. :(

...that is simply x=r' and x=s'. These are equivalent only if r'=s'.

@ymar OK. Let me say it this way: Here are two rrefs: R and S. I look at R' and S' as in the notes. So, R' and S' are equivalent by construction. So, the system I get are equivalent.

Thus, x =r' and x = s' is the system, as you said...

no. These are two equivalent systems.

Yes, agreed. Sorry, I was sloppy at the wrong time.

OK.

Thus, completing the proof.

Yes. :) If these two equations are equivalent, then r'=s', which is obvious.

So, the major part of the proof was Holzmann's realisation that a dominant row cannot be erring and if the row erring is a non-dominant row, we can construct equivalent matrices (the first of the two shown in both the cases).

Can someone tell me if I am right there?

I don't know what an erring row is.

the first column that is not matching -- so, erring "column".

sorry, I seriously meant column.

replace row by column everywhere...

Then yes, I think you're right. I still think he structures the proof differently, but it doesn't make any difference. That's it.

OK. Thank you @ymar, @egreg.

I am now going to TeX this up.

May I ask why you deleted your m.se account, kan?

@ymar I find it distracting. And, some of the users there have been very harsh though I have been good to them.

Fair enough.

Ok, slightly differently: if a column is erring, then, it cannot be dominant column or non-dominant column because we can construct R' and S'... Is that OK?

Yes, that's how I read the proof, but it really doesn't matter at all.

But, it is nice to know pre-hand that an erring column cannot be dominant by definition.

Yes.

Oh...cool. I really appreciate the proof now, you know.

This is insight.

How many semesters of LA do you have to do?

Well, the first one was rendered horrible. The second one is a course in modules but matrices make their appearance hurriedly at the end.

And, no more. But, I am resolving to learn every tiny bit of LA today.

I don't understand. You are in your second year, right?

Yes. So, I meant the second semester where we get to see LA...

(technically, the third semester.)

Oh, so you had no LA in your first semester at university?

no, in the second semester.

@kan I had to become a "ricercatore" (which is the first step in our universities), after my PhD, to learn real Linear Algebra. :) I had to do teaching assistance to a course in LA, where Gauss elimination was used for doing most of the work.

I am in my third semester.

Oh, that's really weird.

@egreg Nobody is helping me. I am not asking them to take time, prepare and teach me. I am only asking them to go through what I write and convey any misconceptions they find in the manuscript.

I am really sad.

I started to hate Gaussian elimination when I took a linear programming course. It was so monotonous I couldn't bear it.

@ymar Oh. OK. Let my explorations begin today. I will have to learn these things to a point where I can see things immediately.

@ymar It's less annoying when you see that it provides for simple proofs of important facts. For instance that the ranks of A and A^T are equal.

Of course. But then you don't actually have to do it. You just think of it. But the course was closer to accountancy than to mathematics. Matrix after matrix, eliminate this, augment that...

Just a couple of algorithms, and you had to pretend you're a computer and the piece of paper is a screen.

Oh... I see.

That is terrible.

@ymar knows how my first LA course was taught. Ask him. @egreg...

I don't really remember. :) I remember something was definitely wrong with it.

OK, I think I'll go or I'll yawn my guts out. I'm really tired. See you some time later!

@ymar Sure... And, it was a pleasure having you help me with that really beautiful proof.

@egreg My thanks to you too. But, I might have been slightly paranoid when I asked you and @ymar some questions here. Hope you and ymar did not mind that.

@kan Don't worry! See you.