- 25.25.1: Let N be a positive integer. Explain why if N is at least ten billi...
- 25.25.2: How large a group of people do we need to consider to be certain th...
- 25.25.3: How large a group of people do we need to consider to be certain th...
- 25.25.4: In any typical large city, there are (at least) two women with exac...
- 25.25.5: Let .a1; a2; a3; a4; a5/ be a sequence of five distinct integers. W...
- 25.25.6: Two Social Security numbers (see Exercise 8.12) match zeros if a di...
- 25.25.7: Given a set of seven distinct positive integers, prove that there i...
- 25.25.8: The squares of an 8 8 chess board are colored black or white. For t...
- 25.25.9: Consider a square whose side has length one. Suppose we select five...
- 25.25.10: Show that Proposition 25.2 is best possible by finding four lattice...
- 25.25.11: Find and prove a generalization of Proposition 25.2 to three dimens...
- 25.25.12: Find a sequence of nine distinct integers that does not contain a m...
- 25.25.13: Let a1; a2; a3; : : : ; a1001 be a sequence of integers. Prove that...
- 25.25.14: Write a computer program that takes as its input a sequence of dist...
- 25.25.15: Ten points are placed in the plane with no two on the same horizont...
- 25.25.16: Let f W N ! Z by f .n/ D ( n=2 if n is even and .n C 1/=2 if n is o...
- 25.25.17: Let E denote the set of even integers. Find a bijection between E a...
- 25.25.18: Let A be a nonempty set. Prove that if f W 2 A ! A then f is not on...
- 25.25.19: In this problem we show that there are more real numbers than there...
Solutions for Chapter 25: The Pigeonhole Principle
Full solutions for Mathematics: A Discrete Introduction | 3rd Edition
Basis for V.
Independent vectors VI, ... , v d whose linear combinations give each vector in V as v = CIVI + ... + CdVd. V has many bases, each basis gives unique c's. A vector space has many bases!
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.
Remove row i and column j; multiply the determinant by (-I)i + j •
Column space C (A) =
space of all combinations of the columns of A.
Complete solution x = x p + Xn to Ax = b.
(Particular x p) + (x n in nullspace).
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.
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.
A(B + C) = AB + AC. Add then multiply, or mUltiply then add.
Exponential eAt = I + At + (At)2 12! + ...
has derivative AeAt; eAt u(O) solves u' = Au.
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.
Nullspace N (A)
= All solutions to Ax = O. Dimension n - r = (# columns) - rank.
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 •
Positive definite matrix A.
Symmetric matrix with positive eigenvalues and positive pivots. Definition: x T Ax > 0 unless x = O. Then A = LDLT with diag(D» O.
Projection p = a(aTblaTa) onto the line through a.
P = aaT laTa has rank l.
Rank one matrix A = uvT f=. O.
Column and row spaces = lines cu and cv.
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).
Simplex method for linear programming.
The minimum cost vector x * is found by moving from comer to lower cost comer along the edges of the feasible set (where the constraints Ax = b and x > 0 are satisfied). Minimum cost at a comer!
Skew-symmetric matrix K.
The transpose is -K, since Kij = -Kji. Eigenvalues are pure imaginary, eigenvectors are orthogonal, eKt is an orthogonal matrix.
If x gives the movements of the nodes, K x gives the internal forces. K = ATe A where C has spring constants from Hooke's Law and Ax = stretching.