 8.1.8.1.1: List the ordered pairs in the relation R from A = {O, 1 , 2, 3 , 4}...
 8.1.8.1.2: a) List all the ordered pairs in the relation R = {(a, b) I a divid...
 8.1.8.1.3: For each of these relations on the set { I , 2, 3, 4}, decide wheth...
 8.1.8.1.4: Determine whether the relation R on the set of all people is reflex...
 8.1.8.1.5: Determine whether the relation R on the set of all Web pages is ref...
 8.1.8.1.6: Determine whether the relation R on the set of all real numbers is ...
 8.1.8.1.7: Determine whether the relation R on the set of all integers is refl...
 8.1.8.1.8: Give an example of a relation on a set that is a) symmetric and ant...
 8.1.8.1.9: Which relations in Exercise 3 are irreflexive?
 8.1.8.1.10: Which relations in Exercise 4 are irreflexive?
 8.1.8.1.11: Which relations in Exercise 5 are irreflexive?
 8.1.8.1.12: Which relations in Exercise 6 are irreflexive?
 8.1.8.1.13: Can a relation on a set be neither reflexive nor irreflexive?
 8.1.8.1.14: Use quantifiers to express what it means for a relation to be irref...
 8.1.8.1.15: Give an example of an irreflexive relation on the set of all people.
 8.1.8.1.16: Which relations in Exercise 3 are asymmetric?
 8.1.8.1.17: Which relations in Exercise 4 are asymmetric?
 8.1.8.1.18: Which relations in Exercise 5 are asymmetric?
 8.1.8.1.19: Which relations in Exercise 6 are asymmetric?
 8.1.8.1.20: Must an asymmetric relation also be anti symmetric? Must an anti sy...
 8.1.8.1.21: Use quantifiers to express what it means for a relation to be asymm...
 8.1.8.1.22: Give an example of an asymmetric relation on the set of all people.
 8.1.8.1.23: How many different relations are there from a set with m elements t...
 8.1.8.1.24: Let R be the relation R = {(a, b) I a < b} on the set of integers. ...
 8.1.8.1.25: Let R be the relation R = {(a, b) I a divides b} on the set of posi...
 8.1.8.1.26: Let R be the relation on the set of all states in the United States...
 8.1.8.1.27: Suppose that the function f from A to B is a onetoone corresponden...
 8.1.8.1.28: Let RI = {(I, 2), (2, 3), (3, 4)} and R2 = {(I, 1), (1,2), (2, 1 ),...
 8.1.8.1.29: Let A be the set of students at your school and B the set of books ...
 8.1.8.1.30: Let R be the relation {(I, 2), (1, 3), (2, 3), (2, 4), (3, I)}, and...
 8.1.8.1.31: Let R be the relation on the set of people consisting of pairs ( a,...
 8.1.8.1.32: Find a) RI UR3 b) RI U Rs. c) R2 n R4. d) R3 n Rs. e) RI  R2. t) R...
 8.1.8.1.33: Find a) R2 U R4. b) R3 U R6 . c) R3 n R6. d) R4 n R6. e) R3  R6 t)...
 8.1.8.1.34: Find a) R, 0 R,. b) R, 0 R2. c) R, 0 R3. d) R, 0 R4. e) R, 0 R5. f)...
 8.1.8.1.35: Find a) R2 0 R,. b) R2 0 R2. c) R3 0 R5. d) R4 0 R,. e) R5 0 R3. f)...
 8.1.8.1.36: Let R be the parent relation on the set of all people (see Example ...
 8.1.8.1.37: Let R be the relation on the set of people with doctorates such tha...
 8.1.8.1.38: Let R, and R2 be the "divides" and "is a multiple of" relations on ...
 8.1.8.1.39: Let R, and R2 be the "congruent modulo 3" and the "congruent modulo...
 8.1.8.1.40: List the 16 different relations on the set {O, I}.
 8.1.8.1.41: How many of the 16 different relations on {O, I} contain the pair (...
 8.1.8.1.42: Which of the 16 relations on {O, l}, which you listed in Exercise 4...
 8.1.8.1.43: a) How many relations are there on the set {a, b, c, d}? b) How man...
 8.1.8.1.44: Let S be a set with n elements and let a and b be distinct elements...
 8.1.8.1.45: How many relations are there on a set with n elements that are a) s...
 8.1.8.1.46: How many transitive relations are there on a set with n elements if...
 8.1.8.1.47: Find the error in the "proof" of the following "theorem." "Theorem"...
 8.1.8.1.48: Suppose that R and S are reflexive relations on a set A. Prove or d...
 8.1.8.1.49: Show that the relation R on a set A is symmetric if and only if R =...
 8.1.8.1.50: Show that the relation R on a set A is anti symmetric if and only i...
 8.1.8.1.51: Show that the relation R on a set A is reflexive if and only if the...
 8.1.8.1.52: Show that the relation R on a set A is reflexive if and only if the...
 8.1.8.1.53: Let R be a relation that is reflexive and transitive. Prove that R ...
 8.1.8.1.54: Let R be the relation on the set {I, 2, 3, 4, 5} containing the ord...
 8.1.8.1.55: Let R be a reflexive relation on a set A. Show that R n is reflexiv...
 8.1.8.1.56: Let R be a symmetric relation. Show that R n is symmetric for all p...
 8.1.8.1.57: List the ordered pairs in the relation R from A = {O, 1 , 2, 3 , 4}...
Solutions for Chapter 8.1: Relations
Full solutions for Discrete Mathematics and Its Applications  6th Edition
ISBN: 9780073229720
Solutions for Chapter 8.1: Relations
Get Full SolutionsChapter 8.1: Relations includes 57 full stepbystep solutions. Discrete Mathematics and Its Applications was written by and is associated to the ISBN: 9780073229720. Since 57 problems in chapter 8.1: Relations have been answered, more than 38667 students have viewed full stepbystep solutions from this chapter. This expansive textbook survival guide covers the following chapters and their solutions. This textbook survival guide was created for the textbook: Discrete Mathematics and Its Applications, edition: 6.

Change of basis matrix M.
The old basis vectors v j are combinations L mij Wi of the new basis vectors. The coordinates of CI VI + ... + cnvn = dl wI + ... + dn Wn are related by d = M c. (For n = 2 set VI = mll WI +m21 W2, V2 = m12WI +m22w2.)

Column space C (A) =
space of all combinations of the columns of A.

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.

Elimination matrix = Elementary matrix Eij.
The identity matrix with an extra eij in the i, j entry (i # j). Then Eij A subtracts eij times row j of A from row i.

Four Fundamental Subspaces C (A), N (A), C (AT), N (AT).
Use AT for complex A.

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.

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.

Normal equation AT Ax = ATb.
Gives the least squares solution to Ax = b if A has full rank n (independent columns). The equation says that (columns of A)·(b  Ax) = o.

Polar decomposition A = Q H.
Orthogonal Q times positive (semi)definite H.

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.

Random matrix rand(n) or randn(n).
MATLAB creates a matrix with random entries, uniformly distributed on [0 1] for rand and standard normal distribution for randn.

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.

Right inverse A+.
If A has full row rank m, then A+ = AT(AAT)l has AA+ = 1m.

Semidefinite matrix A.
(Positive) semidefinite: all x T Ax > 0, all A > 0; A = any RT R.

Singular matrix A.
A square matrix that has no inverse: det(A) = o.

Singular Value Decomposition
(SVD) A = U:E VT = (orthogonal) ( diag)( orthogonal) First r columns of U and V are orthonormal bases of C (A) and C (AT), AVi = O'iUi with singular value O'i > O. Last columns are orthonormal bases of nullspaces.

Solvable system Ax = b.
The right side b is in the column space of A.

Spectrum of A = the set of eigenvalues {A I, ... , An}.
Spectral radius = max of IAi I.

Symmetric factorizations A = LDLT and A = QAQT.
Signs in A = signs in D.

Triangle inequality II u + v II < II u II + II v II.
For matrix norms II A + B II < II A II + II B II·