 8.1.1: As in Example 8.1.2, the congruence modulo 2 relation E is defined ...
 8.1.2: Prove that for all integers m and n, m n is even if, and only if, b...
 8.1.3: The congruence modulo 3 relation, T , is defined from Z to Z as fol...
 8.1.4: Define a relation P on Z as follows: For all m, n Z, mPn m and n ha...
 8.1.5: Let X = {a, b, c}. Recall that P(X) is the power set of X. Define a...
 8.1.6: Let X = {a, b, c}. Define a relation J on P(X) as follows: For all ...
 8.1.7: Define a relation R on Z as follows: For all integers m and n, mRn ...
 8.1.8: Let A be the set of all strings of as and bs of length 4. Define a ...
 8.1.9: Let A be the set of all strings of 0s, 1s, and 2s of length 4. Defi...
 8.1.10: Let A = {3, 4, 5} and B = {4, 5, 6} and let R be the less than rela...
 8.1.11: Let A = {3, 4, 5} and B = {4, 5, 6} and let S be the divides relati...
 8.1.12: a. Suppose a function F: X Y is onetoone but not onto. Is F1 (the...
 8.1.13: Draw the directed graphs of the relations defined in 1318.
 8.1.14: Draw the directed graphs of the relations defined in 1318.
 8.1.15: Draw the directed graphs of the relations defined in 1318.
 8.1.16: Draw the directed graphs of the relations defined in 1318.
 8.1.17: Draw the directed graphs of the relations defined in 1318.
 8.1.18: Draw the directed graphs of the relations defined in 1318.
 8.1.19: Exercises 1920 refer to unions and intersections of relations. Sinc...
 8.1.20: Exercises 1920 refer to unions and intersections of relations. Sinc...
 8.1.21: Define relations R and S on R as follows: R = {(x, y) R R  x < y} ...
 8.1.22: Define relations R and S on R as follows: R = {(x, y) R R  x 2 + y...
 8.1.23: Define relations R and S on R as follows: R = {(x, y) R R  y = x...
 8.1.24: In Example 8.1.7 the result of the query SELECT PatientID#, Name FR...
Solutions for Chapter 8.1: Relations on Sets
Full solutions for Discrete Mathematics with Applications  4th Edition
ISBN: 9780495391326
Solutions for Chapter 8.1: Relations on Sets
Get Full SolutionsDiscrete Mathematics with Applications was written by Sieva Kozinsky and is associated to the ISBN: 9780495391326. This textbook survival guide was created for the textbook: Discrete Mathematics with Applications , edition: 4th. Since 24 problems in chapter 8.1: Relations on Sets have been answered, more than 24152 students have viewed full stepbystep solutions from this chapter. This expansive textbook survival guide covers the following chapters and their solutions. Chapter 8.1: Relations on Sets includes 24 full stepbystep solutions.

CayleyHamilton Theorem.
peA) = det(A  AI) has peA) = zero matrix.

Characteristic equation det(A  AI) = O.
The n roots are the eigenvalues of A.

Complete solution x = x p + Xn to Ax = b.
(Particular x p) + (x n in nullspace).

Condition number
cond(A) = c(A) = IIAIlIIAIII = amaxlamin. In Ax = b, the relative change Ilox III Ilx II is less than cond(A) times the relative change Ilob III lib II· Condition numbers measure the sensitivity of the output to change in the input.

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.

Ellipse (or ellipsoid) x T Ax = 1.
A must be positive definite; the axes of the ellipse are eigenvectors of A, with lengths 1/.JI. (For IIx II = 1 the vectors y = Ax lie on the ellipse IIA1 yll2 = Y T(AAT)1 Y = 1 displayed by eigshow; axis lengths ad

Graph G.
Set of n nodes connected pairwise by m edges. A complete graph has all n(n  1)/2 edges between nodes. A tree has only n  1 edges and no closed loops.

Hankel matrix H.
Constant along each antidiagonal; hij depends on i + j.

Independent vectors VI, .. " vk.
No combination cl VI + ... + qVk = zero vector unless all ci = O. If the v's are the columns of A, the only solution to Ax = 0 is x = o.

Left inverse A+.
If A has full column rank n, then A+ = (AT A)I AT has A+ A = In.

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

Lucas numbers
Ln = 2,J, 3, 4, ... satisfy Ln = L n l +Ln 2 = A1 +A~, with AI, A2 = (1 ± /5)/2 from the Fibonacci matrix U~]' Compare Lo = 2 with Fo = O.

Matrix multiplication AB.
The i, j entry of AB is (row i of A)·(column j of B) = L aikbkj. By columns: Column j of AB = A times column j of B. By rows: row i of A multiplies B. Columns times rows: AB = sum of (column k)(row k). All these equivalent definitions come from the rule that A B times x equals A times B x .

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

Positive definite matrix A.
Symmetric matrix with positive eigenvalues and positive pivots. Definition: x T Ax > 0 unless x = O. Then A = LDLT with diag(D» O.

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

Row space C (AT) = all combinations of rows of A.
Column vectors by convention.

Wavelets Wjk(t).
Stretch and shift the time axis to create Wjk(t) = woo(2j t  k).