Mastering Finite Fields and Combinatorics: A Guide to MATH 2130 Homework 1

Introduction to MATH 2130 Further Linear Algebra and Discrete Mathematics

Welcome to this comprehensive tutorial designed to help you tackle the key concepts in MATH 2130 Homework 1. Whether you’re wrestling with finite fields like F7, proving vector space axioms, or counting passwords and dice rolls, we’ve got you covered. This guide will break down each problem type with step-by-step reasoning, using timely examples from gaming, AI, and sports to make abstract ideas stick. By the end, you’ll be ready to submit a top-notch assignment on Gradescope.

1. Finite Fields: Arithmetic in F7

Finite fields are algebraic structures with a finite number of elements. The field F7 has elements {0,1,2,3,4,5,6} with addition and multiplication modulo 7. Think of it like a 7-day week cycle – every operation wraps around after 7. This is similar to how AI algorithms use modular arithmetic for hashing and cryptography.

(a) Finding -3 in F7

In any field, the additive inverse of an element a is the element b such that a + b = 0. In F7, -3 satisfies 3 + (-3) ≡ 0 mod 7. Since 3 + 4 = 7 ≡ 0, we have -3 = 4. So in F7, -3 is 4.

(b) Finding 4⁻¹ in F7

The multiplicative inverse of 4 is the element x such that 4·x ≡ 1 mod 7. Check multiples: 4·2=8≡1, so 4⁻¹ = 2. This is like finding the reciprocal in a modular world – essential for cryptocurrency and secure communications.

(c) Solving x² + 4x + 3 = 0 in F7

We need x such that x² + 4x + 3 ≡ 0 mod 7. Test x=0..6: x=0→3≠0, x=1→1+4+3=8≡1, x=2→4+8+3=15≡1, x=3→9+12+3=24≡3, x=4→16+16+3=35≡0, x=5→25+20+3=48≡6, x=6→36+24+3=63≡0. So solutions are x=4 and x=6. This is analogous to finding roots of a quadratic in a finite field, used in error-correcting codes for streaming and QR codes.

2. Vector Spaces: M₂×₂(F) Axioms

Proving that the set of 2×2 matrices over a field F with usual addition and scalar multiplication forms a vector space requires checking all eight axioms. This is like verifying that a gaming leaderboard (matrix of player scores) behaves linearly under scaling and addition. Key properties used: commutativity and associativity of addition in F, distributivity of multiplication over addition, etc. For example, the additive identity is the zero matrix, and the additive inverse of a matrix is its negative (each entry negative). The scalar multiplication identity uses the field’s 1. This exercise reinforces how linear algebra underpins machine learning models.

3. Subspace Tests: Real-World Examples

A subset W of a vector space V is a subspace if it contains the zero vector, is closed under addition and scalar multiplication. Let’s test each set.

(a) {(x,y,z) ∈ R³ : x + 14y + 4z = 0}

This is a plane through the origin, so it’s a subspace. Zero vector satisfies equation. If (x1,y1,z1) and (x2,y2,z2) satisfy, then their sum satisfies (x1+x2)+14(y1+y2)+4(z1+z2)=0+0=0. Scalar multiplication works similarly. This is like a budget constraint in finance where total cost equals zero.

(b) {(x,y,z) ∈ R³ : x + 14y + 4z = 28}

This plane does not contain the origin (0+0+0=0≠28), so it fails the zero vector test. Not a subspace. Think of a fixed cost line in economics – not a subspace because it doesn’t pass through zero.

(c) {(x,y) ∈ R² : x² = y²}

This set includes points where x=y or x=-y. It contains (0,0). But check closure: (1,1) and (1,-1) are in the set, but their sum (2,0) gives 2²=4 ≠ 0²=0, so not closed under addition. Hence not a subspace. This is like a symmetry condition that fails linearity.

(d) {(a,b) ∈ F₂² : a·a + b = 0}

In F₂, elements are 0 and 1. a·a = a² = a because 0²=0, 1²=1. So condition becomes a+b=0, i.e., b = a (since in F₂, 0+0=0, 1+1=0). So set = {(0,0), (1,1)}. Contains zero, but check addition: (1,1)+(1,1)=(0,0) which is in set, but (1,1)+(0,0)=(1,1) okay. However, scalar multiplication by 0 gives (0,0), by 1 gives same. This set is actually a subspace? Wait, need closure under addition: (1,1)+(1,1)=(0,0) works. But is (1,1)+(0,0) = (1,1) works. The only nontrivial sum is (1,1)+(1,1)=(0,0). So it’s closed. But check if it’s a subspace: it’s the line y=x in F₂², which is a 1-dimensional subspace. So yes, it is a subspace. However, the original condition a·a+b=0 reduces to a+b=0, so b=a. That’s a subspace. So answer: yes.

4. Union of Subspaces

Prove that U ∪ W is a subspace iff one is contained in the other. This is a classic result. If U ⊆ W, then U∪W=W, which is a subspace. Conversely, if U∪W is a subspace but neither is subset of the other, pick u∈U\W and w∈W\U. Then u+w must be in U∪W. If u+w ∈ U, then w = (u+w)-u ∈ U, contradiction. Similarly if in W. So one must contain the other. This is like team sports where two teams’ union is only a team if one team is a subset of the other.

5. Dice Probability: At Least Three Odds and At Least Two Evens

Roll a fair 6-sided die 7 times. We want probability that number of odd rolls ≥ 3 and number of even rolls ≥ 2. Since total rolls=7, the complement is easier: count outcomes with fewer than 3 odds OR fewer than 2 evens. Use binomial distribution. Let X = #odds. X~Bin(7, 0.5). P(X≥3 and X≤5) because evens=7-X≥2 implies X≤5. So we need P(3≤X≤5). Compute: P(X=3)=C(7,3)/2^7=35/128, P(X=4)=35/128, P(X=5)=21/128. Sum = (35+35+21)/128=91/128 ≈ 0.7109. This probability is like the chance that a basketball player makes at least 3 out of 7 free throws with 50% accuracy, with at least 2 misses.

6. Tabulating Die Rolls: Counting Tables

Roll a die 7 times and count frequencies of each face (1-6). The table is a 6-tuple (n1,...,n6) with sum=7, each ni≥0.

(a) Number of possible tables

This is number of nonnegative integer solutions to n1+...+n6=7: C(7+6-1,6-1)=C(12,5)=792. This is like distributing 7 identical candies among 6 children.

(b) Tables with zero 7s, zero 6s, zero 0s

“Zero 7s as totals” – but totals are frequencies, so “zero 7s” means no face appears 7 times? Actually the table entries are counts, so “zero 7s” means no entry equals 7. Since sum=7, the only way to have a 7 is if one face appears all 7 times. There are 6 such tables (all rolls same face). So tables with zero 7s = 792 - 6 = 786. “Zero 6s” means no entry equals 6. If a face appears 6 times, the remaining 1 roll must be some other face. Number of tables with at least one 6: choose face for 6 (6 ways), choose the remaining face (5 ways) and the remaining roll is that face, so 6*5=30 tables? But careful: tables with two 6s? Not possible because sum would exceed 7. So exactly 30 tables have a 6. So tables with zero 6s = 792 - 30 = 762. “Zero 0s” means every face appears at least once. Since there are 6 faces and 7 rolls, one face appears twice, others once. Number of ways: choose which face appears twice (6 ways), then arrange? Actually the table is determined by counts: one 2 and five 1s. So number = 6. So tables with zero 0s = 6.

7. Password Counting

Password length 10: three uppercase letters (26 choices each), three lowercase (26 each), four digits (10 each). Also need to consider arrangement? The problem says “consisting of” implying the positions are fixed? Usually such problems mean the password contains exactly those types, but the order can be any. However, the wording “consisting of” might imply the characters are in that order: first three uppercase, then three lowercase, then four digits. That is typical for such problems. So number = 26^3 * 26^3 * 10^4 = 26^6 * 10^4 = 308,915,776 * 10,000 = 3,089,157,760,000. If order is arbitrary, it’s multinomial: 10!/(3!3!4!) * 26^3 * 26^3 * 10^4. But given the context, we assume fixed order. This is like creating a strong password for an online banking account.

8. Inclusion-Exclusion: Numbers Not Divisible by 2,3,5

Find integers from 1 to 10,000 not divisible by 2, 3, or 5. Use inclusion-exclusion. Let A2, A3, A5 be sets divisible by 2,3,5. |A2|=floor(10000/2)=5000, |A3|=3333, |A5|=2000. Intersections: |A2∩A3|=floor(10000/6)=1666, |A2∩A5|=1000, |A3∩A5|=666, |A2∩A3∩A5|=floor(10000/30)=333. Then |A2∪A3∪A5| = 5000+3333+2000 - (1666+1000+666) + 333 = 10333 - 3332 + 333 = 7334. So numbers not divisible by any = 10000 - 7334 = 2666. This is like finding prime candidates in a range, relevant to cryptography.

Conclusion

By mastering these problems, you’ve built a solid foundation in linear algebra and discrete mathematics. Remember to justify every step using field axioms, vector space properties, and combinatorial principles. Good luck with your submission!