Rotation vs translation

What is so fundamentally different between a rotation and a translation that one can be represented with a single n-vector and the other one needs an n-n matrix?

Answer

Both are Euclidean isometries (distance and global-shape preserving maps): the only other kind of Euclidean isometry is a reflexion, although this last one is "discrete" - you can't have a fraction of a reflexion, whereas you can have a fraction $\alpha$ of a translation or rotation: you translate $\alpha$ times as far or rotate through $\alpha$ times a given angle. So the two transformations you mention are the only continuous Euclidean isometries.

What's fundamentally different? Translations commute. Rotations do not. This means that for two translations $T_1,\,T_2$ the order of application does not matter: the resultant is the same whichever way around you choose, i.e. $T_1\,T_2 = T_2\,T_1$. This does not hold for rotations: draw some marks on an orange and check this yourself if you haven't noticed this before. Aside from for rotations about the same axis, $R_1\,R_2 \neq R_2\,R_1$.

All groups (look this word up if you haven't met it) of continuous symmetries that are Abelian ( i.e. groups of symmetries that commute - for which the order does not matter) can be shown to be essentially the same (isomorphic) to either (1) a space of vectors kitted with vector addition or (2) a torus whose surface is labelled orthogonal Cartesian co-ordinates and which behaves essentially the same as a vector space of adding arrows. The only difference in the latter, torus group is that if you translate far enough in a given direction, you can get back to your beginning point. Otherwise the torus group looks exactly like a space of vectors. So you can take this as your fundamental informal reason: any commuting Lie group looks either exactly like a space of vectors, or a "compactified" one that behaves the same aside from one's being able to get back to one's beginning point by a far enough translation in any direction.

Another pithy characterisation is CuriousOne's comment:

A translation affects only one coordinate direction, a rotation affects two. An infinitesimal translation needs one vector, an infinitesimal rotation needs two. Maybe the better way to think about comparing these operations is with their generators than the matrices and vectors? I am sure a theorist can chime in with a better answer regarding the representation theory of Lie-groups.

Some background: in higher dimensions, rotations rotate 2D planes and leave the orthogonal complement of a plane invariant. This is what CuriousOne means by "rotation affects two". The axis concept only works in 3 dimensions: you can define a plane in 3 dimensions as the 2D subspace normal to a vector (in two dimensions you rotate about a point). So, in 3D with a vector's direction standing for the axis and its magnitude standing for the angle, you can indeed represent a rotation by a lone vector. There is even a triangle law for vector addition of rotations, but it is somewhat more involved than addition of translations. Nonetheless, it may surprise you just the same: see the discussion under the heading "Example 1.4: ($2\times 2$ Unitary Group $SU(2)$)" on this page of my website here. Another way of saying this is as David Hammen points out: The axis concept's being workable in 3D is an "accident" of dimension: in $N$ dimensions, a rotation is of the form $e^H$ where $H$ is a real $N\times N$ skew-symmetric ($H=-H^T$: equal to the negative of its transpose) matrix and thus $H$ must have noughts along its leading diagonal and its lower, below leading diagonal triangle is simply the upper, above leading diagonal triangle reflected. There are thus $N\,(N-1)/2$ real parameters needed to specify the rotation, which just happens to be equal to $N$ when $N=3$.

Lastly, one should mention the special relationship between translations and rotations. The translations are special insofar that for any isometry $U$ and translation $T$ we have $U\,T\,U^{-1} = T_1$, where $T_1$ is another translation (not needfully the same as $T$). The technical name for this is that the translations form a normal subgroup of the group of isometries; what this means is that any isometry can be uniquely decomposed into the form $T\,R$, where $T$ is a translation and $R$ a rotation: we say that the isometry group $E(N)$ is the semidirect product (written $E(N)=T(N)\rtimes R(N)$) of the group $T(N)$ of translations and $R(N)$ of rotations).

I should add that, in higher dimensions, I use the word "rotation" more loosely than many authors: I simply mean any homogeneous transformation whose matrix is of the form $e^H$ with $H$ skew symmetric. Many authors split these up into further different classes.