3.4.36: Maybe A not= C? If nm, maybe if we start from the Rx=d form, and go back with a different set of valid row operations? Example: Ax=b with A=[1 1 2; 0 1 1], b=[3; 4]. We get Rx=d with R=[1 0 1; 0 1 1], d=[-1; 4]. To get back from d to b, pre-mult by [1 1; 0 1], that's the way we came. But we can also get from d back to b with [5 2; 4 2]. Apply to R yields C=[5 2 7; 4 2 6]. Cx=b, same rref so same complete solutions, but C not= A. Is this correct?

Question

3.4.36: Maybe A not= C? If n>m, maybe if we start from the Rx=d form, and go back with a different set of valid row operations? Example: Ax=b with A=[1 1 2; 0 1 1], b=[3; 4]. We get Rx=d with R=[1 0 1; 0 1 1], d=[-1; 4]. To get back from d to b, pre-mult by [1 1; 0 1], that's the way we came. But we can also get from d back to b with [5 2; 4 2]. Apply to R yields C=[5 2 7; 4 2 6]. Cx=b, same rref so same complete solutions, but C not= A. Is this correct?

anonymous · Answer

More generally, if A1 is full row rank so C(A1) = R^m, then b is guaranteed to be in the column space so there is a solution. Find an invertible P such that Pb= b (see example above, in original question). Then P*A1x=P*b, or A2x=b where A2=P*A1, which is different from A1 (again see example above). If the rref of A1 is E*A1=R, so that A1=inv(E)*R, then we have A2= P*inv(E)*R, so the rref of A2 is also R. Therefore A2x=b has the same solutions as A1x=b. This holds even for n x n invertible A1 & A2 as well as for m x n (n>m) matrices. This conclusion seems contrary to the answer given in the textbook (4th ed.) for problem 3.4.36. What do you think?

anonymous · Answer

Not exactly. Notice that it says "for every b". Given 1 specified b, you can find several A like that, but for every b, A=C is correct. 
Therefore the question is ok. However I think the problem lies with the given solution (we can't prove C=A based on Cy=Ay because y can be not invertible). They probably come from different people then. 
My opinion ^_^ (sorry for bad English)

anonymous · Answer

Thank you for the reply - you've helped me see it - very obvious now! With my argument, I would have needed a different C for every different b. But since I have to stick with the same C for every b, the given answer is correct. Another way to see it, maybe: Consider n right-hand sides b1, ..., bn, arrange them as columns of matrix B (m x n). The solutions x1, ..., xn can be arranged as columns of X (n x n). So we have AX=B and CX=B. Now as suggested in the answer given in the book, we can choose B such that X = I (identity matrix); since it has to work for every case it certainly has to work for those cases. So now it is obvious that A = BI and C = BI, so A=C. Thanks again.