How do we know that group representations exist? Given a finite group $G$, how do we know that there exists a map $\rho: G \rightarrow GL(V)$ such that $\rho(g_1\circ g_2) = \rho(g_1).\rho(g_2)$ for any $g_1, g_2\in G$?
Intuitively, why does matrix multiplication always capture the properties of a group?
 A: Let $G$ be any finite group. We can form a free vector space on the group $G$ by $k[G]$. That is, we define a basis $\{e_g\}_{g\in G}$. Now, we can define a linear action of $G$ on $k[G]$ by left translation. That is, let $g\in G$ act on the left by $g\cdot e_h=e_{gh}$ for all $g,h\in G$. We extend this by linearity to a linear map $T_g:k[G]\to k[G]$. It is not hard to see that $g\mapsto T_g$ defines a group homomorphism $G\to \text{GL}(k[G])$.
Indeed, $T_g\circ T_{g'}(e_h)=e_{gg'h}=T_{gg'}(e_h).$ This formula also shows that $T_{g^{-1}}=T_g^{-1}$ so that the $T_g$ are linear isomorphisms.
A: Permutation matrices fully capture the essential features of the symmetric groups. So for $S_n$ I would take all of the $n!$ permutation matrices of size $n \times n$ and this allows me to ensure any finite group can be represented by matrices this way. Since all groups are subgroups of symmetric groups this allows us to realize the group structure for an arbitrary finite group.
This is however almost never the minimal representation so while it ensures existence we're typically interested in finding the lowest possible dimensional representation, not an arbitrary one. You can see this immediately as $S_3$ only requires a two dimensional representation being isomorphic to $D_6$.
