- 5.1.1: Prove Theorem 5.1.1. That is, show that the relation is reflexive, ...
- 5.1.2: Which of the following sets are finite? (a) the set of all grains o...
- 5.1.3: Complete the proof that any two open intervals and are equivalentby...
- 5.1.4: Complete the proof of Lemma 5.1.2(b) by showing that if andare one-...
- 5.1.5: Show that if then (See also Exercise 13, Section 4.1.)
- 5.1.6: Let A and B be sets. Prove that (a) if A is finite, then is finite.
- 5.1.7: Using the methods of this section, prove that if A and B are finite...
- 5.1.8: Prove part (c) of Theorem 5.1.7.
- 5.1.9: (a) Show that for every set A and every object x.(b) Use Theorem 5....
- 5.1.10: Define to be the set of all functions from A to B. Show that if A a...
- 5.1.11: If possible, give an example of each of the following:(a) an infini...
- 5.1.12: Prove that if A is finite and B is infinite, then is infinite.
- 5.1.13: Prove that if and then (Lemma 5.1.8).
- 5.1.14: Complete the proof of Corollary 5.1.10 by showing that if A is fini...
- 5.1.15: Let A be a finite set. Prove that if and then
- 5.1.16: Prove or disprove:(a) If C is an infinite set and then at least one...
- 5.1.17: Prove by induction on n that if and then f is not onto
- 5.1.18: Let A and B be finite sets with Suppose (a) If f is one-to-one, sho...
- 5.1.19: Prove that if the domain of a function is finite, then the range is...
- 5.1.20: Let A and B be finite sets with and let f be a function fromA to B....
- 5.1.21: . Give a proof using the Pigeonhole Principle:(a) The Italian villa...
- 5.1.22: Assign a grade of A (correct), C (partially correct), or F (failure...
Solutions for Chapter 5.1: Equivalent Sets; Finite Sets
Full solutions for A Transition to Advanced Mathematics | 7th Edition
cond(A) = c(A) = IIAIlIIA-III = 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.
S. Permutation with S21 = 1, S32 = 1, ... , finally SIn = 1. Its eigenvalues are the nth roots e2lrik/n of 1; eigenvectors are columns of the Fourier matrix F.
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.
Fast Fourier Transform (FFT).
A factorization of the Fourier matrix Fn into e = log2 n matrices Si times a permutation. Each Si needs only nl2 multiplications, so Fnx and Fn-1c can be computed with ne/2 multiplications. Revolutionary.
Hypercube matrix pl.
Row n + 1 counts corners, edges, faces, ... of a cube in Rn.
Identity matrix I (or In).
Diagonal entries = 1, off-diagonal entries = 0.
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.
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.
Markov matrix M.
All mij > 0 and each column sum is 1. Largest eigenvalue A = 1. If mij > 0, the columns of Mk approach the steady state eigenvector M s = s > O.
Nilpotent matrix N.
Some power of N is the zero matrix, N k = o. The only eigenvalue is A = 0 (repeated n times). Examples: triangular matrices with zero diagonal.
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.
Particular solution x p.
Any solution to Ax = b; often x p has free variables = o.
Projection p = a(aTblaTa) onto the line through a.
P = aaT laTa has rank l.
Pseudoinverse A+ (Moore-Penrose inverse).
The n by m matrix that "inverts" A from column space back to row space, with N(A+) = N(AT). A+ A and AA+ are the projection matrices onto the row space and column space. Rank(A +) = rank(A).
Row space C (AT) = all combinations of rows of A.
Column vectors by convention.
Schur complement S, D - C A -} B.
Appears in block elimination on [~ g ].
Spectral Theorem A = QAQT.
Real symmetric A has real A'S and orthonormal q's.
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.
Vector v in Rn.
Sequence of n real numbers v = (VI, ... , Vn) = point in Rn.
Stretch and shift the time axis to create Wjk(t) = woo(2j t - k).