# The Most Important Proofs in Prelims Algebra

> Source: https://ollybritton.com/notes/uni/prelims/ht23/groups/important-proofs/ · Updated: 2023-05-31 · Tags: uni, notes

- [Course - Linear Algebra MT22](https://ollybritton.com/notes/uni/prelims/mt22/linear-algebra/)
- [Course - Linear Algebra II HT23](https://ollybritton.com/notes/uni/prelims/ht23/linear-algebra/)
- [Course - Groups and Group Actions HT23](https://ollybritton.com/notes/uni/prelims/ht23/groups/)
- [Course - Groups and Group Actions TT23](https://ollybritton.com/notes/uni/prelims/tt23/groups/)

### Linear Algebra I
#### Steinitz exchange lemma
- Consider two different ways of writing a vector in the span
- Can just rearrange both

#### The dimension formula
- i.e. $\dim(U \cap W) + \dim(U + W) = \dim(U) + \dim(W)$
- Consider a basis of $V \cap W$ and then seperately extend to a basis of $V$ and $W$.
- Then show that the basis with both extensions is a basis of $V+W$.
- Can show it’s spanning, but to show it’s linearly independent you need to note that any vector in $U + W$ must also be in $U \cap W$ by rearranging both sides of the equation.
- Then linear independence follows from the linear independence of the other two bases.

#### The rank-nullity theorem
- Consider a basis for kernel, extend to a basis of the input vector space.
- Then show that the non-kernel bits of the input vector space form a basis for the image.

#### Change of basis theorem ($\ast$)
- Apply definitions. Consider $U, V, W$ as finite-dimensional vector spaces with ordered bases $\mathcal{U, V, W}$. Then write each $S(u_i)$ or $T(v_i)$ as a sum.
- Rearrange sum to notice the hidden matrix multiplication and then result follows.

#### Row rank and column rank are equal
- Make the long line of equalities $\text{rowrank(A) = rowrank(R) = colrank(R) = colrank(A)}$.
- First equality comes from fiddling around with the definition, and using the fact that if $A = ER$ then $E$ is invertible.
- Second equality comes from considering non-zero rows and columns in the RREF.
- Final equality comes from a combination of two things: noting that the kernel of both $A$ and $R$ must be the same and then using the rank-nullity theorem.

#### Cauchy-Schwarz inequality
- All follows from expression $\langle v + tw, v + tw \rangle$. This must be positive as it’s an inner product, and then you get a quadratic in $t$ that you take the discriminant of.
- For equality, it must be the case that $\langle v + tw, v + tw\rangle = 0$, which implies $||v + tw|| = 0$, which itself means that $v = -tw$, and so they are linearly dependent.

#### Rank and nullity of composition of linear maps ($\ast$)
- [Notes - Linear Algebra I MT22, Rank and nullity inequalities](https://ollybritton.com/notes/uni/prelims/mt22/linear-algebra/notes/rank-and-nullity-inequalities/)
- Tackle the rank part by first showing the image of the composition must be a subset of the image of the “outer” linear map, and then applying the rank-nullity theorem to the restriction for the second part.

### Linear Algebra II
#### Multiplicativity of determinant
- Show that the determinant is multiplicative with respect to elementary row operations
- Then any matrix can be written as a product of elementary row operations

#### Eigenvectors are linearly independent
- Argue by contradiction, consider a minimum set of linearly dependent and then apply a transformation to both sides that keeps them as zero.

#### Geometric multiplicity less than algebraic multiplicity
- Maybe worth going over at least once again.
- Consider the matrix with respect to the basis beginning with the basis for its eigenspace beginning with that particular eigenvalue.

#### Symmetric matrices have real eigenvalues
- Rearrange something in two different ways

#### Symmetric matrices are diagonalisable (Spectral theorem)
- Went over recently
- Quite involved, with lots of magically constructing things
- But main idea is by induction on the dimension of the matrix
- Since you know that the block matrix inside $P^\intercal A P$ will also be real symmetric

### Groups I
#### Permutations as products of disjoint cycles
- Explain that you can tackle a cycle at a time by exhausting all particular elements of that cycle.

#### Order of permutation is LCM of cycle types
- One of the proofs where you show $o(g) = L$ by $o(g) | L$ and $L | o(g)$.
- Made a lot easier by clean notation: let $\pi$ be the permutation, and say it consists of disjoint cycles $s_1, \ldots, s_r$ with orders $k_1, \ldots, k_r$.

#### Conjugate iff same cycle type ($\ast$)
- Forward: note that the conjugation is distributive over the disjoint cycles
- Backward: set up a permutation between each disjoint cycle

#### Subgroups of cyclic groups are cyclic
- Follows from defining $n = \min\{k > 0 : g^k \in H\}$ and then for any $g^a \in H$, considering $a = qn + r$, and rearranging to see that $r = 0$.

#### Chinese remainder theorem
- Consider the order of the generator $(g, h)$ where $g$ and $h$ are generators for $C_m$ and $C_n$ respectively.
- Then show $k | mn$ and $mn | k$, using Bezout’s lemma for the last step.

#### Equivalence classes form a partition
- Partitions are a collection of disjoint sets whose union is the entire set.
- Show equivalence classes satisfy this definition.

#### Coset equality lemma
- [Notes - Groups HT23, Cosets](https://ollybritton.com/notes/uni/prelims/ht23/groups/notes/cosets/)
- Suppose $u \in gH = kH$. Write in two different ways, and you end up getting something like $gh_1 = kh_2$ which implies the forward direction.
- For the backward direction, note that then $k = gh$, so $kH = g(hH) = gH$.

#### Lagrange’s theorem
- [Notes - Groups HT23, Lagrange’s theorem](https://ollybritton.com/notes/uni/prelims/ht23/groups/notes/lagranges-theorem/)
- Consider the equivalence relation given by two elements having the same left coset.
- Can show this is a partition by showing that if two left cosets are not disjoint, then they are the same.
- Finally need to show each coset has the same number of elements as $|H|$. Can do this by showing that $h \mapsto gh$ is a bijection.

#### Fermat’s theorem
- Just the size of the multiplicative group, a consequence of Lagrange’s theorem

#### Euler’s theorem
- Just the size of the multiplicative group, another consequence of Lagrange’s theorem

#### Every group with even order has element of order 2
- Consider pairing up elements with their inverses

#### Groups II
#### Kernel of a homomorphism is a normal subgroup
- [Notes - Groups HT23, Homomorphisms](https://ollybritton.com/notes/uni/prelims/ht23/groups/notes/homomorphisms/)
- Show that $g^{-1}hg \in \ker \phi$ for all $h \in \ker \phi$ and $g\in G$.

#### Equivalence in normal subgroup definition
- What did I mean by this??

#### First isomorphism theorem
- [Notes - Groups TT23, First isomorphism theorem](https://ollybritton.com/notes/uni/prelims/tt23/groups/notes/first-isomorphism-theorem/)
- Consider isomorphism $f: G/\text{ker} \phi \to \text{Im } f$ given by $f(g\ker \phi) = \phi(g)$. Then apply definitions.

#### Orbits form a partition
- [Notes - Groups TT23, Orbits and stabilisers](https://ollybritton.com/notes/uni/prelims/tt23/groups/notes/orbits-and-stabilisers/)
- Consider the equivalence relation $x \sim y \iff \exists g \in G \text{ s.t. } g\cdot x = y$.

#### Orbit-stabilizer theorem
- Consider bijection between $G/\text{Stab}(x)$ and $\text{Orb}(x)$ given by $g \text{Stab}(x) \mapsto g \cdot x$. Surjective as we can pick any $g$, and then injective by considering the coset equality lemma.

#### Orbit counting formula
- [Notes - Groups TT23, Counting orbits](https://ollybritton.com/notes/uni/prelims/tt23/groups/notes/counting-orbits/)
- Consider $A = \\{(g, s): g \cdot s = s\\}$.
- Two different ways of summing it up, either over $g \in G$ or over $s \in S$.
- The $s \in S$ way can be manipulated in order to make it talk about orbits, and then you set the two equal to eachother.

#### Left actions and homomorphisms to symmetry groups are samish
- [Lecture - Groups TT23, Cayley’s theorem](https://ollybritton.com/notes/uni/prelims/ht23/groups/lectures/theorem/)
- Show that the definition of $\rho$ corresponds to a homomorphism.
- Show that given a homomorphism, you can construct a group action.

### Cauchy’s theorem
- [Notes - Groups TT23, Cauchy’s theorem](https://ollybritton.com/notes/uni/prelims/tt23/groups/notes/cauchys-theorem/)

#### Cayley’s theorem
- Apply the above theorem to $G$ acting on itself by left multiplication.

---
Olly Britton — https://ollybritton.com. Machine-readable index: https://ollybritton.com/llms.txt