Significance of difference using a distance matrix So my data consists of a distance matrix for some points, and a table classifying the points as either red or green. I want to know if there is any difference between the red and green points. I did UPGMA clustering and they don't look different (doesn't seem to be any tendency for red or green to cluster together) but I don't know how to express the significance of this.
I guess the question would be something like "what is the chance of getting a distance matrix like this, if the points were all randomly distributed".
 A: Here is a simple solution that should give you a taste of how to solve the problem. Whether this solution is satisfactory would depend on your actual application. 
If you want to determine how usual or unusual your distance matrix is compared to other arrangements of the points then you can use the following approach. You will need a measure of how well any set of red and green points are clustered. A very simple metric would be as follows. 
Initialise the metric to zero.
Foreach data point
    If the nearest neighbour of a point is in a different group (ie different colour) then add this distance to the metric.  

Now, you can label the data points randomly with red or green and work out the metric for a random labelling.
Repeat this random labelling many times and record the metric each time, allowing you to determine distribution statistics for the metric.
You can also calculate the metric for your actual set of data points and compare this to the distribution of metric data.
Some things to note. If you have two tightly clustered groups that are well separated then the metric would be zero....ie all neighbours belong to the same group.
The metric can be as simple as I described or more complex, depending on the application of the results. This sort of random reladelling is common. If you have a relatively small number of points you could work out the metric for all possible permutations.
You can find more on this topic here http://en.wikipedia.org/wiki/Resampling_(statistics)
A: You could use point-biserial correlation (and its significance) between variable "distance" and binary variable "points are different colour (1) vs both points are same colour (1)". This will give you numerical impression of whether points of the same colour tend to cluster together according to the distances.
A: For each object, sort the other objects by their distance, compute the ROC curve with respect to the objects class and the area under this curve. If the distance matrix is helpful, the value should be significantly closer to 1.0 than to 0.5
A: Use a permutation test:


*

*Calculate your distance metric 

*Randomly shuffle the red/green status of the points 

*Recalculate the distance metric on the shuffled points

*Repeate steps 2 and 3 a bunch of times (1999 or 9999 would be good)

*Compare the metric for the original data to the metrics from the permuted metrics.

A: Another option is adonis, in the R package vegan.
From the docs:

adonis is a function for the analysis and partitioning sums of squares using semimetric and metric distance matrices. Insofar as it partitions sums of squares of a multivariate data set, it is directly analogous to MANOVA (multivariate analysis of variance). M.J. Anderson (McArdle and Anderson 2001, Anderson 2001) refers to the method as “permutational manova” (formerly “nonparametric manova”). Further, as its inputs are linear predictors, and a response matrix of an arbitrary number of columns (2 to millions), it is a robust alternative to both parametric MANOVA and to ordination methods for describing how variation is attributed to different experimental treatments or uncontrolled covariates. It is also analogous to redundancy analysis (Legendre and Anderson 1999).

