 8.3.1: Suppose that S = {a, b, c, d, e} and R is a relation on S such that...
 8.3.2: Each of the following partitions of {0, 1, 2, 3, 4} induces a relat...
 8.3.3: In each of 314, the relation R is an equivalence relation on the se...
 8.3.4: In each of 314, the relation R is an equivalence relation on the se...
 8.3.5: In each of 314, the relation R is an equivalence relation on the se...
 8.3.6: In each of 314, the relation R is an equivalence relation on the se...
 8.3.7: In each of 314, the relation R is an equivalence relation on the se...
 8.3.8: In each of 314, the relation R is an equivalence relation on the se...
 8.3.9: In each of 314, the relation R is an equivalence relation on the se...
 8.3.10: In each of 314, the relation R is an equivalence relation on the se...
 8.3.11: In each of 314, the relation R is an equivalence relation on the se...
 8.3.12: In each of 314, the relation R is an equivalence relation on the se...
 8.3.13: In each of 314, the relation R is an equivalence relation on the se...
 8.3.14: In each of 314, the relation R is an equivalence relation on the se...
 8.3.15: Determine which of the following congruence relations are true and ...
 8.3.16: a. Let R be the relation of congruence modulo 3. Which of the follo...
 8.3.17: a. Prove that for all integers m and n, m n (mod 3) if, and only if...
 8.3.18: a. Give an example of two sets that are distinct but not disjoint. ...
 8.3.19: In 1931, (1) prove that the relation is an equivalence relation, an...
 8.3.20: In 1931, (1) prove that the relation is an equivalence relation, an...
 8.3.21: In 1931, (1) prove that the relation is an equivalence relation, an...
 8.3.22: In 1931, (1) prove that the relation is an equivalence relation, an...
 8.3.23: In 1931, (1) prove that the relation is an equivalence relation, an...
 8.3.24: In 1931, (1) prove that the relation is an equivalence relation, an...
 8.3.25: In 1931, (1) prove that the relation is an equivalence relation, an...
 8.3.26: In 1931, (1) prove that the relation is an equivalence relation, an...
 8.3.27: In 1931, (1) prove that the relation is an equivalence relation, an...
 8.3.28: In 1931, (1) prove that the relation is an equivalence relation, an...
 8.3.29: In 1931, (1) prove that the relation is an equivalence relation, an...
 8.3.30: In 1931, (1) prove that the relation is an equivalence relation, an...
 8.3.31: In 1931, (1) prove that the relation is an equivalence relation, an...
 8.3.32: Let A be the set of all straight lines in the Cartesian plane. Defi...
 8.3.33: Let A be the set of points in the rectangle with x and y coordinate...
 8.3.34: The documentation for the computer language Java recommends that wh...
 8.3.35: Find an additional representative circuit for the input/output tabl...
 8.3.36: Let R be an equivalence relation on a set A. Prove each of the stat...
 8.3.37: Let R be an equivalence relation on a set A. Prove each of the stat...
 8.3.38: Let R be an equivalence relation on a set A. Prove each of the stat...
 8.3.39: Let R be an equivalence relation on a set A. Prove each of the stat...
 8.3.40: Let R be an equivalence relation on a set A. Prove each of the stat...
 8.3.41: Let R be an equivalence relation on a set A. Prove each of the stat...
 8.3.42: Let R be the relation defined in Example 8.3.12. a. Prove that R is...
 8.3.43: In Example 8.3.12, define operations of addition (+) and multiplica...
 8.3.44: Let A = Z+ Z+. Define a relation R on A as follows: For all (a, b) ...
 8.3.45: The following argument claims to prove that the requirement that an...
 8.3.46: Let R be a relation on a set A and suppose R is symmetric and trans...
 8.3.47: Refer to the quote at the beginning of this section to answer the f...
Solutions for Chapter 8.3: Equivalence Relations
Full solutions for Discrete Mathematics with Applications  4th Edition
ISBN: 9780495391326
Solutions for Chapter 8.3: Equivalence Relations
Get Full SolutionsDiscrete Mathematics with Applications was written by and is associated to the ISBN: 9780495391326. This expansive textbook survival guide covers the following chapters and their solutions. Chapter 8.3: Equivalence Relations includes 47 full stepbystep solutions. Since 47 problems in chapter 8.3: Equivalence Relations have been answered, more than 44999 students have viewed full stepbystep solutions from this chapter. This textbook survival guide was created for the textbook: Discrete Mathematics with Applications , edition: 4.

Basis for V.
Independent vectors VI, ... , v d whose linear combinations give each vector in V as v = CIVI + ... + CdVd. V has many bases, each basis gives unique c's. A vector space has many bases!

Block matrix.
A matrix can be partitioned into matrix blocks, by cuts between rows and/or between columns. Block multiplication ofAB is allowed if the block shapes permit.

Column picture of Ax = b.
The vector b becomes a combination of the columns of A. The system is solvable only when b is in the column space C (A).

Companion matrix.
Put CI, ... ,Cn in row n and put n  1 ones just above the main diagonal. Then det(A  AI) = ±(CI + c2A + C3A 2 + .•. + cnA nl  An).

Diagonal matrix D.
dij = 0 if i # j. Blockdiagonal: zero outside square blocks Du.

Dot product = Inner product x T y = XI Y 1 + ... + Xn Yn.
Complex dot product is x T Y . Perpendicular vectors have x T y = O. (AB)ij = (row i of A)T(column j of B).

Eigenvalue A and eigenvector x.
Ax = AX with x#O so det(A  AI) = o.

Elimination.
A sequence of row operations that reduces A to an upper triangular U or to the reduced form R = rref(A). Then A = LU with multipliers eO in L, or P A = L U with row exchanges in P, or E A = R with an invertible E.

Full row rank r = m.
Independent rows, at least one solution to Ax = b, column space is all of Rm. Full rank means full column rank or full row rank.

Fundamental Theorem.
The nullspace N (A) and row space C (AT) are orthogonal complements in Rn(perpendicular from Ax = 0 with dimensions rand n  r). Applied to AT, the column space C(A) is the orthogonal complement of N(AT) in Rm.

GramSchmidt orthogonalization A = QR.
Independent columns in A, orthonormal columns in Q. Each column q j of Q is a combination of the first j columns of A (and conversely, so R is upper triangular). Convention: diag(R) > o.

Jordan form 1 = M 1 AM.
If A has s independent eigenvectors, its "generalized" eigenvector matrix M gives 1 = diag(lt, ... , 1s). The block his Akh +Nk where Nk has 1 's on diagonall. Each block has one eigenvalue Ak and one eigenvector.

Left nullspace N (AT).
Nullspace of AT = "left nullspace" of A because y T A = OT.

Multiplicities AM and G M.
The algebraic multiplicity A M of A is the number of times A appears as a root of det(A  AI) = O. The geometric multiplicity GM is the number of independent eigenvectors for A (= dimension of the eigenspace).

Multiplier eij.
The pivot row j is multiplied by eij and subtracted from row i to eliminate the i, j entry: eij = (entry to eliminate) / (jth pivot).

Outer product uv T
= column times row = rank one matrix.

Plane (or hyperplane) in Rn.
Vectors x with aT x = O. Plane is perpendicular to a =1= O.

Reflection matrix (Householder) Q = I 2uuT.
Unit vector u is reflected to Qu = u. All x intheplanemirroruTx = o have Qx = x. Notice QT = Q1 = Q.

Rotation matrix
R = [~ CS ] rotates the plane by () and R 1 = RT rotates back by (). Eigenvalues are eiO and eiO , eigenvectors are (1, ±i). c, s = cos (), sin ().

Standard basis for Rn.
Columns of n by n identity matrix (written i ,j ,k in R3).