The previous lecture defined the double coset $HaK$ and showed how it extends ordinary left and right cosets. We now prove the structural reason double cosets organize a group: they are equivalence classes for a natural relation. Two elements $a$ and $b$ are related when $b$ can be obtained from $a$ by multiplying on the left by an element of $H$ and on the right by an element of $K$. This relation partitions the group into double cosets. In this lecture, we prove the equivalence relation carefully and identify each equivalence class with a double coset. :::definition[Double Coset Relation] Let $(G,\circ)$ be a group and let $H$ and $K$ be subgroups of $G$. The $double coset relation$ on $G$ determined by $H$ and $K$ is the relation $\rho$ defined by $$\begin{equation*} a\rho b \iff b=h\circ a\circ k \end{equation*}$$ for some $h\in H$ and some $k\in K$. ::: :::theorem Let $(G,\circ)$ be a group and let $H$ and $K$ be subgroups of $G$. Let $\rho$ be the relation on $G$ defined by $$\begin{equation*} a\rho b \iff b=h\circ a\circ k \end{equation*}$$ for some $h\in H$ and some $k\in K$. Then $\rho$ is an equivalence relation and $$\begin{equation*} \operatorname{cl}(a)=HaK \end{equation*}$$ for every $a\in G$. ::: :::proof Given that $(G,\circ)$ is a group, $H$ and $K$ are subgroups of $G$, and $\rho$ is the relation on $G$ defined by $$\begin{equation*} a\rho b \iff b=h\circ a\circ k \end{equation*}$$ for some $h\in H$ and some $k\in K$. To prove that $\rho$ is an equivalence relation and $$\begin{equation*} \operatorname{cl}(a)=HaK \end{equation*}$$ for every $a\in G$. [1] To prove reflexivity. Let $a\in G$. Since $e\in H$ and $e\in K$, we get $$\begin{align*} a &=e\circ a\circ e. \end{align*}$$ Therefore $a\rho a$. [2] To prove symmetry. Let $a,b\in G$ and let $a\rho b$. Then there exist $h\in H$ and $k\in K$ such that $$\begin{equation*} b=h\circ a\circ k. \end{equation*}$$ Therefore $$\begin{align*} b=h\circ a\circ k &\implies h^{-1}\circ b=a\circ k\\ &\implies h^{-1}\circ b\circ k^{-1}=a\\ &\implies a=h^{-1}\circ b\circ k^{-1}. \end{align*}$$ Since $h^{-1}\in H$ and $k^{-1}\in K$, we get $b\rho a$. [3] To prove transitivity. Let $a,b,c\in G$ such that $a\rho b$ and $b\rho c$. Then there exist $h_1,h_2\in H$ and $k_1,k_2\in K$ such that $$\begin{equation*} b=h_1\circ a\circ k_1 \end{equation*}$$ and $$\begin{equation*} c=h_2\circ b\circ k_2. \end{equation*}$$ Using these equations, we get $$\begin{align*} c &=h_2\circ b\circ k_2\\ &=h_2\circ(h_1\circ a\circ k_1)\circ k_2\\ &=(h_2\circ h_1)\circ a\circ(k_1\circ k_2). \end{align*}$$ Since $h_2\circ h_1\in H$ and $k_1\circ k_2\in K$, we get $a\rho c$. Therefore $\rho$ is an equivalence relation. Now let $a\in G$. The equivalence class of $a$ is $$\begin{align*} \operatorname{cl}(a) &=\{b\in G:a\rho b\}\\ &=\{b\in G:b=h\circ a\circ k,\;h\in H,\;k\in K\}\\ &=HaK. \end{align*}$$ Hence, $\rho$ is an equivalence relation and $$\begin{equation*} \operatorname{cl}(a)=HaK \end{equation*}$$ for every $a\in G$. $\square$ ::: :::corollary Let $(G,\circ)$ be a group and let $H$ and $K$ be subgroups of $G$. Then the set of all double cosets $HaK$ forms a partition of $G$. ::: :::proof Given that $(G,\circ)$ is a group and $H,K$ are subgroups of $G$. To prove that the set of all double cosets $HaK$ forms a partition of $G$. By the previous theorem, the double cosets $HaK$ are precisely the equivalence classes of the double coset relation on $G$. Since every equivalence relation partitions its underlying set into equivalence classes, the set of all double cosets forms a partition of $G$. Hence, the set of all double cosets $HaK$ forms a partition of $G$. $\square$ ::: The double coset relation divides the whole group into equivalence classes. In the additive group $\mathbb{Z}_n$, those classes are the sets $H+a+K$ as $a$ ranges over all residues. Change $H$ and $K$ to see how several representatives can produce the same block. Each displayed block is one double coset, and together the blocks cover every element exactly once. This makes the partition statement visible rather than only symbolic. :::scientific-preview[Double Coset Partition Explorer] ::: Representatives listed in the same block determine equal double cosets. Representatives in different blocks determine disjoint double cosets, matching the equal-or-disjoint property proved next. :::corollary Let $(G,\circ)$ be a group and let $H,K$ be subgroups of $G$. If $a,b\in G$, then either $$\begin{equation*} HaK=HbK \end{equation*}$$ or $$\begin{equation*} HaK\cap HbK=\varnothing. \end{equation*}$$ ::: :::proof Given that $(G,\circ)$ is a group, $H,K$ are subgroups of $G$, and $a,b\in G$. To prove that either $$\begin{equation*} HaK=HbK \end{equation*}$$ or $$\begin{equation*} HaK\cap HbK=\varnothing. \end{equation*}$$ By the previous corollary, the double cosets form a partition of $G$. In a partition, two blocks are either equal or disjoint. Therefore the double cosets $HaK$ and $HbK$ are either equal or disjoint. Hence, either $$\begin{equation*} HaK=HbK \end{equation*}$$ or $$\begin{equation*} HaK\cap HbK=\varnothing. \end{equation*}$$ $\square$ ::: :::theorem Let $(G,\circ)$ be a group and let $H,K$ be subgroups of $G$. If $a,b\in G$, then $$\begin{equation*} HaK=HbK \end{equation*}$$ if and only if $$\begin{equation*} b\in HaK. \end{equation*}$$ ::: :::proof Given that $(G,\circ)$ is a group, $H,K$ are subgroups of $G$, and $a,b\in G$. To prove that $$\begin{equation*} HaK=HbK \iff b\in HaK. \end{equation*}$$ [1] Let $HaK=HbK$. Since $e\in H$ and $e\in K$, we get $$\begin{align*} b &=e\circ b\circ e\\ &\in HbK\\ &=HaK. \end{align*}$$ Therefore $b\in HaK$. [2] Let $b\in HaK$. Since $b\in HbK$, we get $$\begin{equation*} HaK\cap HbK\neq\varnothing. \end{equation*}$$ By the equal-or-disjoint property of double cosets, $$\begin{equation*} HaK=HbK. \end{equation*}$$ Hence, $$\begin{equation*} HaK=HbK \iff b\in HaK. \end{equation*}$$ $\square$ ::: The equality criterion says that $HaK$ and $HbK$ are equal exactly when $b$ belongs to $HaK$. Use this calculator to test the criterion in a finite modular example. Enter two representatives $a$ and $b$, then compare the two computed double cosets. When the calculator says the two sets are equal, it also confirms that the representative $b$ lies in the double coset determined by $a$. This turns the theorem into a quick membership test. :::calculator[Double Coset Equality Checker]