 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 Sieva Kozinsky 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 25018 students have viewed full stepbystep solutions from this chapter. This textbook survival guide was created for the textbook: Discrete Mathematics with Applications , edition: 4th.

Adjacency matrix of a graph.
Square matrix with aij = 1 when there is an edge from node i to node j; otherwise aij = O. A = AT when edges go both ways (undirected). Adjacency matrix of a graph. Square matrix with aij = 1 when there is an edge from node i to node j; otherwise aij = O. A = AT when edges go both ways (undirected).

Circulant matrix C.
Constant diagonals wrap around as in cyclic shift S. Every circulant is Col + CIS + ... + Cn_lSn  l . Cx = convolution c * x. Eigenvectors in F.

Diagonalizable matrix A.
Must have n independent eigenvectors (in the columns of S; automatic with n different eigenvalues). Then SI AS = A = eigenvalue matrix.

Diagonalization
A = S1 AS. A = eigenvalue matrix and S = eigenvector matrix of A. A must have n independent eigenvectors to make S invertible. All Ak = SA k SI.

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).

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.

Free columns of A.
Columns without pivots; these are combinations of earlier columns.

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).

Normal matrix.
If N NT = NT N, then N has orthonormal (complex) eigenvectors.

Particular solution x p.
Any solution to Ax = b; often x p has free variables = o.

Pascal matrix
Ps = pascal(n) = the symmetric matrix with binomial entries (i1~;2). Ps = PL Pu all contain Pascal's triangle with det = 1 (see Pascal in the index).

Pseudoinverse A+ (MoorePenrose inverse).
The n by m matrix that "inverts" A from column space back to row space, with N(A+) = N(AT). A+ A and AA+ are the projection matrices onto the row space and column space. Rank(A +) = rank(A).

Reduced row echelon form R = rref(A).
Pivots = 1; zeros above and below pivots; the r nonzero rows of R give a basis for the row space of A.

Subspace S of V.
Any vector space inside V, including V and Z = {zero vector only}.

Sum V + W of subs paces.
Space of all (v in V) + (w in W). Direct sum: V n W = to}.

Transpose matrix AT.
Entries AL = Ajj. AT is n by In, AT A is square, symmetric, positive semidefinite. The transposes of AB and AI are BT AT and (AT)I.

Unitary matrix UH = U T = UI.
Orthonormal columns (complex analog of Q).

Vector addition.
v + w = (VI + WI, ... , Vn + Wn ) = diagonal of parallelogram.

Volume of box.
The rows (or the columns) of A generate a box with volume I det(A) I.