App B_2 edit

B.2 The permutation group and the permutation tensor ε Definition. A set of elements {gi} form a group G if : gigj is also in the group (closure) gi-1 exists for each gi in G, where gi-1 is also in G (inverse) (gigj)gk = gi(gjgk) (associative) (B.2.1) Comment: It is implicit in the above definition that the group has some "operation" which gives meaning to gigj, which we shall just think of as "multiplication". When group elements are represented by matrices, that operation is multiplication of those matrices, and that will apply to the permutation group below. Fact: giG = G (the rearrangement theorem) (B.2.2) This says that multiplication of all the elements of a group by an element gi in the group creates a reordering of the group elements. Here G is the set of group elements. Proof. Consider giG = gi [g1, g2....gn] = [gig1, gig2....gign] = set of n elements. Unless two elements are the same, this must exhaust the entire group. How do we know that gig1 and gig2 might not be the same? Apply gi-1 from the left and that would say g1 = g2 which is not the case. Fact: Σg f(g) = Σg f(g1g) if Σg runs over the entire group G (B.2.3) Proof: In Σg f(g1g), as g runs over G, the argument g' ≡ g1g runs over G by the above rearrangement theorem. Thus, the sum Σg f(g1g) is just a reordering of the terms in the sum Σg f(g). It is easy to show that the set of permutations of z0 forms a group and therefore the above facts can be used. For example, the product of two permutations is a permutation, and every permutation clearly has an inverse, and (AB)C = A(BC) for any matrices. Fact (B.2.3) can be written ΣB f(Bzo) = ΣB f(CBz0) // b = Bz0 Here the sum ΣB is over all permutation matrices which correspond to permutations b of z0, and C is some arbitrary permutation matrix associated with some permutation c of z0. An equivalent way of stating the above involves a direct summation Σb over all permutation vectors b of z0 , Σb f(b) = Σb f(Cb) . // permutation sum rearrangement theorem (B.2.4) Throwing in the arbitrary permutation C merely causes a reordering of the sum. This is an extremely powerful and useful fact. Consider then : det(M) ≡ Σa [Σb (-1)S+S Π(a,b; M) ] // (B.1.8) = Σa [Σb (-1)S+S Π(A-1a,A-1b; M)] // (B.1.6) with C = A-1; A-1a = A-1Az0 = z0 = Σa [ Σb Parity(A-1b) Π(z0,A-1b; M) ] // (B.1.4) with C = A-1 and a = b = Σa [ Σb Parity(b) Π(z0,b; M) ] // (B.2.4) with C = A-1 (key step) = Σb Parity(b) Π(z0,b; M) // n! identical terms in Σa = Σa Parity(a) Π(z0,a; M) // rename dummy sum variable = Σa Parity(a) M1aM2a ...... Mna . // (B.1.5) (B.2.5) Since det(MT) = det(M) from Theorem 1 (B.1.10), we can also write this result as det(M) = Σa Parity(a) Ma1Ma2 ...... Man (B.2.6) Proof: det(M) = det(MT) = Σa Parity(a) MT1aMT2a ...... MTna = Σa Parity(a) Ma1Ma2 ...... Man Here then are the last two results: ( recall that Sa is the number of pairwise swaps to get from z0 to a ) det(M) ≡ Σa Parity(a) M1aM2a ...... Mna Parity(a) = (-1)S (B.2.7a) det(M) ≡ Σa Parity(a) Ma1Ma2 ...... Man Parity(a) = (-1)S . (B.2.7b) Definition: The permutation tensor εijk.. (n subscripts) : ε12...n = 1 for any index swap, ε changes sign: ε..i..j.. = - ε..j..i.. therefore, if any two indices are the same, ε = 0 ε..i..i.. = - ε..i..i.. = 0 (B.2.8) Fact: If a is a permutation of z0, then εaa... a = Parity(a) = (-1)S ≡ εa . (B.2.9) Proof: Since indices ai represent a permutation of z0 , it takes Sa swaps to get from εaa... a to ε123...n by the definition of ε. In dense notation, one could say εa = (-1)S εz . Using (B.2.9) in (B.2.7) then gives these two classic det(M) expressions : Theorem 2: det(M) can be represented in these two ways: det(M) = Σaa... a εaa... a M1aM2a ...... Mna (B.2.10a) det(M) = Σaa... a εaa... a Ma1Ma2 ...... Man . (B.2.10b) In dense notation, one could write the above as (a is now a vector), det(M) = Σaεa Mza (B.2.10a)' det(M) = ΣaεaMaz . (B.2.10b)' In most applications, the following simpler notation suffices: det(M) = Σabc..q εabc..q M1aM2bM3c....Mnq (B.2.11a) det(M) = Σabc..q εabc..q Ma1Mb2Mc3....Mqn . (B.2.11b) Theorem 3: For a square matrix M, adding a multiple of one row to another does not change det(M). The same is true for adding a multiple of one column to another. (B.2.12) Proof: (rows) Suppose we replace r3 → r3 + α r2. This says M3i → M3i + α M2i . Eq (B.2.11a) says : det(M') = Σabc..q εabc..q M1aM2b(M3c + α M2c) ....Mnq = det(M) + α Σabc..q εabc..q M1aM2bM2c ....Mnq . Since M1aM2bM2c ....Mnq is symmetric under b↔c while εabc..q is anti-symmetric, the extra α term vanishes. That is to say, sum = Σbc AbcSbc = Σcb AcbScb = Σcb (-Abc)(Sbc) = - sum = 0. Using (B.2.11b) this argument shows that c3 → c3 + α c2 similarly does not alter det(M). Theorem 4: Swapping two rows (columns) of square matrix M causes det(M) → - det(M). (B.2.13) Proof: Let's swap rows 1 and 3 in M to get M'. Then from (B.2.11a), det(M') = Σabc..q εabc..q M3aM2bM1c....Mnq = Σabc..q [- εcba..q] M3aM2bM1c....Mnq // swap a↔c on ε = - Σabc..q εabc..q M3cM2bM1a....Mnq // dummy rename a↔c = - Σabc..q εabc..q M1aM2bM3c....Mnq // reorder product = - det(M) . Using Theorem 1 that det(A) = det(AT), we then know that det(M'T) = - det(MT), so swapping columns 1 and 3 negates det(M). An obvious corollary follows if the two swapped columns have identical data : Corollary 4: If two rows (columns) of square matrix A are the same, then det(M) = 0. (B.2.14) Here is one more well-known determinant theorem which again demonstrates the power of the rearrangement theorem (B.2.4). Theorem 5: det(AB) = det(A)det(B) (B.2.15) Proof: Since we already use A in a = Az0 , we shall prove det(XY) = det(X)det(Y) to avoid overloading symbols. Note that Parity(a) Parity(b) = (-1)S(-1)S = (-1)S+S = Parity(Ab) from (B.1.4). Then : det(X)det(Y) = [ Σa Parity(a) Π(z0,a; X)] [ Σb Parity(b) Π(z0,b; Y)] // (B.2.5) twice = Σa [ Σb Parity(a) Parity(b) Π(z0,a; X) Π(z0,b; Y) ] = Σa [ Σb Parity(Ab) Π(z0,a; X) Π(Az0,Ab; Y) ] // (B.1.6) with C = A = Σa [ Σb Parity(Ab) Π(z0,a; X) Π(a,Ab; Y) ] // Az0 = a = Σa [ Σb Parity(b) Π(z0,a; X) Π(a,b; Y) ] // (B.2.4) with C = A = Σb Parity(b) Σa Π(z0,a; X) Π(a,b; Y) // move Σa = Σb Parity(b) Σa Π(z0,b; XY) // see below = det(XY) . // (B.2.5) The idea here is to get a in the right place on both Π's so that Σa Π(z0,a; X) Π(a,b; Y) = Σ aa... a X1aX2a ...... Xna YabYab ...... Yab = Σ aa... a (X1aYab)(X2aYab).....(XnaYab) = (XY)1b (XY)2b ... (XY)nb = Π(z0,b; XY) which in dense notation one would write as Σa XzaYab = (XY)zb . Corollary 5: det(ABC) = det(A)det(B)det(C) and so on. (B.2.16) Proof: det(ABC) = det(A[BC]) = det(A)det(BC) = det(A)det(B)det(C) . It is not hard to generalize the results of Theorem 2 to obtain (proof follows) : Theorem 2A: det(M) can be represented in these two ways: εbb... b det(M) = Σaa... a εaa... a MbaMba ...... Mba (B.2.17a) εbb... b det(M) = Σaa... a εaa... a MabMab ...... Mab . (B.2.17b) In dense notation, one could write the above as (a and b are now vectors), εbdet(M) = ΣaεaMba (B.2.18a) εbdet(M) = ΣaεaMab . (B.2.18a) For the special case b = z0 Theorem 2A reduces to Theorem 2. Proof : (we prove only the first lines, the proof for the second lines is similar) det(M) = Σa Parity(a) Π(z0,a; M) // line 6 of (B.2.5) = Σa Parity(a) Π(Bz0,Ba; M) // (B.1.6) with C = B = Σa Parity(Ba) Parity(b) Π(Bz0,Ba; M) // Parity(Ba) Parity(b) = Parity(a) = Σa Parity(a) Parity(b) Π(Bz0,a; M) // (B.2.4) that Σa f(Ba) = Σa f(a) = Parity(b) Σa Parity(a) Π(b,a; M) // b = Bz0 = εbb... b Σaa... a εaa... a MbaMba .... Mba // (B.1.5) and (B.2.9) = εb Σa εa Mba // previous line in dense notation (B.2.19) Here it is assumed that B and hence b is associated with a permutation of z0, In this case, (εb)2 = 1 so we can move εb to the left side to get εbdet(M) = Σa εa Mba . (B.2.20) In this form, the equation is valid whether or not b is a permutation of z0 . If in b = (b1,b2...bn) the bi are arbitrary elements of the set {1,2,...n} where two or more bi are the same (that is, b is not a permutation of z0), then Σa εaa... a MbaMba .... Mba = 0 by symmetry. For example, if b1 = b2 then S ≡ Σa εaa... a MbaMba .... Mba = Σa εaa... a MbaMba .... Mba // rename dummy indices a1 ↔ a2 = Σa [-εaa... a ] MbaMba .... Mba // (B.2.8) for ε and slide Mba to the right = - Σaεaa... aMbaMba .... Mba = - S S = 0 (B.2.21) So in this case the right side of (B.2.20) is zero. But from (B.2.8) εb = 0 so the left side is also zero.