 8.5.1E: Each of the following is a relation on {0, 1, 2, 3}. Draw directed ...
 8.5.2E: Let P be the set of all people in the world and define a relation R...
 8.5.3E: Let S be the set of all strings of a’s and b’s. Define a relation R...
 8.5.4E: Let R be the “less than” relation on the set R of all real numbers:...
 8.5.5E: Let R be the set of all real numbers and define a relation R on R ×...
 8.5.6E: Let P be the set of all people who have ever lived and define a rel...
 8.5.7E: Define a relation R on the set Z of all integers as follows: For al...
 8.5.8E: Define a relation R on the set Z of all integers as follows: For al...
 8.5.9E: Define a relation R on the set of all real numbers R as follows: Fo...
 8.5.10E: Suppose R and S are antisymmetric relations on a set A. Must R ? S ...
 8.5.11E: Let A = {a, b}, and suppose A has the partial order relation R wher...
 8.5.12E: Prove Theorem 8.5.1Reference:
 8.5.13E: Let A = {a, b}. Describe all partial order relations on A.
 8.5.14E: Let A = {a, b, c}.a. Describe all partial order relations on A for ...
 8.5.15E: Suppose a relation R on a set A is reflexive, symmetric, transitive...
 8.5.16E: Consider the “divides” relation on each of the following sets A. Dr...
 8.5.17E: Consider the “subset” relation onP(S) for each of the following set...
 8.5.18E: Let S = {0, 1} and consider the partial order relation R defined on...
 8.5.19E: Let S = {0, 1} and consider the partial order relation R defined on...
 8.5.20E: Let S = {0, 1} and consider the partial order relation R defined on...
 8.5.21E: Consider the “divides” relation defined on the set A={1, 2, 22, 23,...
 8.5.22E: In 22–29, find all greatest, least, maximal, and minimal elements f...
 8.5.23E: In 22–29, find all greatest, least, maximal, and minimal elements f...
 8.5.24E: In 22–29, find all greatest, least, maximal, and minimal elements f...
 8.5.25E: In 22–29, find all greatest, least, maximal, and minimal elements f...
 8.5.26E: In 22–29, find all greatest, least, maximal, and minimal elements f...
 8.5.27E: In 22–29, find all greatest, least, maximal, and minimal elements f...
 8.5.28E: In 22–29, find all greatest, least, maximal, and minimal elements f...
 8.5.29E: In 22–29, find all greatest, least, maximal, and minimal elements f...
 8.5.30E: Each of the following sets is partially ordered with respect to the...
 8.5.31E: Let A = {a, b, c, d}, and let R be the relationR = {(a, a), (b, b),...
 8.5.32E: Let A = {a, b, c, d}, and let R be the relationR = {(a, a), (b, b),...
 8.5.33E: Consider the set A = {12, 24, 48, 3, 9} ordered by the “divides” re...
 8.5.34E: Suppose that R is a partial order relation on a set A and that B is...
 8.5.35E: The set P({w, x, y, z}) is partially ordered with respect to the “s...
 8.5.36E: The set A = {2, 4, 3, 6, 12, 18, 24} is partially ordered with resp...
 8.5.37E: Find a chain of length 2 for the relation defined in exercise 19.Re...
 8.5.38E: Prove that a partially ordered set is totally ordered if, and only ...
 8.5.39E: Suppose that A is a totally ordered set. Use mathematical induction...
 8.5.40E: Prove that a nonempty finite partially ordered set hasa. at least o...
 8.5.41E: Prove that a finite partially ordered set hasa. at most one greates...
 8.5.42E: Draw a Hasse diagram for a partially ordered set that has two maxim...
 8.5.43E: Draw a Hasse diagram for a partially ordered set that has three max...
 8.5.44E: Use the algorithm given in the text to find a topological sorting f...
 8.5.45E: Use the algorithm given in the text to find a topological sorting f...
 8.5.46E: Use the algorithm given in the text to find a topological sorting f...
 8.5.47E: Use the algorithm given in the text to find a topological sorting f...
 8.5.48E: Use the algorithm given in the text to find a topological sorting f...
 8.5.49E: Refer to the prerequisite structure shown in Figure 8.5.1.a. Find a...
 8.5.50E: A set S of jobs can be ordered by writing x y to mean that either x...
 8.5.51E: Suppose the tasks described in Example 8.5.12 require the following...
Solutions for Chapter 8.5: Discrete Mathematics with Applications 4th Edition
Full solutions for Discrete Mathematics with Applications  4th Edition
ISBN: 9780495391326
Solutions for Chapter 8.5
Get Full SolutionsDiscrete Mathematics with Applications was written by Sieva Kozinsky and is associated to the ISBN: 9780495391326. Chapter 8.5 includes 51 full stepbystep solutions. This expansive textbook survival guide covers the following chapters and their solutions. This textbook survival guide was created for the textbook: Discrete Mathematics with Applications , edition: 4th. Since 51 problems in chapter 8.5 have been answered, more than 24940 students have viewed full stepbystep solutions from this chapter.

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

Augmented matrix [A b].
Ax = b is solvable when b is in the column space of A; then [A b] has the same rank as A. Elimination on [A b] keeps equations correct.

Big formula for n by n determinants.
Det(A) is a sum of n! terms. For each term: Multiply one entry from each row and column of A: rows in order 1, ... , nand column order given by a permutation P. Each of the n! P 's has a + or  sign.

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.

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

Exponential eAt = I + At + (At)2 12! + ...
has derivative AeAt; eAt u(O) solves u' = Au.

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.

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.

Hilbert matrix hilb(n).
Entries HU = 1/(i + j 1) = Jd X i 1 xj1dx. Positive definite but extremely small Amin and large condition number: H is illconditioned.

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.

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.

Network.
A directed graph that has constants Cl, ... , Cm associated with the edges.

Norm
IIA II. The ".e 2 norm" of A is the maximum ratio II Ax II/l1x II = O"max· Then II Ax II < IIAllllxll and IIABII < IIAIIIIBII and IIA + BII < IIAII + IIBII. Frobenius norm IIAII} = L La~. The.e 1 and.e oo norms are largest column and row sums of laij I.

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 •

Pivot.
The diagonal entry (first nonzero) at the time when a row is used in elimination.

Rayleigh quotient q (x) = X T Ax I x T x for symmetric A: Amin < q (x) < Amax.
Those extremes are reached at the eigenvectors x for Amin(A) and Amax(A).

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.

Schwarz inequality
Iv·wl < IIvll IIwll.Then IvTAwl2 < (vT Av)(wT Aw) for pos def A.

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.