- 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
Upper triangular systems are solved in reverse order Xn to Xl.
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.
A = CTC = (L.J]))(L.J]))T for positive definite A.
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.
Column picture of Ax = b.
The vector b becomes a combination of the columns of A. The system is solvable only when b is in the column space C (A).
Diagonal matrix D.
dij = 0 if i #- j. Block-diagonal: zero outside square blocks Du.
Eigenvalue A and eigenvector x.
Ax = AX with x#-O so det(A - AI) = o.
Inverse matrix A-I.
Square matrix with A-I A = I and AA-l = I. No inverse if det A = 0 and rank(A) < n and Ax = 0 for a nonzero vector x. The inverses of AB and AT are B-1 A-I and (A-I)T. Cofactor formula (A-l)ij = Cji! detA.
Krylov subspace Kj(A, b).
The subspace spanned by b, Ab, ... , Aj-Ib. Numerical methods approximate A -I b by x j with residual b - Ax j in this subspace. A good basis for K j requires only multiplication by A at each step.
Least squares solution X.
The vector x that minimizes the error lie 112 solves AT Ax = ATb. Then e = b - Ax is orthogonal to all columns of A.
Length II x II.
Square root of x T x (Pythagoras in n dimensions).
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.
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.
Polar decomposition A = Q H.
Orthogonal Q times positive (semi)definite H.
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.
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.
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.
Skew-symmetric matrix K.
The transpose is -K, since Kij = -Kji. Eigenvalues are pure imaginary, eigenvectors are orthogonal, eKt is an orthogonal matrix.
Special solutions to As = O.
One free variable is Si = 1, other free variables = o.
Unitary matrix UH = U T = U-I.
Orthonormal columns (complex analog of Q).