 5.5.1E: Prove that the program segmenty:= 1z:= x + yis correct with respect...
 5.5.2E: Verify that the program segmentif x < 0 then x:= 0is correct with r...
 5.5.3E: Verify that the program segmentx:= 2z:= x + yif y > 0 thenz:=z+1els...
 5.5.4E: Verify that the program segmentif x<y thenmin:= xelsemin:= yis corr...
 5.5.5E: Devise a rule of inference for verification of partial correctness ...
 5.5.7E: Use a loop invariant to prove that the following program segment fo...
 5.5.8E: Prove that the iterative program for finding fn given in Section 5....
 5.5.9E: Provide all the details in the proof of correctness given in Exampl...
 5.5.11E: Suppose that both the program assertion p{S}q0 and the conditional ...
 5.5.10E: Suppose that both the conditional statement p0 ? p1 and the program...
 5.5.12E: This program computes quotients and remainders.r:= aq:= 0whiler? dr...
 5.5.13E: Use a loop invariant to verify that the Euclidean algorithm (Algori...
Solutions for Chapter 5.5: Discrete Mathematics and Its Applications 7th Edition
Full solutions for Discrete Mathematics and Its Applications  7th Edition
ISBN: 9780073383095
Solutions for Chapter 5.5
Get Full SolutionsSince 12 problems in chapter 5.5 have been answered, more than 198724 students have viewed full stepbystep solutions from this chapter. This expansive textbook survival guide covers the following chapters and their solutions. Chapter 5.5 includes 12 full stepbystep solutions. This textbook survival guide was created for the textbook: Discrete Mathematics and Its Applications, edition: 7. Discrete Mathematics and Its Applications was written by and is associated to the ISBN: 9780073383095.

Affine transformation
Tv = Av + Vo = linear transformation plus shift.

Conjugate Gradient Method.
A sequence of steps (end of Chapter 9) to solve positive definite Ax = b by minimizing !x T Ax  x Tb over growing Krylov subspaces.

Echelon matrix U.
The first nonzero entry (the pivot) in each row comes in a later column than the pivot in the previous row. All zero rows come last.

Full column rank r = n.
Independent columns, N(A) = {O}, no free variables.

Full row rank r = m.
Independent rows, at least one solution to Ax = b, column space is all of Rm. Full rank means full column rank or full row rank.

Hypercube matrix pl.
Row n + 1 counts corners, edges, faces, ... of a cube in Rn.

Independent vectors VI, .. " vk.
No combination cl VI + ... + qVk = zero vector unless all ci = O. If the v's are the columns of A, the only solution to Ax = 0 is x = o.

Left inverse A+.
If A has full column rank n, then A+ = (AT A)I AT has A+ A = In.

Left nullspace N (AT).
Nullspace of AT = "left nullspace" of A because y T A = OT.

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.

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

Permutation matrix P.
There are n! orders of 1, ... , n. The n! P 's have the rows of I in those orders. P A puts the rows of A in the same order. P is even or odd (det P = 1 or 1) based on the number of row exchanges to reach I.

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

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.

Rotation matrix
R = [~ CS ] rotates the plane by () and R 1 = RT rotates back by (). Eigenvalues are eiO and eiO , eigenvectors are (1, ±i). c, s = cos (), sin ().

Semidefinite matrix A.
(Positive) semidefinite: all x T Ax > 0, all A > 0; A = any RT R.

Standard basis for Rn.
Columns of n by n identity matrix (written i ,j ,k in R3).

Trace of A
= sum of diagonal entries = sum of eigenvalues of A. Tr AB = Tr BA.

Vector addition.
v + w = (VI + WI, ... , Vn + Wn ) = diagonal of parallelogram.