 40.40.1: At the beginning of this section we considered the following operat...
 40.40.2: Let ? be an operation defined on the real numbers R by x ? y D x C ...
 40.40.3: Consider the operation ? for real numbers x and y defined by x ? y ...
 40.40.4: Explain why .Z5; / is not a group. Give at least two reasons.
 40.40.5: Consider the operations ^, _, and _ defined on the set fTRUE; FALSE...
 40.40.6: The set of even permutations of f1; 2; : : : ; ng is denoted An. Pr...
 40.40.7: Show that the operation in Example 40.9 is not associative.
 40.40.8: Prove that if .G; / is a group and g 2 G, then g 1 1 D g.
 40.40.9: Prove that if .G; / is a group, then e 1 D e.
 40.40.10: We saw that .QC;/ is a group (positive rational numbers with multip...
 40.40.11: This problem is only for those who have studied linear algebra. Let...
 40.40.12: Let A be a set. Prove that .2A; / is a group.
 40.40.13: Let G be a group and let a 2 G. Define a function f W G ! G by f .g...
 40.40.14: Let G be a group. Define a function f W G ! G by f .g/ D g 1 . Prov...
 40.40.15: Let be an operation on a finite set G. Form the operation table. Pr...
 40.40.16: Let .G; / be a group and let g; h 2 G. Prove that .g h/1 D h 1 g 1 ...
 40.40.17: Let .G; / be a group. Prove that G is Abelian if and only if .g h/1...
 40.40.18: Let .G; / be a group. Define a new operation ? on G by g ? h D h g:...
 40.40.19: Let .G; / be a group. Notice that e 1 D e. Prove that if jGj is fin...
 40.40.20: Let be an operation defined on a set A. We say that has the left ca...
 40.40.21: Reverse Polish Notation. We remarked at the beginning of this secti...
 40.40.22: RPN continued. Convert the following expressions from standard nota...
 40.40.23: RPN continued. Suppose we have a list of numbers and operations (C ...
 40.40.24: RPN continued. Write a computer program to evaluate RPN expressions.
Solutions for Chapter 40: Groups
Full solutions for Mathematics: A Discrete Introduction  3rd Edition
ISBN: 9780840049421
Solutions for Chapter 40: Groups
Get Full SolutionsThis textbook survival guide was created for the textbook: Mathematics: A Discrete Introduction, edition: 3. Mathematics: 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. Since 24 problems in chapter 40: Groups have been answered, more than 9275 students have viewed full stepbystep solutions from this chapter. Chapter 40: Groups includes 24 full stepbystep solutions.

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!

Circulant matrix C.
Constant diagonals wrap around as in cyclic shift S. Every circulant is Col + CIS + ... + Cn_lSn  l . Cx = convolution c * x. Eigenvectors in F.

Complex conjugate
z = a  ib for any complex number z = a + ib. Then zz = Iz12.

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.

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 Fn1c can be computed with ne/2 multiplications. Revolutionary.

Free columns of A.
Columns without pivots; these are combinations of earlier columns.

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.

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.

Pivot columns of A.
Columns that contain pivots after row reduction. These are not combinations of earlier columns. The pivot columns are a basis for the column space.

Plane (or hyperplane) in Rn.
Vectors x with aT x = O. Plane is perpendicular to a =1= O.

Projection p = a(aTblaTa) onto the line through a.
P = aaT laTa has rank l.

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.

Row picture of Ax = b.
Each equation gives a plane in Rn; the planes intersect at x.

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!

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

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

Unitary matrix UH = U T = UI.
Orthonormal columns (complex analog of Q).

Vector space V.
Set of vectors such that all combinations cv + d w remain within V. Eight required rules are given in Section 3.1 for scalars c, d and vectors v, w.

Vector v in Rn.
Sequence of n real numbers v = (VI, ... , Vn) = point in Rn.