Why does an $n \times n$ rotation matrix have $\frac{1}{2}n(n-1)$ undetermined parameters? Consider an orthogonal transformation between Cartesian coordinate systems in $n$-dimensional space. The $n \times n$ rotation matrix 
$$R = \left(a_{ij}\right)$$ 
has $n^2$ entries. These are not independent; they are related by the orthogonality conditions
$$a_{ik}a_{jk} = \delta_{ij},$$ 
which are $\frac{1}{2}\!\!\left(n^2 + n\right)$ independent equations in the $a_{ij}$. Thus, 
$$n^2 - \frac{1}{2}\!\!\left(n^2 + n\right) = \frac{1}{2}n\left(n-1 \right)$$
of the $a_{ij}$ are left undetermined. 
Why is the last step justified? If there are $n$ independent equations, is it always possible to solve them for $n$ unknowns (even if the equations involve the sums of quadratic terms, as they do here)? If so, why? Under what general conditions is it possible to solve a system of $n$ independent equations for $n$ unknowns? 

A general rotation can be written in terms of a "rotor" in a clifford algebra.  These rotors take the form
$$q = q_0 + \sum_{i<j} q_{ij} e_i \wedge e_j, \quad q_0^2 + \sum_{i<j} q_{ij}^2 = 1$$
so that the rotation, written in terms of the geometric product, is, for any vector $a$,
$$a' = q a q^{-1}$$
The astute reader should recognize this is a generalization of quaternions.  The numbers $q_{ij}$ number $n(n-1)/2$ in total.  This is the number of degrees of freedom that characterizes the rotor $q$, for $q_0$ is determined by the normalization condition.
Interpreting the degrees of freedom of a rotation--which applies equally to a matrix that describes the rotation--is quite easy to do from this geometric perspective:  the wedge product $e_i \wedge e_j$ represents a planar subspace.  Each of the numbers $q_{ij}$ is a coefficient of a planar subspace, representing how much of the rotation involves rotation in that specified plane.
Thus, $n(n-1)/2$ comes from the fact that there are $n(n-1)/2$ linearly independent planes in an $n$-dimensional space.
