Me and my roommates don't split expenses right away but enter the amounts paid for others into a spreadsheet. So at the end of the month, we can pay each other the residual amounts. We discovered that many transactions can be avoided when "indirect payments" can be avoided (e.g. A has to give B 10€ and B has to give C 10€ then A can give the 10€ straight to C). This question told me that the maximum (and the usual) amount of these transactions is $n-1$. However, there is no description of how I can determine which transactions to do.
I want to automate the process of simplifying the transactions using scripts in the spreadsheet but I couldn't find any solution online (partly due to lack of knowing a word for this type of problem). I was thinking this may be some special form of transportation theory or something else to do with simplex, as I vaguely remember that being similar to what has to be achieved here (when you put the transactions into a matrix).
If anyone knows an algorithm to simplify the matrix for the transactions it would be highly appreciated.