- 10.3.1E: Find real numbers a, b, and c such that the following are true.
- 10.3.2E: Find the adjacency matrices for the following directed graphs.
- 10.3.3E: Find directed graphs that have the following adjacency matrices:
- 10.3.4E: Find adjacency matrices for the following (undirected) graphs. c. K...
- 10.3.5E: Find graphs that have the following adjacency matrices.
- 10.3.6E: The following are adjacency matrices for graphs. In each case deter...
- 10.3.7E: Suppose that for all positive integers i , all the entries in the i...
- 10.3.8E: Find each of the following products.
- 10.3.9E: Find each of the following products.
- 10.3.10E: For each of the following, determine whether the indicated product ...
- 10.3.11E: Give an example different from that in the text to show that matrix...
- 10.3.12E: Let O denote the matrix Find 2 × 2 matrices A and B such that A ? O...
- 10.3.13E: Let O denote the matrix Find 2 × 2 matrices A and B such that A ? B...
- 10.3.14E: In 14–18 assume the entries of all matrices are real numbers.Prove ...
- 10.3.15E: In 14–18 assume the entries of all matrices are real numbers.Prove ...
- 10.3.16E: In 14–18 assume the entries of all matrices are real numbers.Prove ...
- 10.3.17E: In 14–18 assume the entries of all matrices are real numbers.Use ma...
- 10.3.18E: In 14–18 assume the entries of all matrices are real numbers.Use ma...
- 10.3.19E: b. Let G be the graph with vertices v1, v2, and v3 and with A as it...
- 10.3.20E: The following is an adjacency matrix for a graph: Answer the follow...
- 10.3.21E: Let A be the adjacent matrix for K3, the complete graph on three ve...
- 10.3.22E: a. Draw a graph that has as its adjacency matrix. Is this graph bip...
- 10.3.23E: a. Let G be a graphwith n vertices, and let v and w be distinct ver...
Solutions for Chapter 10.3: Discrete Mathematics with Applications 4th Edition
Full solutions for Discrete Mathematics with Applications | 4th Edition
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).
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.)
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.
z = a - ib for any complex number z = a + ib. Then zz = Iz12.
Cramer's Rule for Ax = b.
B j has b replacing column j of A; x j = det B j I det A
Diagonal matrix D.
dij = 0 if i #- j. Block-diagonal: zero outside square blocks Du.
A = S-1 AS. A = eigenvalue matrix and S = eigenvector matrix of A. A must have n independent eigenvectors to make S invertible. All Ak = SA k S-I.
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).
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.
Exponential eAt = I + At + (At)2 12! + ...
has derivative AeAt; eAt u(O) solves u' = Au.
0,1,1,2,3,5, ... satisfy Fn = Fn-l + Fn- 2 = (A7 -A~)I()q -A2). Growth rate Al = (1 + .J5) 12 is the largest eigenvalue of the Fibonacci matrix [ } A].
Hankel matrix H.
Constant along each antidiagonal; hij depends on i + j.
Hilbert matrix hilb(n).
Entries HU = 1/(i + j -1) = Jd X i- 1 xj-1dx. Positive definite but extremely small Amin and large condition number: H is ill-conditioned.
Hypercube matrix pl.
Row n + 1 counts corners, edges, faces, ... of a cube in Rn.
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.
= Xl (column 1) + ... + xn(column n) = combination of columns.
If N NT = NT N, then N has orthonormal (complex) eigenvectors.
Reflection matrix (Householder) Q = I -2uuT.
Unit vector u is reflected to Qu = -u. All x intheplanemirroruTx = o have Qx = x. Notice QT = Q-1 = Q.
Iv·wl < IIvll IIwll.Then IvTAwl2 < (vT Av)(wT Aw) for pos def A.
Vandermonde matrix V.
V c = b gives coefficients of p(x) = Co + ... + Cn_IXn- 1 with P(Xi) = bi. Vij = (Xi)j-I and det V = product of (Xk - Xi) for k > i.