For example, let's say I have 3 objects $o_1, o_2, o_3$ and I am given that $o_2$ is 1 more than $o_1$, and $o_3$ is 2 less than $o_1$. I am given this information in the form of an incomplete matrix $A$ where $A(i,j) =$ the relative difference in size of $o_j$ from $o_i$:
$A = \begin{bmatrix} 0 & 1 & -2\\ & 0 & r \\ & & 0 \end{bmatrix} $
This is a very simple example and it is clear that $r=-1$.
But how can I efficiently solve this problem given that the matrix may be very large and sparse?
Thank you for you help.
First, it should be skew symmetric;
$$\sigma_j - \sigma_i = A(i, j) = -A(j, i) = -(\sigma_i - \sigma_j),$$ which means you'll only need to figure out at most $\frac{(n-1)(n-2)}{2}$ of the entries. That seems like good news, as the time should be at most quadratic, if that's efficient enough.
Now, the trickier part, filling in all the $A(i, j)$ given only some values. You'll certainly need at least $n-1$ entries to begin with, but they can't just be relations between a subset of your $\sigma_k$; every $\sigma_k$ needs to be involved in at least one relation. Hopefully that's taken care of, by wherever you get your values.
OK, so on to the math. In your example, you correctly said that $r = A(2, 3) = -1$.
This is because $$A(2, 3) = \sigma_3 - \sigma_2 = (\sigma_3 -\sigma_1) + (\sigma_1 - \sigma_2) = A(3, 1) + A(2, 3) = -2 + 1;$$
that is, if we can compare $\sigma_2$ to $\sigma_3$ if we've already compared them both to some intermediate $\sigma_k$, in this case, $ \sigma_1$.
So, my algorithm would do something like this.
1) Confirm that at least one of $A(k, \_)$ or $A(\_,k)$ is filled in for each $k$, and make sure that you've set $A(j, i) = -A(i, j)$ if you were given $A(i, j)$.
2) Create a list, $L$, of all pairs $(i, j)$ for which $A(i, j)$ is unknown.
3) Now comes iteration (sheesh, this is sounding less efficient as I write it!). For each $(i, k) \in L$, see if there exists some $j$ such that $A(i, j)$ and $A(j, k)$ are both known, in which case set $A(i, k) = A(i, j) + A(j, k)$ (and remember that it's skew symmetric, so set $A(j, i) = -A(i, j) $too).
4) Iterate step 3 until L is empty, it will lead to a complete solution, as long as each $\sigma_k$ was compared to some other $\sigma_k$, and you start off with at least $n - 1$ comparisons.
I'm making no claims that this is as efficient as possible, but it should at least be something that gets the job done in polynomial time. Hopefully someone else will have a better answer if one exists.