Suppose I have a set of N objects, {a,b,c,d,e,...}, and an NxN matrix whose values are the overlap (in length, area, volume, etc) of each pair of objects. With this matrix, can I recover the ordering of the bounds of the objects?
For example, suppose that the objects are intervals, each with an upper and a lower bound. The diagonal values of the matrix will be the length of each interval, and the off-diagonal values will be the length of the intersection of each pair of intervals. The matrix must then be symmetric. Let's call it the intersection matrix.
It seems to me that, at least for 1D objects, such a matrix captures all the information necessary to establish the ordering of the bounds of the objects. If an off-diagonal cell {a,b}=0, this means that the two objects do not overlap, i.e. the upper and lower bounds of a are both either higher or lower than the bounds of b. If {a,b}={a,a}, this means that a's bounds are contained within b. If 0 < {a,b} <{a,a}, then one (but not both) of a's bounds are between b's bounds. All the cells of the matrix then give a set of constraints that would order all the bounds of the N objects (at least in 1D).
Not all symmetric matrices could be interpreted in this way, e.g. if {a,b}>{a,a} cannot be true in an intersection matrix (probably there are other rules). This and the symmetry property are reminiscent of a covariance matrix.
Now suppose I have a matrix that I think might reflect a set of intersecting objects - is there a tool that tells me 1) if the matrix is a valid intersection matrix, 2) what are the valid orderings of the bounds, and 3) what is the dimensionality of the set?
I can easily imagine an algorithmic solution (e.g. fitting a set of bounds to a matrix or some kind of Gaussian mixture model) but I would like to know if there is a mathematical solution/description for this problem.
Thanks!
(edit: if there are possibly more appropriate flags for this question please let me know!)
You have nothing that indicates the direction of intersection. For example, if $a=(0,4), b=(3,5)$ you have the matrix $\begin {pmatrix} 4&1\\1&2 \end {pmatrix}$, but $b$ could be $(-1,1)$ just as well and give the same matrix. If you have groups of intervals that do not intersect there is nothing to indicate the order at all. For example, if $a=(0,4), b=(3,5), c=(10,11)$ you have the matrix $\begin {pmatrix} 4&1&0\\1&2&0\\0&0&1 \end {pmatrix}$ and you can't position $c$ with respect to $a,b$. If you have 2D objects, even if they are all rectangles, I have no idea what your matrix should look like.