The problem can be reinterpreted as a pure math problem of linear space projection.

Consider each person's ID as an index and a transaction `[i, j, y]`

as number y_{i,j}, then we can form an NxN matrix **Y** = (y_{i,j}), which has property that transpose **Y**^{T} = -**Y**, where we consider if person `i`

gave `j`

$`y`

then it is equivalent to say person `j`

gave `i`

-$`y`

. Note that such matrices form a linear space (i.e., linearly closed)

= {~~Y~~**Y**in R^{NxN}:**Y**^{T}= -**Y**}.

Now let's consider what does it mean by settling the debt? When the debt is settled for person `i`

, it means neither `i`

owes any money from other people nor other people owes `i`

any money, so we have each row sum Σ_{j=1:N}y_{i,j} = 0. Such special matrices from actually form a subspace (i.e., linearly closed)

= {~~X~~**X**in:~~Y~~**Xe**=**0**}, with**e**= (1, 1, ...,1) in R^{N}.

That is, subspace is the subset of

**which is orthogonal to vector**

~~Y~~**e**.

If we define a metric ||.|| on matrices to count number of non-zero entries:

- ||
**Y**|| = Σ_{i,j=1:N}|sgn(y_{i,j})|, ( sgn(.) is the sign function)

Then the debt settling problem is transformed to a **linear space projection problem**:

- Given a
**Y**in space, find the minimum projection distance P(~~Y~~**X**) = ||**Y**-**X**||, where**X**in subspace.~~X~~

Note that metric ||.|| indeed defines a distance with distance inequality: ||**A** + **B**|| ≤ ||**A**|| + ||**B**||.

But I haven't figured out a way to go from here yet. Maybe I will try another day.

Anyone interested to try this way?