- 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
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.
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 Fn-1c 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, ... , 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.
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+ (Moore-Penrose 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 = U-I.
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.