 56.56.1: What is the width of a total order?
 56.56.2: Let n be a positive integer. a. How many different (unequal) linear...
 56.56.3: Prove that a minimal element of a total order is a minimum element....
 56.56.4: Suppose f is an isomorphism between posets P and Q, and let x and y...
 56.56.5: Let P and Q be isomorphic posets and let f be an isomorphism. Let x...
 56.56.6: Prove that .N; / and .Z; / are not isomorphic. Note: This exercise ...
 56.56.7: Let .X; / be a totally ordered set. Define a new relation on X X as...
 56.56.8: For a linear order .X; / we say that element x is between elements ...
Solutions for Chapter 56: Linear Orders
Full solutions for Mathematics: A Discrete Introduction  3rd Edition
ISBN: 9780840049421
Solutions for Chapter 56: Linear Orders
Get Full SolutionsMathematics: A Discrete Introduction was written by and is associated to the ISBN: 9780840049421. This expansive textbook survival guide covers the following chapters and their solutions. Chapter 56: Linear Orders includes 8 full stepbystep solutions. Since 8 problems in chapter 56: Linear Orders have been answered, more than 9315 students have viewed full stepbystep solutions from this chapter. This textbook survival guide was created for the textbook: Mathematics: A Discrete Introduction, edition: 3.

CayleyHamilton Theorem.
peA) = det(A  AI) has peA) = zero matrix.

Column space C (A) =
space of all combinations of the columns of A.

Determinant IAI = det(A).
Defined by det I = 1, sign reversal for row exchange, and linearity in each row. Then IAI = 0 when A is singular. Also IABI = IAIIBI and

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

Ellipse (or ellipsoid) x T Ax = 1.
A must be positive definite; the axes of the ellipse are eigenvectors of A, with lengths 1/.JI. (For IIx II = 1 the vectors y = Ax lie on the ellipse IIA1 yll2 = Y T(AAT)1 Y = 1 displayed by eigshow; axis lengths ad

Graph G.
Set of n nodes connected pairwise by m edges. A complete graph has all n(n  1)/2 edges between nodes. A tree has only n  1 edges and no closed loops.

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.

Kronecker product (tensor product) A ® B.
Blocks aij B, eigenvalues Ap(A)Aq(B).

Krylov subspace Kj(A, b).
The subspace spanned by b, Ab, ... , AjIb. 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.

Length II x II.
Square root of x T x (Pythagoras in n dimensions).

Linear transformation T.
Each vector V in the input space transforms to T (v) in the output space, and linearity requires T(cv + dw) = c T(v) + d T(w). Examples: Matrix multiplication A v, differentiation and integration in function space.

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.

Pseudoinverse A+ (MoorePenrose 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).

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 = Q1 = Q.

Singular matrix A.
A square matrix that has no inverse: det(A) = o.

Skewsymmetric matrix K.
The transpose is K, since Kij = Kji. Eigenvalues are pure imaginary, eigenvectors are orthogonal, eKt is an orthogonal matrix.

Spectrum of A = the set of eigenvalues {A I, ... , An}.
Spectral radius = max of IAi I.

Symmetric factorizations A = LDLT and A = QAQT.
Signs in A = signs in D.