×
×

# Solutions for Chapter 9.2: Coding Theory

## Full solutions for Mathematical Structures for Computer Science | 7th Edition

ISBN: 9781429215107

Solutions for Chapter 9.2: Coding Theory

Solutions for Chapter 9.2
4 5 0 354 Reviews
27
1
##### ISBN: 9781429215107

Since 18 problems in chapter 9.2: Coding Theory have been answered, more than 21560 students have viewed full step-by-step solutions from this chapter. This expansive textbook survival guide covers the following chapters and their solutions. Chapter 9.2: Coding Theory includes 18 full step-by-step solutions. This textbook survival guide was created for the textbook: Mathematical Structures for Computer Science, edition: 7. Mathematical Structures for Computer Science was written by and is associated to the ISBN: 9781429215107.

Key Math Terms and definitions covered in this textbook
• Associative Law (AB)C = A(BC).

Parentheses can be removed to leave ABC.

• Column space C (A) =

space of all combinations of the columns of A.

• Diagonalizable matrix A.

Must have n independent eigenvectors (in the columns of S; automatic with n different eigenvalues). Then S-I AS = A = eigenvalue matrix.

• Elimination matrix = Elementary matrix Eij.

The identity matrix with an extra -eij in the i, j entry (i #- j). Then Eij A subtracts eij times row j of A from row i.

• Fourier matrix F.

Entries Fjk = e21Cijk/n give orthogonal columns FT F = nI. Then y = Fe is the (inverse) Discrete Fourier Transform Y j = L cke21Cijk/n.

• Gauss-Jordan method.

Invert A by row operations on [A I] to reach [I A-I].

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

• Hypercube matrix pl.

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

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

• lA-II = l/lAI and IATI = IAI.

The big formula for det(A) has a sum of n! terms, the cofactor formula uses determinants of size n - 1, volume of box = I det( A) I.

• Left inverse A+.

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

• Orthogonal matrix Q.

Square matrix with orthonormal columns, so QT = Q-l. Preserves length and angles, IIQxll = IIxll and (QX)T(Qy) = xTy. AlllAI = 1, with orthogonal eigenvectors. Examples: Rotation, reflection, permutation.

• Orthogonal subspaces.

Every v in V is orthogonal to every w in W.

• Pascal matrix

Ps = pascal(n) = the symmetric matrix with binomial entries (i1~;2). Ps = PL Pu all contain Pascal's triangle with det = 1 (see Pascal in the index).

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

• Row picture of Ax = b.

Each equation gives a plane in Rn; the planes intersect at x.

• Semidefinite matrix A.

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

• Subspace S of V.

Any vector space inside V, including V and Z = {zero vector only}.

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

×