Homework 3 Solution

We discussed in class the concept of equivalence relations and then studied a very speci c equivalence relation de ned over the set Mm n(R). The goal of this question is to review these concepts.



Denote by S the set of all students in our class. Give examples of three di erent relations that one can de ne over the set S which are equivalence relations. Explain why you claim that they are equivalence relations. For example, you can check that the following relation is an



equivalence relation: "For a; b 2 S we say that a b if b has the same amount of siblings as a does".




Denote by S the set of all students in our class. Give examples of three di erent relations that one can de ne over the set S which are not (necessarily) equivalence relations. Explain why you claim that they



are not (necessarily) equivalence relations. For example: the relation




de ned by: "For a; b 2 S we say that a b if b enjoys the company of a", is not (necessarily) an equivalence relation as (unfortunately) it may happen that this relation is not symmetric (that is, b might enjoy the company of a while a does not enjoy the company of b so much).




It also may happen that this relation is not transitive (that is, it can happen that c enjoys the company of b, and b enjoys that of a, however




c does not enjoy being around a at all). In fact, this relation might even




not be re exive (it can happen that a person extremely su ers from the company of himself...).




The relation de ned over R2 by (x1; y1) (x2; y2) if x1 = x2 is an equivalence relation. Prove this fact. Can you describe the equivalence classes obtained by this equivalence relation?



The relation de ned over R2 by (x1; y1) (x2; y2) if x1 + x2 = 0 is not an equivalence relation. Prove this fact.



In class we de ned a very speci c relation over Mm n(R) and proved that this speci c relation is an equivalence relation. Complete this sen-tence: "For A; B 2 Mm n(R) we de ned that A B if ...". Recall that in this case, we say that A and B are row equivalent.



For the speci c equivalence relation de ned in (v), give examples of 3
di erent matrices which are in the equivalence class of the matrix

0 1

1
1
1
A :
@ 0
0
3
2 8



(That is, give examples of matrices which are row equivalent to this matrix).




1






2




In each of the following parts determine whether the two given matrices are row equivalent. (We discussed how such a question can be solved in class.



Examples will be given in the next recitation.)

i.
(
3


1
) and (
4
8
)








(
1


3








1
2




)


ii.


1
2
2
) and (
2
2
5




0
1
1
1


1




0
3
1


1
iii.


0


0
3
and
0
1
0
3


@


1


1
1
A




@
0
1
2
A




2


2
8




1
1
1
Prove the following statements.

Let A 2 Mm n(R). If an echelon form of A has a row of zeroes then there exists b 2 Rm such that (Ajb) has no solution.



If m n and A 2 Mm n(R) then there exists b 2 Rm such that (Ajb) has no solution.



If A 2 Mn(R) is a square n n matrix such that the homogenous system (Aj0) has in nity many solutions, then there exists b 2 Rn such that (Ajb) has no solution.



Let A 2 Mn(R) be a square n n matrix. Prove that the following two statements are equivalent, that is, prove that a ) b and b ) a (one can also say that "a is true if and only if b is true").



The homogeneous system (Aj0) has exactly one solution.



For every b 2 Rn the linear system (Ajb) has a solution.



The following statements are false. Prove that they are false by providing a counterexample in each case (you may choose the numbers m and n to be whatever is convenient, try to work with small numbers).



If A 2 Mm n(R) is a matrix such that the homogenous system (Aj0) has in nity many solutions, then there exists b 2 Rn such that (Ajb) has no solution. (Note that by question (4), we know that this statement is in fact true if A is a square matrix).



Let A; B 2 Mm n(R) and b 2 Rm. If A and B are row equivalent then (Ajb) and (Bjb) have the same amount of solutions.



If A; B 2 Mm n(R) are row equivalent then B can be obtained from A by performing column operations (that is, by performing a sequence of operations of the form 'swapping two columns', 'multiplying a column by a scalar di erent from zero', 'adding to a column another column multiplied by a scalar').






3




Let A 2 Mm n(R) and b 2 Rm. If u; v 2 Sol(Ajb) then u + v 2 Sol(Ajb).



Let A 2 Mm n(R) and b 2 Rm. If u 2 Sol(Ajb) and t 2 R then tu 2 Sol(Ajb).