Consider a network of 
agents, each owing money to and being owed money by other agents. The debts are represented pictorially by the weighted directed graph
which I called an IOU graph on my previous post on this topic. The IOU graph representing this network is an ordered triple 
, where 
is the node set (each node of the IOU graph represents a different agent), 
is the edge set (containing 
elements), and 
is a weight function that assigns positive weights to each edge in 
. Each directed edge of graph 
is an ordered pair 
, where 
is the edge’s tail and 
is the edge’s head. If 
then node owes money to node . We do not allow nodes to owe money to themselves and, therefore, for each 
we must have 
. The weight of edge 
is given by 
, and it tells us the amount of money that node owes to node .
Alternatively, the information contained in the IOU graph can be encoded in the following nonnegative matrix
![\left[\begin{array}{cccccccccc} 0 & 10 & 0 & 20 & 20 & 5 & 15 & 0 & 0 & 0\\ 0 & 0 & 5 & 10 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 15 & 0 & 5 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 10 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 5 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 10 & 0 & 0 & 0 & 0\\ 5 & 20 & 0 & 0 & 0 & 0 & 5 & 0 & 0 & 0\\ 0 & 15 & 0 & 0 & 0 & 0 & 0 & 20 & 0 & 10\\ 0 & 5 & 15 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \end{array}\right]](http://l.wordpress.com/latex.php?latex=%5Cleft%5B%5Cbegin%7Barray%7D%7Bcccccccccc%7D+0+%26+10+%26+0+%26+20+%26+20+%26+5+%26+15+%26+0+%26+0+%26+0%5C%5C+0+%26+0+%26+5+%26+10+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0%5C%5C+0+%26+15+%26+0+%26+5+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0%5C%5C+0+%26+0+%26+0+%26+0+%26+10+%26+0+%26+0+%26+0+%26+0+%26+0%5C%5C+0+%26+0+%26+0+%26+0+%26+0+%26+5+%26+0+%26+0+%26+0+%26+0%5C%5C+0+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0%5C%5C+0+%26+0+%26+0+%26+0+%26+0+%26+10+%26+0+%26+0+%26+0+%26+0%5C%5C+5+%26+20+%26+0+%26+0+%26+0+%26+0+%26+5+%26+0+%26+0+%26+0%5C%5C+0+%26+15+%26+0+%26+0+%26+0+%26+0+%26+0+%26+20+%26+0+%26+10%5C%5C+0+%26+5+%26+15+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0%5C%5C+%5Cend%7Barray%7D%5Cright%5D&bg=ffffff&fg=000000&s=0 "\left[\begin{array}{cccccccccc} 0 & 10 & 0 & 20 & 20 & 5 & 15 & 0 & 0 & 0\\ 0 & 0 & 5 & 10 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 15 & 0 & 5 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 10 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 5 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 10 & 0 & 0 & 0 & 0\\ 5 & 20 & 0 & 0 & 0 & 0 & 5 & 0 & 0 & 0\\ 0 & 15 & 0 & 0 & 0 & 0 & 0 & 20 & 0 & 10\\ 0 & 5 & 15 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \end{array}\right]")
where entry is the amount of money node owes to node . Since we do not allow nodes to owe money to themselves, the entries on the main diagonal of this matrix are zero. We will call this matrix the IOU matrix. Note that the IOU matrix is the adjacency matrix of the IOU graph. Every nonnegative matrix with zero entries on the main diagonal is an admissible IOU matrix, and we can associate with it a corresponding IOU graph.
If the IOU matrix contains all the information about the IOU graph, then we can work with the IOU matrix instead of the IOU graph. Is there any advantage in doing so? I believe there is. In my opinion, the IOU graph is good for conceptual thinking and intuition, while the IOU matrix is a data structure that is convenient for computation. However, the matrix is not the only data structure that one can use to encode the information in an IOU graph. Another possibility would be to use adjacency lists, for example.
__________
Divergence and IOU Matrices
Suppose we are given an IOU graph 
, whose node set is 
. Note that 
for each , because nodes cannot owe money to themselves. We now introduce variables 
as follows
and build the (nonnegative) adjacency matrix of the IOU graph 
![Y = \left[\begin{array}{ccccc} 0 & y_{12} & y_{13} & \ldots & y_{1n}\\ y_{21} & 0 & y_{23} & \ldots & y_{2n}\\ y_{31} & y_{32} & 0 & \ldots & y_{3n}\\\vdots & \vdots & \vdots & \ddots & \vdots\\ y_{n1} & y_{n2} & y_{n3} & \ldots & 0\\\end{array}\right]](http://l.wordpress.com/latex.php?latex=Y+%3D+%5Cleft%5B%5Cbegin%7Barray%7D%7Bccccc%7D+0+%26+y_%7B12%7D+%26+y_%7B13%7D+%26+%5Cldots+%26+y_%7B1n%7D%5C%5C+y_%7B21%7D+%26+0+%26+y_%7B23%7D+%26+%5Cldots+%26+y_%7B2n%7D%5C%5C+y_%7B31%7D+%26+y_%7B32%7D+%26+0+%26+%5Cldots+%26+y_%7B3n%7D%5C%5C%5Cvdots+%26+%5Cvdots+%26+%5Cvdots+%26+%5Cddots+%26+%5Cvdots%5C%5C+y_%7Bn1%7D+%26+y_%7Bn2%7D+%26+y_%7Bn3%7D+%26+%5Cldots+%26+0%5C%5C%5Cend%7Barray%7D%5Cright%5D&bg=ffffff&fg=000000&s=0 "Y = \left[\begin{array}{ccccc} 0 & y_{12} & y_{13} & \ldots & y_{1n}\\ y_{21} & 0 & y_{23} & \ldots & y_{2n}\\ y_{31} & y_{32} & 0 & \ldots & y_{3n}\\\vdots & \vdots & \vdots & \ddots & \vdots\\ y_{n1} & y_{n2} & y_{n3} & \ldots & 0\\\end{array}\right]")
which is the IOU matrix associated with the IOU graph . The entry of matrix 
denotes the amount of money that node owes to node . The divergence of node is a scalar defined as
and it gives us the amount of money node owes to other nodes minus the amount of money node is owed to by other nodes. In terms of the IOU matrix 
, the divergence of node is given by
where 
is the -th vector of the canonical basis for 
, i.e., the -th column of the 
identity matrix 
, and 
is an 
-dimensional vector of ones. Let 
denote the vectorization operator, which stacks a given matrix’s columns in one large column vector. Note that if we apply operator to a scalar, we obtain the same scalar. Hence, we have that
and
where 
denotes the Kronecker product. Therefore, the divergence of node can be written as
![\mbox{div}_i (\mathcal{G}_0) = \left[(1_n^T \otimes e_i^T) - (e_i^T \otimes 1_n^T)\right] \mbox{vec} (Y)](http://l.wordpress.com/latex.php?latex=%5Cmbox%7Bdiv%7D_i+%28%5Cmathcal%7BG%7D_0%29+%3D+%5Cleft%5B%281_n%5ET+%5Cotimes+e_i%5ET%29+-+%28e_i%5ET+%5Cotimes+1_n%5ET%29%5Cright%5D+%5Cmbox%7Bvec%7D+%28Y%29&bg=ffffff&fg=000000&s=0 "\mbox{div}_i (\mathcal{G}_0) = \left[(1_n^T \otimes e_i^T) - (e_i^T \otimes 1_n^T)\right] \mbox{vec} (Y)")
.
We define also the divergence vector of graph as the -dimensional vector whose -th component is 
![\mbox{div} (\mathcal{G}_0) = \left[\begin{array}{c} (1_n^T \otimes e_1^T) - (e_1^T \otimes 1_n^T)\\ (1_n^T \otimes e_2^T) - (e_2^T \otimes 1_n^T)\\ \vdots\\ (1_n^T \otimes e_n^T) - (e_n^T \otimes 1_n^T)\\\end{array}\right] \mbox{vec} (Y)](http://l.wordpress.com/latex.php?latex=%5Cmbox%7Bdiv%7D+%28%5Cmathcal%7BG%7D_0%29+%3D+%5Cleft%5B%5Cbegin%7Barray%7D%7Bc%7D+%281_n%5ET+%5Cotimes+e_1%5ET%29+-+%28e_1%5ET+%5Cotimes+1_n%5ET%29%5C%5C+%281_n%5ET+%5Cotimes+e_2%5ET%29+-+%28e_2%5ET+%5Cotimes+1_n%5ET%29%5C%5C+%5Cvdots%5C%5C+%281_n%5ET+%5Cotimes+e_n%5ET%29+-+%28e_n%5ET+%5Cotimes+1_n%5ET%29%5C%5C%5Cend%7Barray%7D%5Cright%5D+%5Cmbox%7Bvec%7D+%28Y%29&bg=ffffff&fg=000000&s=0 "\mbox{div} (\mathcal{G}_0) = \left[\begin{array}{c} (1_n^T \otimes e_1^T) - (e_1^T \otimes 1_n^T)\\ (1_n^T \otimes e_2^T) - (e_2^T \otimes 1_n^T)\\ \vdots\\ (1_n^T \otimes e_n^T) - (e_n^T \otimes 1_n^T)\\\end{array}\right] \mbox{vec} (Y)")
.
Alternatively, we can use equation 
, and write the divergence vector as
and, since
and
,
we obtain
.
Note that 
-dimensional vectors 
and 
contain the same entries, but in a different order. Hence, there exists a 
permutation matrix 
such that
which allows us to write
.
Do note that the permutation matrix depends on only. It does not depend on the entries of the matrix to which operator is applied. Henceforth, we will denote 
. Finally, we have a rather compact equation for the divergence vector
.
The divergence vector of an IOU graph tells us how much money each node in the graph will lose after debts have been paid. We say that two IOU graphs (on the same node set) are equi-divergent if their divergence vectors are the same. This means that, although the debt relationships are different, both IOU graphs result in every node getting paid what he is owed and paying what he owes.
__________
Minimum Money Flow
Suppose we are given an IOU graph . We would like to find a new IOU graph on the same node set 
, such that the two IOU graphs are equi-divergent, i.e., 
. Moreover, we would like the new IOU graph to be “optimal” in some sense. On this post, we will consider the following optimality criterion:
minimum money flow: we want to minimize the total amount of money being exchanged between the nodes. This is the same as minimizing the sum of the weights of the IOU graph .
Let us start with matrix 
, which will be an admissible IOU matrix if we impose two constraints:
- nonnegativity: the entries of matrix
must be nonnegative. This is equivalent to imposing the constraint that vector 
has nonnegative entries, i.e., 
, which is equivalent to 
.
- zero entries on the main diagonal: we must have
for all . Note that 
, and therefore is equivalent to 
. Hence, imposing the constraint that the entries on the main diagonal be zero is equivalent to imposing the equality constraints
![\left[\begin{array}{c} e_1^T \otimes e_1^T\\ e_2^T \otimes e_2^T\\ \vdots\\ e_n^T \otimes e_n^T\\\end{array}\right] \tilde{x} = 0_n](http://l.wordpress.com/latex.php?latex=%5Cleft%5B%5Cbegin%7Barray%7D%7Bc%7D+e_1%5ET+%5Cotimes+e_1%5ET%5C%5C+e_2%5ET+%5Cotimes+e_2%5ET%5C%5C+%5Cvdots%5C%5C+e_n%5ET+%5Cotimes+e_n%5ET%5C%5C%5Cend%7Barray%7D%5Cright%5D+%5Ctilde%7Bx%7D+%3D+0_n&bg=ffffff&fg=000000&s=0 "\left[\begin{array}{c} e_1^T \otimes e_1^T\\ e_2^T \otimes e_2^T\\ \vdots\\ e_n^T \otimes e_n^T\\\end{array}\right] \tilde{x} = 0_n")
.
Once these two constraints have been imposed, matrix is the adjacency matrix of an IOU graph. Finally, we must impose the constraint that the divergence vector of the new IOU graph is the same as the divergence vector of the given IOU graph, i.e., , which yields
where 
can be computed from the given IOU graph. Considering the minimum money flow criterion, the cost function to be minimized is the following
and, hence, we obtain the following linear program in 
![\begin{array}{ll} \text{minimize} & \displaystyle 1_{n^2}^T \tilde{x}\\\\ \text{subject to} & (1_n^T \otimes I_n) (I_{n^2} - P) \tilde{x} = \mbox{div} (\mathcal{G}_0)\\\\ & \left[\begin{array}{c} e_1^T \otimes e_1^T\\ e_2^T \otimes e_2^T\\ \vdots\\ e_n^T \otimes e_n^T\\\end{array}\right] \tilde{x} = 0_n\\\\ & (-I_{n^2}) \tilde{x} \leq 0_{n^2}\\\\\end{array}](http://l.wordpress.com/latex.php?latex=%5Cbegin%7Barray%7D%7Bll%7D+%5Ctext%7Bminimize%7D+%26+%5Cdisplaystyle+1_%7Bn%5E2%7D%5ET+%5Ctilde%7Bx%7D%5C%5C%5C%5C+%5Ctext%7Bsubject+to%7D+%26+%281_n%5ET+%5Cotimes+I_n%29+%28I_%7Bn%5E2%7D+-+P%29+%5Ctilde%7Bx%7D+%3D+%5Cmbox%7Bdiv%7D+%28%5Cmathcal%7BG%7D_0%29%5C%5C%5C%5C+%26+%5Cleft%5B%5Cbegin%7Barray%7D%7Bc%7D+e_1%5ET+%5Cotimes+e_1%5ET%5C%5C+e_2%5ET+%5Cotimes+e_2%5ET%5C%5C+%5Cvdots%5C%5C+e_n%5ET+%5Cotimes+e_n%5ET%5C%5C%5Cend%7Barray%7D%5Cright%5D+%5Ctilde%7Bx%7D+%3D+0_n%5C%5C%5C%5C+%26+%28-I_%7Bn%5E2%7D%29+%5Ctilde%7Bx%7D+%5Cleq+0_%7Bn%5E2%7D%5C%5C%5C%5C%5Cend%7Barray%7D&bg=ffffff&fg=000000&s=0 "\begin{array}{ll} \text{minimize} & \displaystyle 1_{n^2}^T \tilde{x}\\\\ \text{subject to} & (1_n^T \otimes I_n) (I_{n^2} - P) \tilde{x} = \mbox{div} (\mathcal{G}_0)\\\\ & \left[\begin{array}{c} e_1^T \otimes e_1^T\\ e_2^T \otimes e_2^T\\ \vdots\\ e_n^T \otimes e_n^T\\\end{array}\right] \tilde{x} = 0_n\\\\ & (-I_{n^2}) \tilde{x} \leq 0_{n^2}\\\\\end{array}")
which has 
equality and inequality constraints. One can easily solve this linear program with MATLAB using function linprog.
However, this formulation looks a bit silly. Note that initially we have degrees of freedom (the entries of matrix ), then we impose equality constraints to ensure that the entries on the main diagonal are zero, which leaves us with 
degrees of freedom. If we already know that the entries on the main diagonal are zero, why consider them as decision variables? Wouldn’t it make much more sense to consider only the 
entries off the main diagonal as decision variables?
Let 
be a 
binary matrix such that 
is the reduced vector of 
decision variables, containing solely the entries of off the main diagonal. We now eliminate the columns of 
matrix 
which were to be multiplied by the 
variables. We do so by multiplying matrix on the right by 
, which produces a 
matrix 
.
The new vector of decision variables is 
. Since we no longer consider the entries on the main diagonal as decision variables, we don’t need to impose the equality constraints . Hence, we obtain a lower-dimensional linear program
where we now have equality constraints (divergences at the nodes), and inequality constrains (
). My intuition tells me that
![(1_n^T \otimes I_n) (I_{n^2} - P) R^T = \left[\begin{array}{c} (1_n^T \otimes e_1^T) - (e_1^T \otimes 1_n^T)\\ (1_n^T \otimes e_2^T) - (e_2^T \otimes 1_n^T)\\ \vdots\\ (1_n^T \otimes e_n^T) - (e_n^T \otimes 1_n^T)\\\end{array}\right] R^T](http://l.wordpress.com/latex.php?latex=%281_n%5ET+%5Cotimes+I_n%29+%28I_%7Bn%5E2%7D+-+P%29+R%5ET+%3D+%5Cleft%5B%5Cbegin%7Barray%7D%7Bc%7D+%281_n%5ET+%5Cotimes+e_1%5ET%29+-+%28e_1%5ET+%5Cotimes+1_n%5ET%29%5C%5C+%281_n%5ET+%5Cotimes+e_2%5ET%29+-+%28e_2%5ET+%5Cotimes+1_n%5ET%29%5C%5C+%5Cvdots%5C%5C+%281_n%5ET+%5Cotimes+e_n%5ET%29+-+%28e_n%5ET+%5Cotimes+1_n%5ET%29%5C%5C%5Cend%7Barray%7D%5Cright%5D+R%5ET&bg=ffffff&fg=000000&s=0 "(1_n^T \otimes I_n) (I_{n^2} - P) R^T = \left[\begin{array}{c} (1_n^T \otimes e_1^T) - (e_1^T \otimes 1_n^T)\\ (1_n^T \otimes e_2^T) - (e_2^T \otimes 1_n^T)\\ \vdots\\ (1_n^T \otimes e_n^T) - (e_n^T \otimes 1_n^T)\\\end{array}\right] R^T")
is an incidence matrix of the directed complete graph on node set . What do you think? Do you agree?
__________
A Numerical Example
Consider a network of agents whose debts are represented by the following IOU graph (with 
edges)
The IOU matrix associated with this given IOU graph is
![Y = \left[\begin{array}{cccccccccc} 0 & 0 & 0 & 20 & 20 & 5 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 10 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 5 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 10 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 5 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 10 & 0 & 0 & 0 & 0\\ 5 & 20 & 0 & 0 & 0 & 0 & 5 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 20 & 0 & 10\\ 0 & 5 & 15 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \end{array}\right]](http://l.wordpress.com/latex.php?latex=Y+%3D+%5Cleft%5B%5Cbegin%7Barray%7D%7Bcccccccccc%7D+0+%26+0+%26+0+%26+20+%26+20+%26+5+%26+0+%26+0+%26+0+%26+0%5C%5C+0+%26+0+%26+0+%26+10+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0%5C%5C+0+%26+0+%26+0+%26+5+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0%5C%5C+0+%26+0+%26+0+%26+0+%26+10+%26+0+%26+0+%26+0+%26+0+%26+0%5C%5C+0+%26+0+%26+0+%26+0+%26+0+%26+5+%26+0+%26+0+%26+0+%26+0%5C%5C+0+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0%5C%5C+0+%26+0+%26+0+%26+0+%26+0+%26+10+%26+0+%26+0+%26+0+%26+0%5C%5C+5+%26+20+%26+0+%26+0+%26+0+%26+0+%26+5+%26+0+%26+0+%26+0%5C%5C+0+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0+%26+20+%26+0+%26+10%5C%5C+0+%26+5+%26+15+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0%5C%5C+%5Cend%7Barray%7D%5Cright%5D&bg=ffffff&fg=000000&s=0 "Y = \left[\begin{array}{cccccccccc} 0 & 0 & 0 & 20 & 20 & 5 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 10 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 5 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 10 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 5 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 10 & 0 & 0 & 0 & 0\\ 5 & 20 & 0 & 0 & 0 & 0 & 5 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 20 & 0 & 10\\ 0 & 5 & 15 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \end{array}\right]")
Solving the linear program, we obtain a new IOU matrix
![X = \left[\begin{array}{cccccccccc} 0 & 6.097 & 3.924 & 10.776 & 10.776 & 8.427 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0.850 & 0.644 & 1.234 & 1.234 & 1.039 & 0 & 0 & 0 & 0\\ 0 & 1.690 & 1.185 & 2.505 & 2.505 & 2.114 & 0 & 0 & 0 & 0\\ 0 & 4.672 & 3.063 & 7.980 & 7.980 & 6.306 & 0 & 0 & 0 & 0\\ 0 & 1.690 & 1.185 & 2.505 & 2.505 & 2.114 & 0 & 0 & 0 & 0\\\end{array}\right]](http://l.wordpress.com/latex.php?latex=X+%3D+%5Cleft%5B%5Cbegin%7Barray%7D%7Bcccccccccc%7D+0+%26+6.097+%26+3.924+%26+10.776+%26+10.776+%26+8.427+%26+0+%26+0+%26+0+%26+0%5C%5C+0+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0%5C%5C+0+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0%5C%5C+0+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0%5C%5C+0+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0%5C%5C+0+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0+%26+0%5C%5C+0+%26+0.850+%26+0.644+%26+1.234+%26+1.234+%26+1.039+%26+0+%26+0+%26+0+%26+0%5C%5C+0+%26+1.690+%26+1.185+%26+2.505+%26+2.505+%26+2.114+%26+0+%26+0+%26+0+%26+0%5C%5C+0+%26+4.672+%26+3.063+%26+7.980+%26+7.980+%26+6.306+%26+0+%26+0+%26+0+%26+0%5C%5C+0+%26+1.690+%26+1.185+%26+2.505+%26+2.505+%26+2.114+%26+0+%26+0+%26+0+%26+0%5C%5C%5Cend%7Barray%7D%5Cright%5D&bg=ffffff&fg=000000&s=0 "X = \left[\begin{array}{cccccccccc} 0 & 6.097 & 3.924 & 10.776 & 10.776 & 8.427 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0.850 & 0.644 & 1.234 & 1.234 & 1.039 & 0 & 0 & 0 & 0\\ 0 & 1.690 & 1.185 & 2.505 & 2.505 & 2.114 & 0 & 0 & 0 & 0\\ 0 & 4.672 & 3.063 & 7.980 & 7.980 & 6.306 & 0 & 0 & 0 & 0\\ 0 & 1.690 & 1.185 & 2.505 & 2.505 & 2.114 & 0 & 0 & 0 & 0\\\end{array}\right]")
which is the adjacency matrix of a new IOU graph. The given IOU graph and the new IOU graph are equi-divergent. The given IOU graph had edges and a total of 
flowing in it, while the new IOU graph has 
edges and a total of 
flowing in it. While the flow of money has been reduced, the number of edges (i.e., the number of transactions) has increased dramatically!!
On my previous post on this topic, I gave two very simple examples, and in both of them the minimum money flow solution also yielded the least number of transactions. I wondered back then if that was always the case. This example clearly shows that it is not. Generally speaking, not only does the minimum money flow criterion fail to minimize the number of transactions, but it can actually result in more transactions than the ones in the initial IOU graph. I cannot think of any reason why minimizing the total amount of money flowing in the IOU graph at the cost of a larger number of transactions would be a good idea…
Therefore, the next step is to abandon the minimum money flow criterion, and focus solely on the least number of transactions. Minimizing the number of transactions is a hard combinatorial problem, but maybe there are approximation algorithms that make the problem tractable.
, with initial value 
. Suppose we would like to compute 
. Numerical methods produce rather bizarre results. The reason is that there is no solution at 
(finite escape time, anyone?). The moral of the story is that the theorems on existence and uniqueness of solutions to initial value problems do indeed matter.
have binary representations where the 
. For example, 
. It’s interesting to note that this was a somewhat serendipitous finding.
, 
symbol classifier. This is not mathematics per se, but it is an interesting tool for those who need to type mathematical expressions. And if you are interested in machine learning, you will definitely be intrigued.
