20 3 Alternating k-Linear Functions To show linear independence,suppose ci=0 for some ciR.Applying both sides to the vector ej gives 0=>ciai(ej)=>ci=cj.j=1.n. Hence,a,.,a"are linearly independent. This basis a,.a")for V*is said to be dual to the basis e1.en)for V. Corollary 3.2.The dual space V*of a finite-dimensional vector space V has the same dimension as y. Erample 3.3 (Coordinate functions).With respect to a basis efor a vector ∈V can be written unic s alin b(v)ei e昆Letpe the a to:过 a(v)=(v)ej=>bi(v)a'(ej)=>bi(v)8j =b(v) Thus,the set of coordinate functions"with respect to the basise.e is precisely the dual basis to e.en. 3.2 Permutations Fix a positive integer k.Apermutation of the set A=(1.is a bijection:A A.The product and of A is the composition A,in that order:first apply a,thent.The cyclic permutation(a a2.ar)is the permutation o such that a(a1)=a2,a(a2)=a3,.,(dr-1)=(dr),a(a)=a, and such that o fixes all the otherelements of A.The cyclic permutation(a a2.a,) is also called a cycle of length r or an r-cycle.A transposition is a cycle of the form (a b)that interchanges a and b,leaving all other elements of A fixed. A permutation:A-A can be described in two ways:as a matrix 12.。.k a()2).(k) or as a product of disjoint cycles(aan,)(b1.brn). Example 3.4.Supp ose the tion:,2,3,4,5-,23.4.5maps1,2 「123451 0= 24513 =(124)(35)
20 3 Alternating k-Linear Functions To show linear independence, suppose ciαi = 0 for some ci ∈ R. Applying both sides to the vector ej gives 0 = ciαi (ej ) = ciδi j = cj , j = 1, . . . , n. Hence, α1,.,αn are linearly independent. This basis {α1,.,αn} for V ∗ is said to be dual to the basis {e1,.,en} for V . Corollary 3.2. The dual space V ∗ of a finite-dimensional vector space V has the same dimension as V . Example 3.3 (Coordinate functions). With respect to a basis e1,.,en for a vector space V , every v ∈ V can be written uniquely as a linear combination v = bi (v)ei, where bi (v) ∈ R. Let α1,.,αn be the basis of V ∗ dual to e1,.,en. Then αi (v) = αi ⎛ ⎝ j bj (v)ej ⎞ ⎠ = j bj (v)αi (ej ) = j bj (v)δi j = bi (v). Thus, the set of coordinate functions b1,.,bn with respect to the basis e1,.,en is precisely the dual basis to e1,.,en. 3.2 Permutations Fix a positive integer k. A permutation of the set A = {1,.,k} is a bijection σ : A −→ A. The product τ σ of two permutations τ and σ of A is the composition τ ◦ σ : A −→ A, in that order; first apply σ, then τ . The cyclic permutation (a1 a2 ··· ar) is the permutation σ such that σ (a1) = a2, σ (a2) = a3, . . . , σ (ar−1) = (ar), σ (ar) = a1, and such that σ fixes all the other elements of A. The cyclic permutation (a1 a2 ··· ar) is also called a cycle of length r or an r-cycle. A transposition is a cycle of the form (a b) that interchanges a and b, leaving all other elements of A fixed. A permutation σ : A −→ A can be described in two ways: as a matrix 1 2 ··· k σ (1) σ(2) ··· σ (k) or as a product of disjoint cycles (a1 ··· ar1 )(b1 ··· br2 )··· . Example 3.4. Suppose the permuation σ : {1, 2, 3, 4, 5} −→ {1, 2, 3, 4, 5} maps 1, 2, 3, 4, 5 to 2, 4, 5, 1, 3 in that order. Then σ = 12345 24513 = (124)(3 5).
3.2 Permutations 21 Let be the group of all permutations of the set .Apermutation is on whe rit isth e produc ons.From the theory of permutatio at this is a we concept:an even permutation can never be written as the product of an odd numbe of transpositions and vice versa.The sign of a permutation o,denoted sgn()or sgno,is defined to be +1 or-1 depending on whether the permutation is even or odd.Clearly,the sign of a permutation satisfies sgn(ar)=sgn(a)sgn(t) for o,rE Sk. Example 3.5.The decomposition (12345)=(15)(14)(13)(12) shows that the 5-cycle(1 2 3 4 5)is an even permutation. More generally,the decomposition (a1a2·ar)=(a1ar)(a1ar-1）.(aa3)(a1a2) shows that an r-cycle is an even permutation if and only ifr is odd,and an odd permutation if and only ifr is even.Thus one way to compute the sign of apermutation is to decompose it into a product of cycles and to count the number of cycles of even length.For example,the permutation o in Example 3.4 is odd because(12 4)is even and (3 5)is odd. buta(i)>a().Th mutation in Example 3.4h nve inversions:(2.1). (4,1),(5,1).(4,3),and(5, A secon to compute the sign of a permutation is to count the number of inversions as in the following proposition. Proposition 3.6.A permutation is even if and only if it has an even number of inver- sions. Proof.By multiplying by a number of transpositions,we can obtain the identity This can be achieved ink steps (1)First,look for the number 1 among (1).(2). (k).Eve ery number p eding 1 in this li i ppos 1 (i). ((1)1 ,(o )1)are inversion of o.Now move I to the begin ning of the list across the i-I elements (1). 01 1).This requires transpositions.Note that the number of transpositions is the number of inversions ending in 1. (2)Next look for the number 2in the list:1,(1),.(i-1),(i+1).(k). Every number other than I preceding 2 in this list gives rise to an inversion ((m),2).Suppose there are i2 such numbers.Then there are iz inversions ending in 2.In moving 2 to its natural position 1,2.(1).(2).we need to move it a ers.This requires i transpositions
3.2 Permutations 21 Let Sk be the group of all permutations of the set {1,.,k}. A permutation is even or odd depending on whether it is the product of an even or an odd number of transpositions. From the theory of permutations we know that this is a well-defined concept: an even permutation can never be written as the product of an odd number of transpositions and vice versa. The sign of a permutation σ, denoted sgn(σ ) or sgn σ, is defined to be +1 or −1 depending on whether the permutation is even or odd. Clearly, the sign of a permutation satisfies sgn(σ τ ) = sgn(σ )sgn(τ ) for σ, τ ∈ Sk. Example 3.5. The decomposition (12345) = (1 5)(1 4)(1 3)(1 2) shows that the 5-cycle (12345) is an even permutation. More generally, the decomposition (a1 a2 ··· ar) = (a1 ar)(a1 ar−1)···(a1 a3)(a1 a2) shows that an r-cycle is an even permutation if and only if r is odd, and an odd permutation if and only ifr is even. Thus one way to compute the sign of a permutation is to decompose it into a product of cycles and to count the number of cycles of even length. For example, the permutation σ in Example 3.4 is odd because (124) is even and (3 5) is odd. An inversion in a permutation σ is an ordered pair (σ (i), σ (j )) such that i<j but σ (i) > σ (j ). Thus, the permutation σ in Example 3.4 has five inversions: (2, 1), (4, 1), (5, 1), (4, 3), and (5, 3). A second way to compute the sign of a permutation is to count the number of inversions as in the following proposition. Proposition 3.6. A permutation is even if and only if it has an even number of inversions. Proof. By multiplying σ by a number of transpositions, we can obtain the identity. This can be achieved in k steps. (1) First, look for the number 1 among σ (1), σ (2), . . . , σ (k). Every number preceding 1 in this list gives rise to an inversion. Suppose 1 = σ (i). Then (σ (1), 1), . . . , (σ (i − 1), 1) are inversions of σ. Now move 1 to the beginning of the list across the i − 1 elements σ (1), . . . , σ (i − 1). This requires i − 1 transpositions. Note that the number of transpositions is the number of inversions ending in 1. (2) Next look for the number 2 in the list: 1,σ(1), . . . , σ (i −1), σ (i +1), . . . , σ (k). Every number other than 1 preceding 2 in this list gives rise to an inversion (σ (m), 2). Suppose there are i2 such numbers. Then there are i2 inversions ending in 2. In moving 2 to its natural position 1, 2,σ(1), σ (2), . . . , we need to move it across i2 numbers. This requires i2 transpositions
22 3 Alternating k-Linear Functions Repeating this procedure,we see that for each j=1.k,the number of transpositions required to move j to its natural position is the same as the number of inversions ending in j.In the end we achieve the ordered list 1.2.k from o(k)by multiplying o by as many tran efore.()( positions as the total number no.The 3.3 Multilinear Functions Denote by vk=V .x V the Cartesian product of k copies of a real vector space V.A function f:VkR is k-linear if it is linear in each of its k arguments f(.,av+b,.)=af(.,v,.)+bf(,.) for a,b ER and v.w e V.Instead of 2-linear and 3-linear,it is customary to say "bilinear and "trilinear."A k-linear function on V is also called a k-tensor on V. We will denote the vector space of all k-tensors on V by L(V).If f is a k-tensor on V,we also call k the degree of f. Example 3.7.The dot product f(v.w)=v.w on R"is bilinear: where v=∑v'ei and w=∑w'ei. Example 3.8.The determinant f(v1. Un)=det[vl.Un].viewed as a function of the n column vectors v.in R",is n-linear. Definition 3.9.Ak-linear function f:Vk-R is symmetric if f(vg),g)）=f(U1,g) for all:it is alterating if f(va(1).va())=(sgna)f(v1.v) for all∈Sk Example 3.10. (i)The dot product f(v.w)=v.w on R"is symmetric. (ii)The determinant f(v1.vn)=det[v.vn]on R"is alternating. Weareespecially interested in the space A(V)of all altematingk-linear functions on a vector space V for k 0.These are also called alternating k-tensors,k- covectors,or multicovectors on V.For k =0,we define a0-covector to be a constant so that Ao(V)is the vector space R.A 1-covector is simply a covector
22 3 Alternating k-Linear Functions Repeating this procedure, we see that for each j = 1,.,k, the number of transpositions required to move j to its natural position is the same as the number of inversions ending in j . In the end we achieve the ordered list 1, 2,.,k from σ (1), σ (2), . . . , σ (k) by multiplying σ by as many transpositions as the total number of inversions in σ. Therefore, sgn(σ ) = (−1)# inversions in σ . 3.3 Multilinear Functions Denote by V k = V ×···×V the Cartesian product of k copies of a real vector space V . A function f : V k −→ R is k-linear if it is linear in each of its k arguments f (. . . , av + bw, . . . ) = af (. . . , v, . . . ) + bf (. . . , w, . . . ) for a, b ∈ R and v, w ∈ V . Instead of 2-linear and 3-linear, it is customary to say “bilinear’’ and “trilinear.’’ A k-linear function on V is also called a k-tensor on V . We will denote the vector space of all k-tensors on V by Lk(V ). If f is a k-tensor on V , we also call k the degree of f . Example 3.7. The dot product f (v, w) = v · w on Rn is bilinear: v · w = vi wi , where v = vi ei and w = wi ei. Example 3.8. The determinant f (v1,.,vn) = det[v1 ··· vn], viewed as a function of the n column vectors v1,.,vn in Rn, is n-linear. Definition 3.9. A k-linear function f : V k −→ R is symmetric if f (vσ (1),.,vσ (k)) = f (v1,.,vk) for all permutations σ ∈ Sk; it is alternating if f (vσ (1),.,vσ (k)) = (sgn σ )f (v1,.,vk) for all σ ∈ Sk. Example 3.10. (i) The dot product f (v, w) = v · w on Rn is symmetric. (ii) The determinant f (v1,.,vn) = det[v1 ··· vn] on Rn is alternating. We are especially interested in the space Ak(V ) of all alternating k-linear functions on a vector space V for k > 0. These are also called alternating k-tensors, kcovectors, or multicovectors on V . For k = 0, we define a 0-covector to be a constant so that A0(V ) is the vector space R. A 1-covector is simply a covector.
3.4 Permutation Action on k-Linear Functions 23 3.4 Permutation Action on k-Linear Functions If f is a k-linear function on a vector space V and o is a permutation in S,we define a new k-linear function o f by (ofD(U1,g)=f(va(.g】 Thus,f is symmetric if and only if of f for all o e Se and f is alternating if and only if of (sgno)f for allo Sk. upS is the identity group and a 1-linea A1(V=L1(V)=V* Lemma 3.11.Ifa.S and f is a k-linear function on V.then t(of)=(o)f Proof.For v,k∈V, t(of)(v1.v)=(af)(vr().vr()) =(of)(w1.wg)(letting wi vr(i)) =f(wa),Wa） =f(vr(a(D).vr(a())=f(v(ra)().v(a)(k)) =(ta)f(v1,.vk). In general,if G is a group and X is a set,a map G×XX (a,x)→·x is called a left action of G on X if (i)1.x =x where 1 is the identity in G and x is any element in X,and (it·(a·)=(to)x for all,o∈G,x∈X. In this terminology,we have defined a left action of the e permutation group S on the space L(V)of k-linear functions on V.Note that each permutation acts as a linear function on the vector space L(V)since of is R-linear in f. A right action of G on X is defined similarly:it is a map Xx G-X such that 0x1=x ((·)·t=x·(ot) for all o.t∈G and x∈X. Remark 3.12.Insome books the notation forofis fo.In that notation,(f)=fre, not for
3.4 Permutation Action on k-Linear Functions 23 3.4 Permutation Action on k-Linear Functions If f is a k-linear function on a vector space V and σ is a permutation in Sk, we define a new k-linear function σf by (σf )(v1,.,vk) = f (vσ (1),.,vσ (k)). Thus, f is symmetric if and only if σf = f for all σ ∈ Sk and f is alternating if and only if σf = (sgn σ )f for all σ ∈ Sk. When there is only one argument, the permutation group S1 is the identity group and a 1-linear function is both symmetric and alternating. In particular, A1(V ) = L1(V ) = V ∗. Lemma 3.11. If σ, τ ∈ Sk and f is a k-linear function on V , then τ (σf ) = (τ σ )f . Proof. For v1,.,vk ∈ V , τ (σf )(v1,.,vk) = (σf )(vτ (1),.,vτ (k)) = (σf )(w1,.,wk) (letting wi = vτ (i)) = f (wσ (1),.,wσ (k)) = f (vτ (σ (1)),.,vτ (σ (k))) = f (v(τ σ )(1),.,v(τ σ )(k)) = (τ σ )f (v1,.,vk). In general, if G is a group and X is a set, a map G × X −→ X (σ, x) → σ · x is called a left action of G on X if (i) 1 · x = x where 1 is the identity in G and x is any element in X, and (ii) τ · (σ · x) = (τ σ ) · x for all τ,σ ∈ G, x ∈ X. In this terminology, we have defined a left action of the permutation group Sk on the space Lk(V ) of k-linear functions on V . Note that each permutation acts as a linear function on the vector space Lk(V ) since σf is R-linear in f . A right action of G on X is defined similarly; it is a map X × G −→ X such that (i) x · 1 = x, (ii) (x · σ ) · τ = x · (σ τ ) for all σ, τ ∈ G and x ∈ X. Remark 3.12. In some books the notation for σf is f σ . In that notation,(f σ )τ = f τ σ , not f σ τ
24 3 Alterating k-Linear Functions 3.5 The Symmetrizing and Alternating Operators Given any k-linear function f ona vector space V,there is a way to make asymmetric k-linear function Sf from it: (Sf)(u1.,g)=f(a,gw） or,in our new shorthand, Sf=∑of GESk Similarly,there is a way to make an alternating k-linear function from f.Define Af=∑(sgno)af GESk Proposition 3.13. (i)The k-linear function Sf is symmetric. ()The k-linear function Af is alterating. Proof.We prove(ii)only and leave(i)as an exercise. r(Af)=(sgna)t(af) a∈S =∑(sgno)(ra)f (Lemma3.11) =(sgnr)(sgn ra)(ra)f =(sgn r)Af. since as o runs through all permutations in Sk.so does ro. Exercise 3.14(Symmetrizing operator).Show that the k-linear function Sf is symmetric. Lemma 3.15.If f is an alternating k-linear function on a vector space V,then Af=(k!)f. Proof. Af=〉(sgno)f=〉(sgno)(sgna)f=(kf. 0 aS GESL Exercise 3.16 (The alternating operator).If f is a 3-linear function on a vector space V. what is (Af)(v1.v2 3),where v1,v2.3 V?
24 3 Alternating k-Linear Functions 3.5 The Symmetrizing and Alternating Operators Given any k-linear function f on a vector space V , there is a way to make a symmetric k-linear function Sf from it: (Sf )(v1,.,vk) = σ∈Sk f (vσ (1),.,vσ (k)) or, in our new shorthand, Sf = σ∈Sk σf. Similarly, there is a way to make an alternating k-linear function from f . Define Af = σ∈Sk (sgn σ )σf. Proposition 3.13. (i) The k-linear function Sf is symmetric. (ii) The k-linear function Af is alternating. Proof. We prove (ii) only and leave (i) as an exercise. If τ ∈ Sk, τ (Af ) = σ∈Sk (sgn σ )τ (σf ) = σ∈Sk (sgn σ )(τ σ )f (Lemma 3.11) = (sgn τ ) σ∈Sk (sgn τ σ )(τ σ )f = (sgn τ )Af, since as σ runs through all permutations in Sk, so does τ σ. Exercise 3.14 (Symmetrizing operator). Show that the k-linear function Sf is symmetric. Lemma 3.15. If f is an alternating k-linear function on a vector space V , then Af = (k!)f . Proof. Af = σ∈Sk (sgn σ )σf = σ∈Sk (sgn σ )(sgn σ )f = (k!)f. Exercise 3.16 (The alternating operator). If f is a 3-linear function on a vector space V , what is (Af )(v1, v2, v3), where v1, v2, v3 ∈ V ?