- Fri 02 May 2014
- Maths
- #combinatorics, #graph theory
Consider \(N\) distinct points \(P_{1}\), \(P_{2}\), ..., \(P_{N}\) with coordinates \(x_{1}\), \(x_{2}\), ..., \(x_{N}\). One can draw \(N^{2}\) lines connecting these \(N\) points. If we ommit lines that connect a point to itself, then we have \(N(N-1)/2\) possible distinct lines. Out of these, \(N\) can be regarded as external lines (corresponding to the edges of a convex polygonal perimeter connecting the \(N\) points) and \(N(N - 3)/2\) can be regarded as internal lines (the lines inside the perimeter).
We start with \(N\) distinct position variables. One can imagine making a change of variables
where \(X\) describes the center-of-mass position of the system, and the \(x_{ij}\) variables represent a set of \(N - 1\) independent coordinate differences \(x_{ij} \equiv x_{i} - x_{j}\). One can construct more than \(N - 1\) coordinate differences, but it is only possible to have \(N - 1\) linearly independent ones. Indeed, one can write
which can be rewritten as
So if we want to keep all possible \(N(N-1)/2\) coordinate differences available, we need to introduce \((N-2)(N-1)/2\) auxilliary variables (i.e. Lagrange multipliers) that enforce the linear constraints that leave only \(N-1\) linearly-independent ones.