On local matchability in groups and vector spaces ∗† 6 1 0 2 Mohsen Aliabadi1 and Mano Vikash Janardhanan2 b e F 1Department of Mathematics, Statistics, and Computer Science, University of Illinois, 2 851 S. Morgan St, Chicago, IL 60607, USA ] 2Department of Mathematics, Statistics, and Computer Science, University of Illinois R 851 S. Morgan St, Chicago, IL 60607, USA G . h 1E-mail address: [email protected] at 2E-mail address: [email protected] m [ 2 v Abstract 2 2 3 In this paper, we define locally matchable subsets of a group which 6 0 is extracted from the concept of matchings in groups and used as a tool . 1 to give alternative proofs for existing results in matching theory. We 0 6 also give the linear analogue of local matchability for subspaces in a 1 : v field extension. Our tools mix additive number theory, combinatorics i X and algebra. r a 1 Introduction The notion of matchings in groups was used to study an old problem of Wake- ford concerning canonical forms for symmetric tensors [11]. Losonczy in [10] ∗ Key Words: abelian group, matching, acyclic matching property, torsion-free group † AMS Mathematics Subject Classification: 05A15, 20F99, 20D60, 12F05. 1 introduced matchings for groups to work on Wakeford’s problem.Let G be an additive abelian group and A and B be two non-empty subsets of G. A matching from A to B is a map f : A → B which is bijective and satisfies the condition a+f(a) 6∈ A, for any a ∈ A.This concept can be used to define the matching property in the sense of groups. It is said that the abelian group G has the matching property, if for every pair A and B of non-empty finite subsets satisfying #A = #B and 0 6∈ B, there exists at least one matching from A to B. In addition to this generalization of the definition of matching, we can see the following which is its extension in a new fashion: Let A, B and C be non-empty finite subsets of G such that A ⊆ C. A C- matching from A to B is a map f : A → B which is bijective and satisfies the condition a+f(a) 6∈ C, for all a ∈ A. Clearly, a matching from A to B is an A-matching from A to B. The following definition can also be extracted from the original concept of matchable subsets of a group. Let A and B be non-empty subsets of G such that for any proper subgroup H of G with H ∩ B 6= ∅ and a + H ⊆ A for some a ∈ A, one can find an A-matching from a subset of A to H ∩B. Then we say A is locally matched to B. It is obvious that if A is matched to B, then it is locally matched to B as well. We will see in the section 3 that matchability concludes local matchability, i.e. these two concepts are equivalent. We will use this concept as a tool to give an alternative proof for groups with matching property. 2 Organization of the paper The purpose of this paper is to find the relations between local matchability and matchability in groups and vector spaces to give alternative proofs for existing results on matching property for groups and also its linear analogue. In section 2, we will mention the results that have been proven on matching in groups and vector spaces and also some tools of additive number theory required to prove our main results. In section 3, we will show the equivalency between matchability and local matchability for subsets of a group. Section 4 concerned with the linear analogueof one of Losonzy’s results on matchings for cyclic groups. Furthermore, we will present a dimension criteria for the prim- itive subspaces related to our results in Theorem 4.1.Finally, in section 5, we show that if A is matched to B, then A it is locally matched to B in the sense of vector spaces. However, the converse is still not clear in the general case. We will see in Theorem 5.2 that for vector spaces in a field extension whose algebraic elements are separable, the local matchability implies the matchabil- ity. As an application we give an alternative proof for author’s main result in [6]. 2 Prelimanaries The following theorems are known about matching for groups and vector spaces. As we already mentioned, our goal in this paper is to prove their more general cases. Theorem 1. An abelian group G has the matching property if and only if G is torsion-free or cyclic of prime order [8]. 3 Theorem 2. Let G be a non-trivial finite cyclic group. Suppose we are given non-empty subsets A and B of G such that #A = #B and every element of B is a generator of G. Then there exists at least one matching from A to B [8]. Here, we define the matching property for subspaces in a field extension. Let K ⊆ L be a field extension and A and B be n-dimensional K-subspaces of the field extension L. Let A = {a ,...,a } and B = {b ,...,b } be bases 1 n 1 n of A and B, respectively. It is said that A is matched to B if a b ∈ A ⇒ b ∈ hb ,...,ˆb ,...,b i, i 1 i n for all b ∈ B and i = 1,...,n, where hb ,...,ˆb ,...,b i is the hyperplane of 1 i n B spanned by the set B \ {b }; moreover, it is said that A is matched to i B if every basis A of A can be matched to a basis B of B. As it is seen, the matchable bases are defined in a natural way based on the definition of matching in a group. Indeed, we can consider A and B as subsets of the multiplicative group L∗ and so the bijection a 7→ b is a matching in the group i i setting sense. It’s said L has the linear matching property if, for every n ≥ 1 and every n-dimensional subspaces A and B of L with 1 6∈ B, the subspaces A is matched with B. Now, our definition for matchable subsets of two matchable bases: Let A˜ and B˜ be two K-subspaces of A and B, respectively. We say that A˜ is A-matched to B˜, if for any basis A˜ = {a ,...,a } of A˜, there exists a basis 1 m B˜ = {b ,...,b } of B˜ for which a b 6∈ A, for i = 1,...,m. In this case, it is 1 m i i also said that A˜ is A-matched to B˜. The following is the linear analogue of locally matchable subsets for the vector spaces in a field extension. Let K ⊆ L be a field extension and A, B be two n-dimensional K-subspaces of L. We say that A is locally matched to B if for any proper subfield H of L 4 with H ∩B 6= {0} and aH ⊆ A, for some a ∈ A, one can find a subspace A˜ of A such that A˜ is A-matched to H ∩B. The following theorem is a dimension criteria for matchable bases. For more results on linear version of matching see [2, 3, 4 and 6]. Theorem 3. Let K ⊂ Lbe a field extensionand AandB be two n-dimensional K-subspaces of L. Suppose that A = {a ,...,a } is a basis of A. Then A can 1 n be matched to a basis of B if and only if, for all J ⊆ {1,...,n}, we have: dim a−1A∩B ≤ n−#J. i i∈J \(cid:0) (cid:1) See[6]formoredetails. Oneofthemainresultin[6]isthatafieldextension K ⊂ L has the linear matching property if and only if there are no trivial finite intermediate extension K ⊂ M ⊂ L. We would like to mention that, although the statement of [6, Theorem 2.6] is slightly different and assumes that the extension is either purely transcendental or finite of prime degree, what they actually use in their proof is that there are no nontrivial finite intermediate extensions, which is a weaker condition. (See also [1].) For proving our main results, we shall need the following theorems from [9, page 116, Theorem 4.3]. Theorem 4 (Kneser). If C = A+B, where A and B are finite subsets of an abelian group G, then #C ≥ #A+#B −#H, where H is the subgroup H = {g ∈ G : C +g = C}. See [5] for more details regarding the following theorem which is the linear analogue of Kneser’s theorem. 5 Theorem 5. Let K ⊆ L be a field extension in which every algebraic element of L is separable over K. Let A,B ⊂ L be non-zero finite-dimensional K- subspaces of L and H be the stabilizer of hABi. Then dim hABi ≥ dim A+dim B −dim H. K K K K (Here H is a subfield of L containing K and we have HhABi = hABi.) Let E be a vector space over the field K and let E = {E ,E ,...,E } be a 1 2 n collection of vector subspaces of E. A free transversal for E is a free family of vectors {x ,...,x } in E satisfying x ∈ E for all i = 1,...,n. The following 1 n i i result of Rado [8] gives necessary and sufficient conditions for the existence of a free transversal for E, very similar to those of Hall’s marriage theorem. The interested readers are also referred to [7]. Theorem 6. Let E be a vector space over K and let E = {E ,E ,...,E } be 1 2 n a family of vector subspaces of E. Then E admits a free transversal if and only if dim + E ≥ #J, K i∈J i for all J ⊆ {1,...,n}. We shall use the following standard notation denoted by B∗ = {f : B → K : f is linear}, the dual of B where B is a K-vector space; furthermore, for any subspace C ⊆ B, we denote by C⊥ = {f ∈ B∗ : C ⊆ kerf} the orthogonal of C in B∗. Recall that dim C⊥ = dim B −dim C. K K K 6 Corollary 1. LetE be a n-dimensionalvectorspace overK andE = {E ,...,E } 1 k bea familyofvectorsubspacesofE such thatforanyJ ⊆ {1,...,k}, dim E ≤ K i i∈J \ n − #J. Then, there exist vector subspaces E˜ of E such that E ⊆ E˜ for i i i i = 1,...,k and for any J ⊆ {1,...,k}, dim E˜ = n−#J. K i i∈J \ Proof. Since dim E ≤ n−#J, then dim + E⊥ ≥ J. Using Theorem K i K i∈J i i∈J \ 2.6, E˜ = E⊥,...,E⊥ admits a free transversal. Let (a ,...,a ) be a free 1 k 1 k transversa(cid:8)l for E˜. The(cid:9)n dimK +i∈Jhaii = #J. Set E˜i = haii⊥, thus Ei ⊆ E˜i and dim E˜ = n−#J. K i i∈J \ We finish this section by inclusion-exclusion principle for vector spaces which states that for two finite dimensional K-vector spaces A and B, we have the following equality for the dimension of K-vector space A+B: dim (A+B) = dim A+dim B −dim A∩B. K K K K Note that since dim (A+B) = dim hA∪Bi, then we can rewrite the above K K equality as follows: dim hA∪Bi = dim A+dim B −dim (A∩B). K K K K 3 Local matchability for groups The following theorem shows that local matchability is equivalent to match- ability for abelian groups. Note that it is obvious that matchability implies local matchability. Then, we just show its converse. Theorem 7. Let G be an additive abelian group and A, B be non-empty finite subsets of G satisfying the conditions #A = #B and 0 6∈ B. If A is locally matched to B, then A is matched to B. 7 Proof. Suppose there is no matching from A to B. We are going to reach a contradiction. By Hall marriage Theorem there exists a non-empty finite subset S of A such that #B\U < #S, where U = {b ∈ B : s+b ∈ A, for any s ∈ S}. Let #A = #B = n, then #U +#S > n. Set U = U ∪{0}. Using 0 Kneser’s Theorem one can find the subgroup H of G such that #(U +S) ≥ #U +#S −#H, (1) 0 0 where H = {g ∈ G : g +U +S = U +S}. Applying Kneser’s Theorem for 0 0 U′ = H ∪U and S, we can find the subgroup H′ of G for which #(U′ +S) ≥ #U′ +#S −#H′, (2) where H′ = {g ∈ G : g +U′ +S = U′ +S}. We claim that H = H′ and to prove this, it suffices to show that U′ +S = U +S. We have 0 U′ +S = (H ∪U)+S = (H +S)∪(U +S) 0 = (H +S)∪(U +S +H) 0 = H +(S ∪(U +S)) 0 = H +(U +S) = U +S. (3) 0 0 Then H = H′ and it follows from (2) that #(U +S) ≥ #U′ +#S −#H. (4) 0 Using (3), (4) we get #(U +S) = #(U′ +S) 0 = #U′ +#S −#H = #(H ∪U)+#S −#H = #H +#U −#(H ∩U)+#S −#H = #U +#S −#(H ∩U). (5) 8 As U +S = S ∪(S +U), (5) follows 0 #(S ∪(S +U)) ≥ #U +#S −#(H ∩U). (6) Now, we have two cases for H ∩U. 1. If H∩U is empty, then by (6) we conclude that #(S∪(S+U)) ≥ n. On the other hand S ∪(S +U) is a subset of A. We would have #A > n, which contradicts #A = n above. 2. If H∩U is non-empty, then H∩B is. Also, if s ∈ S ⊆ A, then according to the definition of H, s + H ⊆ U + S + H = U + S ⊆ A. As A is 0 0 locally matched to B, then there is an A-matching f from a subset of A to H ∩ B. We claim that f−1(H ∩U) ∩ (U + S) is empty. If not and 0 a ∈ f−1(H∩U)∩(U +S), then a+f(a) ∈ (U +S)+H as a ∈ U +S and 0 0 0 f(a) ∈ H∩U ⊆ H. SinceU +S ⊆ A, thena+f(a) ∈ Awhichcontradicts 0 the case f being an A-matching. Therefore f−1(H ∩ U) ∩ (U + S) is 0 empty. As the sets f−1(H ∩U) and U + S are both subsets of A and 0 have nothing in common, then #f−1(H ∩ U) + #(U + S) ≤ n. Thus 0 #(H∩U)+#(U +S) ≤ nandthistellsus#(H∩U)+#(S∪(S+U)) ≤ n. 0 Next, using (6) yields that #U +#S ≤ n which is a contradiction. Therefore in both cases we extract contradictions. Then there is a matching from A to B. Using Theorem 3.1, we give an alternative proof to Theorem 2.1. Assume that G is either torsion-free or cyclic of prime order. Then G has no non-trivial subgroup of finite order. This means if A,B ⊆ G with |A| = |B| and 0 6∈ B, then A is locally matched to B. Using Theorem 3.1 yields that A is matched to B and so G has matching property. 9 Conversely, assume that G is neither torsion-free nor cyclic of prime order. Then it has a non-trivial finite subgroup H. Choose g ∈ G\H and set A = H and B = H ∪ {g} \ {0}. Clearly, H ∩ B 6= ∅ and a + H ⊆ A for some a ∈ A (Indeed for any a ∈ A). If A is locally matched to B, then one can find an A-matching f from a subset A of A to H ∩B. But if a ∈ A , then 0 0 a+f(a) ∈ H +(H ∩B) = H +(H \{0}) = H = A, which is a contradiction. Then A is not locally matched to B and so by Theorem 3.1, A is not matched to B. Therefore G has no matching property. 4 The linear analogue of Losonzcy’s result on matchable subsets ThefollowingisthelinearversionofTheorem2.2whichinvestigates thematch- able subspaces in a simple field extension. Here, we say that K ⊆ L is a simple field extension if L = K(α), for some α ∈ L. Also, if B is a K-subspace of L suth that K(b) = L, for any b ∈ B \ {0}, we say that B is a primitive K-subspace of L. Theorem 8. Let K $ L be a finite and separable field extension and A and B be two n-dimensional K-subspaces in L with n ≥ 1 and B is a primitive K-subspace of L. Then A is matched with B. Proof. Assume that A is not matched to B. Using Theorem 2.3, one can find J ⊆ {1,...,n} and a basis A = {a ,...,a } of A such that 1 n a−1A∩B > n−#J. (7) i i∈J \(cid:0) (cid:1) Set S = ha : i ∈ Ji the K-subspace of A spanned by a ’s, i ∈ J, U = i i 10