The Most Important Proofs in Prelims Algebra

• [[Course - Linear Algebra I MT22]]^U
• [[Course - Linear Algebra II HT23]]^U
• [[Course - Groups and Group Actions HT23]]^U
• [[Course - Groups and Group Actions TT23]]^U

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 $ \vert \vert v + tw \vert \vert = 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]]^U
• 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) \vert L$ and $L \vert 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 \vert mn$ and $mn \vert 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]]^U
• 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]]^U
• 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 $ \vert H \vert $. 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]]^U
• 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]]^U
• 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]]^U
• 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]]^U
• 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

• [[Notes - Groups TT23, Cayley’s theorem]]^U
• 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]]^U

Cayley’s theorem

• Apply the above theorem to $G$ acting on itself by left multiplication.