Can every group be represented by a group of matrices?
Or are there any counterexamples? Is it possible to prove this from the group axioms?
Can every group be represented by a group of matrices?
Or are there any counterexamples? Is it possible to prove this from the group axioms?
Every finite group is isomorphic to a matrix group. This is a consequence of Cayley's theorem: every group is isomorphic to a subgroup of its symmetry group. Since the symmetric group $S_n$ has a natural faithful permutation representation as the group of $n\times n$ 0-1 matrices with exactly one 1 in each row and column, it follows that every finite group is a matrix group.
However, there are infinite groups which are not matrix groups, for example, the symmetric group on an infinite set or the metaplectic group.
Note that every group can be represented non-faithfully by a group of matrices: just take the trivial representation. My answer above is for the question of whether every group has a faithful matrix representation.
It is not true that every group can be represented by a group of finite-dimensional matrices (say over $\mathbb{C}$). The groups that can are called linear. There are many examples of non-linear groups; here is a relatively simple one.
Claim: The group $(\mathbb{Z}/2\mathbb{Z})^{\infty}$ is not linear.
Proof. Suppose to the contrary that there exists a faithful representation $(\mathbb{Z}/2\mathbb{Z})^{\infty} \to \text{GL}_n(\mathbb{C})$ for some $n$. In particular, for arbitrarily large $m$, there exists a faithful representation $(\mathbb{Z}/2\mathbb{Z})^m \to \text{GL}_n(\mathbb{C})$. We can conjugate this to a representation into $U(n)$ and then simultaneously diagonalize to obtain a representation into $\mathbb{T}^n$. But the subgroup of elements of $\mathbb{T}^n$ of order $2$ is $(\mathbb{Z}/2\mathbb{Z})^n$, so the representation cannot be faithful if $m > n$; contradiction.
For finite groups, the answer is yes: every finite group is isomorphic to a subgroup of $Gl(n)$ for some $n$ large enough. In fact, we can do slightly better and embed it into $SO(n)$ for $n$ large enough.
The idea: Every group acts on itself, by, say, left translations. This gives an embedding $G\rightarrow S_{|G|}$ into the symmetric group on $|G|$ letters. Hence, every group is a subgroup of some $S_k$ for $k$ large enough.
Thus, we just need to show that we can embed every $S_n$ into $GL_n$ for $n$ large enough. But $S_n$ acts on $\mathbb{R}^{n}$ by permuting the coordinates. It's easy to see that this action is linear, hence defines an embedding $S_n\rightarrow GL(n)$.
If you insist on positive determinant, one can include $GL(n)$ into $Gl(n+1)$ sending a matrix $A$ to $\operatorname{diag}(A, \operatorname{sign}(\det(A)))$.
Finally, to embed orthogonally, pick your favorite inner product $\langle, \rangle$ on $\mathbb{R}^n$ and define $\langle x, y\rangle_1 = \sum_{g\in G} \langle g(x),g(y)\rangle$. It's easy to see that this new metric is $G$ invariant, so $G$ acts by isometries in this metric, hence, $G$ embeds into $SO(n)$ for $n$ large enough.
The story for infinite groups is more complicated. Of course, there are groups of any preassigned cardinality, while any subset of $Gl(n)$ can have cardinality at most that of the real numbers. So, no sufficiently large group can embed into $Gl(n)$.
If you mix a bit of topology, then, for example, every compact Lie group embeds into $SO(n)$ for $n$ large enough, but the proof is not trivial. Noncompact Lie groups need not embed into $GL_(n)$ for any $n$. For example, I believe that the universal cover of $Sl(2)$ is such an example.
Finitely generated linear groups are residually finite. Although this is a deep result, it allows you to conjure up non-linear groups willy-nilly.
For example, groups which are non-Hopfian are not linear. A good example of such a group is the Baumslag-Solitar group $BS(2, 3)\cong \langle a, t; t^{-1}a^2t=a^3\rangle.$ This group is not Hopfian (that is to say, there exists a surjective endomorphism which is not injective). For a proof, see Magnus, Karrass and Solitar, "Combinatorial Group Theory". It is well-known, and can be found in your favourite graduate group-theory text, or in this Math.SE answer, that finitely generated, residually finite groups are Hopfian. Thus, finitely generated, non-Hopfian groups are not residually finite and so not linear.
The question you are now asking is, of course, "are all finitely generated residually finite groups linear?". Well...no. There is a paper of Cornelia Drutu and Mark Sapir, where they prove that the group $\langle a, t; a^{(t^2)}=a^2\rangle$ is residually finite but non-linear.
Your question is slightly vague, but...this paper discusses groups which are counter-linear: a group $G$ is counter-linear if for every field $K$ and every positive integer $n$ the only homomorphism $G \rightarrow \operatorname{GL}_n(K)$ is the trivial homomorphism. In particular, counter-linear groups exist! examples of counter-linear groups are given. (See also Jack Schmidt's comment below.)
In group theory one often says that a group is linear over a field $K$ if it admits a faithful $n$-dimensional $K$-representation, i.e., an injective homomorphism $\rho: G \hookrightarrow \operatorname{GL}_n(K)$, for some positive integer $n$. In particular counter-linear groups are not linear over any field, but it is easier to give examples of the latter. For instance, Qiaochu's group $(\mathbb{Z}/2\mathbb{Z})^{\infty}$ is not linear over any field. I feel like I gave a similar answer on MO at one point, but I just searched unsuccessfully for it. Oh, well. Anyway, an argument for the general case can be obtained by counting conjugacy classes of involutions in $\operatorname{GL}_n(K)$: this is a good linear algebra exercise.
Note that if you allow "infinite dimensional matrices" then the answer might be different. For instance if we just ask whether every group can be embedded in $\operatorname{Aut}_k(V)$ for some (possibly infinite-dimensional) vector space over a field $k$, then the answer is clearly yes, over any field $k$: this follows from Cayley's theorem upon identifying permutations of $G$ with linear maps of the $k$-vector space with basis $G$.
There are many groups which have infinite number of elements. Then of course you can't represent them with a finite bunch of stored matrices. For example the group of 2D rotations over real valued 2D vectors. But you can sometimes get arbitrarily close by using only one or a few matrices and natural numbers as exponents.
$R_\theta = \begin{bmatrix}\cos(\theta)&\sin(\theta)\\-\sin(\theta)&\cos(\theta)\end{bmatrix}$
Now choose $\theta = \epsilon = 2\pi\cdot 2^{-n}>0$
${R_\theta} ^{2^n} = I$
Given some measure of closeness, we can go on to prove we can get arbitrarily close to any element in the group if we just allow $n$ and matrix-exponents (integers) be large enough. In the example above we have in some sense a "resolution" of $n$ bits. But it's real convenient to just have to consider one "building block" $R_\theta$ and it's exponents and not try to store all possible elements separately.
( We would quickly run out of memory if we tried for any infinite group )