 9.4.1E: Let R be the relation on the set {0,1, 2, 3} containing the ordered...
 9.4.2E: Let R be the relation {(a, b) a ? b} on the set of integers. What ...
 9.4.3E: Let R be the relation {(a, b)  a divides b} on the set of integers...
 9.4.4E: How can the directed graph representing the reflexive closure of a ...
 9.4.5E: In Exercises 5 draw the directed graph of the reflexive closure of ...
 9.4.6E: In Exercises 6 draw the directed graph of the reflexive closure of ...
 9.4.7E: In Exercises 7 draw the directed graph of the reflexive closure of ...
 9.4.8E: How can the directed graph representing the symmetric closure of a ...
 9.4.10E: Find the smallest relation containing the relation in Example 2 tha...
 9.4.11E: Find the directed graph of the smallest relation that is both refle...
 9.4.9E: Find the directed graphs of the symmetric closures of the relations...
 9.4.12E: Suppose that the relation R on the finite set A is represented by t...
 9.4.13E: Suppose that the relation R on the finite set A is represented by t...
 9.4.14E: Show that the closure of a relation R with respect to a property P,...
 9.4.15E: When is it possible to define the "irreflexive closure" of a relati...
 9.4.17E: Find all circuits of length three in the directed graph in Exercise...
 9.4.18E: Determine whether there is a path in the directed graph in Exercise...
 9.4.16E: Determine whether these sequences of vertices are paths in this dir...
 9.4.19E: Let R be the relation on the set {1, 2, 3, 4, 5} containing the ord...
 9.4.20E: Let R be the relation that contains the pair (a, b) if a and b are ...
 9.4.21E: Let R be the relation on the set of all students containing the ord...
 9.4.22E: Suppose that the relation R is reflexive. Show that R * is reflexive.
 9.4.24E: Suppose that the relation R is irreflexive, Is the relation R 2 nec...
 9.4.23E: Suppose that the relation R is symmetric, Show that R * is symmetric.
 9.4.25E: Use Algorithm 1 to find the transitive closures of these relations ...
 9.4.26E: Use Algorithm 1 to find the transitive closures of these relations ...
 9.4.27E: Use Warshall's algorithm to find the transitive closures of the rel...
 9.4.28E: Use Warshall's algorithm to find the transitive closures of the rel...
 9.4.29E: Find the smallest relation containing the relation {(1,2), (1,4), (...
 9.4.30E: Finish the proof of the case when a ? b in Lemma 1.
 9.4.31E: Algorithms have been devised that use 0(n2.8) bit operations to com...
 9.4.32E: Devise an algorithm using the concept of interior vertices in a pat...
 9.4.34E: Adapt Warshall's algorithm to find the reflexiv e closure of the tr...
 9.4.33E: Adapt Algorithm 1 to find the reflexive closure of the transitive c...
 9.4.35E: that the closure with respect to the property P of the relation R =...
Solutions for Chapter 9.4: Discrete Mathematics and Its Applications 7th Edition
Full solutions for Discrete Mathematics and Its Applications  7th Edition
ISBN: 9780073383095
Solutions for Chapter 9.4
Get Full SolutionsSince 35 problems in chapter 9.4 have been answered, more than 198965 students have viewed full stepbystep solutions from this chapter. This textbook survival guide was created for the textbook: Discrete Mathematics and Its Applications, edition: 7. Discrete Mathematics and Its Applications was written by and is associated to the ISBN: 9780073383095. This expansive textbook survival guide covers the following chapters and their solutions. Chapter 9.4 includes 35 full stepbystep solutions.

Commuting matrices AB = BA.
If diagonalizable, they share n eigenvectors.

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

Covariance matrix:E.
When random variables Xi have mean = average value = 0, their covariances "'£ ij are the averages of XiX j. With means Xi, the matrix :E = mean of (x  x) (x  x) T is positive (semi)definite; :E is diagonal if the Xi are independent.

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

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

GaussJordan method.
Invert A by row operations on [A I] to reach [I AI].

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.

Hessenberg matrix H.
Triangular matrix with one extra nonzero adjacent diagonal.

Identity matrix I (or In).
Diagonal entries = 1, offdiagonal entries = 0.

Kirchhoff's Laws.
Current Law: net current (in minus out) is zero at each node. Voltage Law: Potential differences (voltage drops) add to zero around any closed loop.

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 .

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.

Orthogonal matrix Q.
Square matrix with orthonormal columns, so QT = Ql. Preserves length and angles, IIQxll = IIxll and (QX)T(Qy) = xTy. AlllAI = 1, with orthogonal eigenvectors. Examples: Rotation, reflection, permutation.

Orthogonal subspaces.
Every v in V is orthogonal to every w in W.

Orthonormal vectors q 1 , ... , q n·
Dot products are q T q j = 0 if i =1= j and q T q i = 1. The matrix Q with these orthonormal columns has Q T Q = I. If m = n then Q T = Q 1 and q 1 ' ... , q n is an orthonormal basis for Rn : every v = L (v T q j )q j •

Saddle point of I(x}, ... ,xn ).
A point where the first derivatives of I are zero and the second derivative matrix (a2 II aXi ax j = Hessian matrix) is indefinite.

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.

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

Vandermonde matrix V.
V c = b gives coefficients of p(x) = Co + ... + Cn_IXn 1 with P(Xi) = bi. Vij = (Xi)jI and det V = product of (Xk  Xi) for k > i.

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