permutations and dets

Appendix B : Determinants B.1 Definition of the determinant First, define z0 to be the n-component vector of increasing integers 1 to n, z0 ≡ . (B.1.1) Let a be some permutation (reordering) of these integers, so write a ≡ = A = A z0 (B.1.2) where A is an nxn matrix which has 1's in the right places to create this permutation vector a. For example, a = Azo ↔ = . The vector a can be obtained from the vector z0 by making Sa pairwise swaps of elements of z0. Although Sa is not unique, the number (-1)S is unique. For example, to get from (1,2,3) to (1,3,2) one could swap the second pair so Sa = 1, but one could then swap the first pair twice and then Sa = 3. This number (-1)S is of course ±1 and we shall call it the parity of the permutation a. Parity(a) ≡ (-1)S (B.1.3) Fact: Parity(Ca) = Parity(CAz0) = (-1)S+S = Parity(C-1a) (B.1.4) Proof: Doing permutation CA involves first doing A with its Sa swaps, and then doing C with its Sc swaps, for a total of Sa+Sc swaps. The inverse permutation C-1 obviously involves the same number of swaps as the permutation C. Moving now toward the definition of the determinant of a matrix M, define Π(a,b; M) ≡ MabMab ...... Mab = product of n factors (B.1.5) Suppose c = Cz0 is some arbitrary permutation. Then: Fact: Π(Ca,Cb; M) = Π(a,b; M) (B.1.6) Proof: Applying the same permutation to both the ak and bk indices of MabMab ...... Mab, just reorders the terms in the product but the product stays the same. Fact: Π(a,b; MT) = Π(b,a; M) (B.1.7) Proof: Π(a,b; MT) = MTabMTab .... MTab = MbaMba .... Mba = Π(b,a; M) We shall now define the determinant of an n x n matrix M in the following admittedly obscure manner (and later we will show that it reduces to more familiar forms), det(M) ≡ Σa Σb (-1)S+S Π(a,b; M) = Σa Σb (-1)S+S MabMab ...... Mab . (B.1.8) Here Σa means the sum over all permutations a of z0. In (B.1.8) the columns and rows of M are on a completely equal footing. Notice that a and b are in effect dummy summation indices. If we do a↔b, the expression for det(M) is unchanged. Thus we can rewrite (B.1.8) as det(M) = Σb Σa (-1)S+S Π(b,a; M) . (B.1.9) We are now ready for our first determinant theorem: Theorem 1: det(MT) = det(M). Switching rows with columns does not change a determinant. (B.1.10) Proof: det(MT) = Σb Σa (-1)S+S Π(b,a; MT) // (B.1.9) = Σb Σa (-1)S+S Π(a,b; M) // (B.1.7) = det(M) // (B.1.8) 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 where gi-1 is an element of the group (inverse) (gigj)gk = gi(gjgk) (associative) (B.2.1) 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. 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 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 is 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) but this is the same as saying Σb f(b) = Σb f(Cb) (B.2.4) Again, throwing in the permutation C merely causes a reordering of the sum. 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 last two results: det(M) ≡ Σa Parity(a) M1aM2a ...... Mna (B.2.7a) det(M) ≡ Σa Parity(a) Ma1Ma2 ...... Man (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: Σa Parity(a) f(a) = Σaa... a εaa... a f(a1, a2...an) (B.2.9) Proof: Although the sum on the right includes all nn terms, any terms with identical indices are removed since ε = 0 for such terms. Thus, the sum is really only over those n! terms which are permutations of 123,,n. For any such permutation, Parity(a) = εaa... a . Why? We know that Parity(a) = (-1)S where Sa is the number of swaps to get to a from z0 . But it then takes Sa index swaps to get from εaa... a to ε123..n and that involves Sa negations, which again is (-1)S . 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 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, we then know that det(M'T) = - det(MT), so swapping columns 1 and 3 negates det(M). An obvious corollary 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) B.3 Minors, Cofactors, the Cofactor Expansions of det(M) Definition: The minor of a matrix element Mrs is the determinant of the submatrix obtained by crossing out the rth row and the sth column. It is a challenge, however, to write this out in symbols. Let's start with a more detailed version of (B.2.11a), where the ai are column summation indices, det(M) = Σaaaaa...a εaaaaa...a M1aM2aM3aM4aM5a ...... Mna . (B.3.1) We shall make the following conjecture for the form of minor(M23) minor(M32) = (-1)3-2 Σaaaa...a εaa2aa...a M1aM2aM4aM5a ...... Mna (B.3.2) Compared to det(M) shown in (B.3.1), we have made these changes : Removed the factor M3a ( since row 3 matrix elements cannot appear in minor(M32) ) Removed the sum over a3. Replaced a3 by the number 2 on the ε tensor. added a sign factor (-1)3-2. Notice that since there is a 2 on the ε tensor, any time a summation index ai = 2 there is no contribution since then the ε tensor has two indices the same. so in effect the value 2 has been removed from all the residual summations ai. That is good, since column 2 is supposedly "crossed out" in minor(M32). The factor (-1)3-2 is added so that the "diagonal term" in the minor will be positive. This sign (-1)3-2 gets used up if we slide the "2" to its natural position (position 2) on the ε tensor, minor(M32) = Σaaaa...a εa2aaa...a M1aM2aM4aM5a ...... Mna . (B.3.3) The diagonal term in minor(M32) is then positive, matching the mechanical crossing out method, ε12345..n M11M22M44M55 ...... Mnn = + M11M22M44M55 ...... Mnn . (B.3.4) A more compact notation for (B.3.2) would be minor(M32) = (-1)3-2 Σa,i≠3 εa,a=2 Πi≠3 (Mi,a) . (B.3.5) Starting over, we could show similarly that minor(M42) = (-1)4-2 Σa,i≠4 εa,a=2 Πi≠4 (Mi,a) (B.3.6) We now have a sign factor (-1)4-2 because the "2" on ε has to be slid 2 positions to get to its natural location (position 4 on ε). More generally we can say minor(Ms2) = (-1)s-2 Σa,i≠s εa,a=2 Πi≠s (Mi,a) (B.3.7) where the slide is now s-2 places. Still more generally we find, replacing 2 by r, minor(Msr) = (-1)s±r Σa,i≠s εa,a=r Πi≠s (Mi,a) . (B.3.8) This then is our "best form" expression for a minor of matrix element Msr. Either sign will do, since (-1)s-r = (-1)s-r(-1)2r = (-1)s+r since (-1)2r = 1 Choosing the + sign in (B.3.8) and putting (-1)s+r on the left side we get, (-1)s+r minor(Msr) = Σa,i≠s εa,a=r Πi≠s (Mi,a) . (B.3.9) The left side here is called the cofactor of Msr, written cof(Msr). Thus we have shown that cof(Msr) ≡ (-1)s+r minor(Msr) = Σa,i≠s εa,a=r Πi≠s (Mi,a) . (B.3.10) Fact: Neither minor(Msr) nor cof(Msr) are functions of the Msr matrix elements of M! In (B.3.10) this is so because (1) row s is excluded in Πi≠s(Mi,a); (2) ai = r is excluded by the factor εa,a=r . More intuitively, this is so because to get minor(Msr) we "cross out" row s and column r. Thus, = = 0 for any pair r,s in 1,2...n (B.3.11) Finally, suppose we replace r with an integer which we call as. Doing this causes εa,a=r → εa,a=a = εa = εaaaa...a = the normal ε tensor form (B.3.12) Then (B.3.10) becomes the following, cof(Msa) ≡ (-1)s+a minor(Msa) = Σa,i≠s εa Πi≠s (Mi,a) . (B.3.13) Now start again with det(M) of (B.3.1) and rewrite it in our compact notation: det(M) = Σaaaaa...a εaaaaa...a M1aM2aM3aM4aM5a ...... Mna = Σa εa Πi(Mi,a) // next, extract the as sum and its Msa factor : = Σa Msa [Σa,i≠s εa Πi≠s (Mi,a)] // next use (B.3.12) to get = Σa Msa [cof(Msa)] // next, change summation index from as to n = Σn Msn cof(Msn) . // valid for any s in 1,2...n (B.3.14) This is the cofactor expansion of det(M) where one "works across row s" and n is a column index. Another form of this expansion is det(M) = det(MT) = Σn MTsn cof(MTsn) = Σn Mns cof(Mns) (B.3.15) and in this form one "works down column s" where n is now a row index. We have just proven : Theorem 5 (Cofactor Expansions): det(M) = Σn Msn cof(Msn) = Σn (rs)n cof(Msn) work across row s s = 1,2....n (B.3.16a) det(M) = Σn Mns cof(Mns) = Σn (cs)n cof(Mns) work down column s s = 1,2....n (B.3.16b) B.4 Expressions for the inverse matrix M-1 and Cramer's Rule Consider our expansion (B.3.15a) working across row s, det(M) = Σn Msn cof(Msn) (B.4.1) Suppose we replace the elements of row s (Msn) with the elements of some other row r in M (Mrn). In doing so we have created a new matrix, call it M'. Notice that cof(M'sn) = cof(Msn) because, although going from M to M' we have altered row s, we have not altered cof(Msn) since this depends only on the entries in all the rows other than row s (think "crossing out" row s for minor(Msn) ). See Fact (B.3.11). Therefore we find, det(M') = Σn M'sn cof(M'sn) = Σn Mrn cof(Msn) . (B.4.2) But by Corollary 4 (B.2.14) det(M') = 0 since two rows of M' are the same. Thus 0 = Σn Mrn cof(Msn) r ≠ s (B.4.3) Combining this with (B.4.1) gives, Σn Mrn cof(Msn) = det(M)δr,s . (B.4.4) Now for clarity define a cofactor matrix C in this manner Csn ≡ cof(Msn) (B.4.5) In matrix notation, we could define the matrix cof(M) to be matrix C and then C = cof(M) Csn = [cof(M)]sn = cof(Msn) . (B.4.6) Now (B.4.4) says ΣnMrn Csn = det(M)δr,s or ΣnMrn CTns = det(M)δr,s and finally in matrix notation, MCT = det(M) 1 or M [ ] = 1 . (B.4.7) Therefore we find this classic square matrix inversion formula, Theorem 6: M-1 = = = (B.4.8) To verify the last equality in (B.4.8) consider : = [cof(M)]Tns = [cof(M)]sn // meaning of transpose = cof(Msn) // (B.4.6) = cof(MTns) = [cof(MT)]ns // (B.4.6) applied to MT and therefore we have this matrix identity, [cof(M)]T = [cof(MT)] . (B.4.9) Using (B.4.8) it is trivial to solve a non-singular (detM≠0) system of linear equations y = Mx : y = Mx x = M-1 y = cof(MT) y = [cof(M)]T y . (B.4.10) In components, xs = Σn ([cof(M)]T)sn yn = Σn yn [cof(M)]ns = Σn yn cof(Mns) . (B.4.11) Now recall the cofactor expansion (B.3.16b), det(M) = Σn Mns cof(Mns) = Σn (cs)n cof(Mns) . (B.4.12) If one replaces column cs in M by y one gets det(M[cs→ y]) = Σn yn cof(Mns) // (B.4.12) = det(M) xs . // (B.4.11) (B.4.13) Solving this for xs we obtain another classic result, Theorem 7 (Cramer's Rule): y = Mx xs = (B.4.14)