Any one considered linear space perspective for this problem? (not solved yet but interesting!)


  • 0

    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 yi,j, then we can form an NxN matrix Y = (yi,j), which has property that transpose YT = -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 RNxN: YT = -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:Nyi,j = 0. Such special matrices from Y actually form a subspace (i.e., linearly closed)

    • X = {X in Y: Xe = 0 }, with e = (1, 1, ...,1) in RN.

    That is, subspace X is the subset of Y which is orthogonal to vector e.

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

    • ||Y|| = Σi,j=1:N|sgn(yi,j)|, ( sgn(.) is the sign function)

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

    • Given a Y in space Y, find the minimum projection distance P(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?
    0_1481128973742_ProjectSpace.JPG


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.