Return to Answer

If you make the objective to minimize the sum of the diagonal entries (i.e. the trace), your problem becomes a linear programming problem, solvable with readily available software (I think even Excel). In many cases the optimal solution will have all diagonal entries $0$.

EDIT: It may help to think of the problem this way. There are $n$ people, numbered from $1$ to $n$. Each person $i$ has a nonnegative amount $\pi_i$ of money, and we want to move all the money around so that everyone ends up with the same amount they started with. $P_{ij}$ is the fraction of person $i$'s money that goes to person $j$. Of course this will not be possible if one person has more than half the total amount of money. Otherwise it will be possible, by the following algorithm. We arrange the people in order clockwise from richest to poorest around a circular table, and everyone puts their money on the table in front of them (let's say in coins of a given denomination). The richest persion (#1) takes the amount $\pi_1$ off the table, starting with #2's coins, which come after his own coins. Each person then continues, taking the correct number of coins starting where the previous one left off. By induction, for $k$ from $2$ to $n$, when #k's turn comes, all his coins have already been taken.

EDIT: Here is a more explicit version of the algorithm I alluded to above.
We may assume that $\pi_1 \ge \pi_2 \ge \ldots \pi_n > 0$. If necessary, we reorder the rows and columns to make them decrease. If some $\pi_i$ are $0$, we make the corresponding columns all $0$ and put a $1$ arbitrarily (off the diagonal) in each of the corresponding rows, and follow the following algorithm for the rows and columns where $\pi > 0$.

If $\pi_1 > 1/2$, we let $P_{11} = 2 - 1/\pi_1$, $P_{i1}=1$ and $P_{1i} = \pi_i/\pi_1$ for $ i > 1$, and all other $P_{ij} = 0$. It is easy to check that this works, and no solution can have $P_{11} < 2 - 1/\pi_1$.

Now suppose $\pi_1 \le 1/2$. Let $S_k = \sum_{i=1}^k \pi_i$ be the partial sums of $\pi$, so $S_0 = 0$ and $S_n = 1$. Let $r_{ij}$ be the length of the intersection of the intervals $[S_{i-1}, S_i]$ and $[S_{j-1}+\pi_1, S_j + \pi_1] \mod 1$. Then $P_{ij} = r_{ij}/\pi_i$.

If you make the objective to minimize the sum of the diagonal entries (i.e. the trace), your problem becomes a linear programming problem, solvable with readily available software (I think even Excel). In many cases the optimal solution will have all diagonal entries $0$.

EDIT: It may help to think of the problem this way. There are $n$ people, numbered from $1$ to $n$. Each person $i$ has a nonnegative amount $\pi_i$ of money, and we want to move all the money around so that everyone ends up with the same amount they started with. $P_{ij}$ is the fraction of person $i$'s money that goes to person $j$. Of course this will not be possible if one person has more than half the total amount of money. Otherwise it will be possible, by the following algorithm. We arrange the people in order clockwise from richest to poorest around a circular table, and everyone puts their money on the table in front of them (let's say in coins of a given denomination). The richest persion (#1) takes the amount $\pi_1$ off the table, starting with #2's coins, which come after his own coins. Each person then continues, taking the correct number of coins starting where the previous one left off. By induction, for $k$ from $2$ to $n$, when #k's turn comes, all his coins have already been taken.

EDIT: Here is a more explicit version of the algorithm I alluded to above.
We may assume that $\pi_1 \ge \pi_2 \ge \ldots \pi_n > 0$. If necessary, we reorder the rows and columns to make them decrease. If some $\pi_i$ are $0$, we make the corresponding columns all $0$ and put a $1$ arbitrarily (off the diagonal) in each of the corresponding rows, and follow the following algorithm for the rows and columns where $\pi > 0$.

If $\pi_1 > 1/2$, we let $P_{11} = 2 - 1/\pi_1$, $P_{i1}=1$ and $P_{1i} = \pi_i/\pi_1$ for $ i > 1$, and all other $P_{ij} = 0$. It is easy to check that this works, and no solution can have $P_{11} < 2 - 1/\pi_1$.

Now suppose $\pi_1 \le 1/2$. Let $S_k = \sum_{i=1}^k \pi_i$ be the partial [[sums of $\pi$, so $S_0 = 0$ and $S_n = 1$. Let $r_{ij}$ be the length of the intersection of the intervals $[S_{i-1}, S_i]$ and $[S_{j-1}+\pi_1, S_j + \pi_1] \mod 1$. Then $P_{ij} = r_{ij}/\pi_i$.

For example, suppose $\pi = [0.3, 0.24, 0.24, 0.16, 0.06]$. The partial sums are $[0, 0.3, 0.54, 0.78, 0.94, 1]$. The shifted partial sums $S_i + \pi_1$ are $[.3, .0.6, 0.84, 1.08, 1.24, 1.30]$. Then, for example, the intersection of $[S_{2} + \pi_1, S_3 + \pi_1] \mod 1 = [.84, 1] \cup [0, .08]$ and $[S_0, S_1]=[0,0.3]$ has length $0.08$, so $P_{13} = 0.08/0.3 = 4/15$, while the intersection of $[S_2+\pi_1, S_3 + \pi_1] \mod 1$ with $[S_3, S_4] =[.78, .94]$ has length $.1$ so $P_{43} = .1/.16 = 5/8$ and the intersection of $[S_2+\pi_1, S_3 + \pi_1] \mod 1$ with $[S_4, S_5] = [.94, 1]$ has length $.06$ so $P_{53} = .06/.06 = 1$. The resulting matrix is $$ \pmatrix{ 0 & 0 & 4/15 & 8/15 & 1/5\cr 1 & 0 & 0 & 0 & 0\cr 1/4 & 3/4 & 0 & 0 & 0\cr 0 & 3/8 & 5/8 & 0 & 0\cr 0 & 0 & 1 & 0 & 0\cr} $$

If you make the objective to minimize the sum of the diagonal entries (i.e. the trace), your problem becomes a linear programming problem, solvable with readily available software (I think even Excel). In many cases the optimal solution will have all diagonal entries $0$.

EDIT: It may help to think of the problem this way. There are $n$ people, numbered from $1$ to $n$. Each person $i$ has a nonnegative amount $\pi_i$ of money, and we want to move all the money around so that everyone ends up with the same amount they started with. $P_{ij}$ is the fraction of person $i$'s money that goes to person $j$. Of course this will not be possible if one person has more than half the total amount of money. Otherwise it will be possible, by the following algorithm. We arrange the people in order clockwise from richest to poorest around a circular table, and everyone puts their money on the table in front of them (let's say in coins of a given denomination). The richest persion (#1) takes the amount $\pi_1$ off the table, starting with #2's coins, which come after his own coins. Each person then continues, taking the correct number of coins starting where the previous one left off. By induction, for $k$ from $2$ to $n$, when #k's turn comes, all his coins have already been taken.

If you make the objective to minimize the sum of the diagonal entries (i.e. the trace), your problem becomes a linear programming problem, solvable with readily available software (I think even Excel). In many cases the optimal solution will have all diagonal entries $0$.

EDIT: It may help to think of the problem this way. There are $n$ people, numbered from $1$ to $n$. Each person $i$ has a nonnegative amount $\pi_i$ of money, and we want to move all the money around so that everyone ends up with the same amount they started with. $P_{ij}$ is the fraction of person $i$'s money that goes to person $j$. Of course this will not be possible if one person has more than half the total amount of money. Otherwise it will be possible, by the following algorithm. We arrange the people in order clockwise from richest to poorest around a circular table, and everyone puts their money on the table in front of them (let's say in coins of a given denomination). The richest persion (#1) takes the amount $\pi_1$ off the table, starting with #2's coins, which come after his own coins. Each person then continues, taking the correct number of coins starting where the previous one left off. By induction, for $k$ from $2$ to $n$, when #k's turn comes, all his coins have already been taken.

EDIT: Here is a more explicit version of the algorithm I alluded to above.
We may assume that $\pi_1 \ge \pi_2 \ge \ldots \pi_n > 0$. If necessary, we reorder the rows and columns to make them decrease. If some $\pi_i$ are $0$, we make the corresponding columns all $0$ and put a $1$ arbitrarily (off the diagonal) in each of the corresponding rows, and follow the following algorithm for the rows and columns where $\pi > 0$.

If $\pi_1 > 1/2$, we let $P_{11} = 2 - 1/\pi_1$, $P_{i1}=1$ and $P_{1i} = \pi_i/\pi_1$ for $ i > 1$, and all other $P_{ij} = 0$. It is easy to check that this works, and no solution can have $P_{11} < 2 - 1/\pi_1$.

Now suppose $\pi_1 \le 1/2$. Let $S_k = \sum_{i=1}^k \pi_i$ be the partial sums of $\pi$, so $S_0 = 0$ and $S_n = 1$. Let $r_{ij}$ be the length of the intersection of the intervals $[S_{i-1}, S_i]$ and $[S_{j-1}+\pi_1, S_j + \pi_1] \mod 1$. Then $P_{ij} = r_{ij}/\pi_i$.

If you make the objective to minimize the sum of the diagonal entries (i.e. the trace), your problem becomes a linear programming problem, solvable with readily available software (I think even Excel). In many cases the optimal solution will have all diagonal entries $0$.

EDIT: It may help to think of the problem this way. There are $n$ people, numbered from $1$ to $n$. Each person $i$ has a nonnegative amount $\pi_i$ of money, and we want to move all the money around so that everyone ends up with the same amount they started with. $P_{ij}$ is the fraction of person $i$'s money that goes to person $j$. Of course this will not be possible with one person has more than half the total amount of money. Otherwise it will be possible, by the following algorithm. We arrange the people in order clockwise from richest to poorest around a circular table, and everyone puts their money on the table in front of them (let's say in coins of a given denomination). The richest persion (#1) takes the amount $\pi_1$ off the table, starting with #2's coins, which come after his own coins. Each person then continues, taking the correct number of coins starting where the previous one left off. By induction, for $k$ from $2$ to $n$, when #k's turn comes, all his coins have already been taken.

If you make the objective to minimize the sum of the diagonal entries (i.e. the trace), your problem becomes a linear programming problem, solvable with readily available software (I think even Excel). In many cases the optimal solution will have all diagonal entries $0$.

EDIT: It may help to think of the problem this way. There are $n$ people, numbered from $1$ to $n$. Each person $i$ has a nonnegative amount $\pi_i$ of money, and we want to move all the money around so that everyone ends up with the same amount they started with. $P_{ij}$ is the fraction of person $i$'s money that goes to person $j$. Of course this will not be possible if one person has more than half the total amount of money. Otherwise it will be possible, by the following algorithm. We arrange the people in order clockwise from richest to poorest around a circular table, and everyone puts their money on the table in front of them (let's say in coins of a given denomination). The richest persion (#1) takes the amount $\pi_1$ off the table, starting with #2's coins, which come after his own coins. Each person then continues, taking the correct number of coins starting where the previous one left off. By induction, for $k$ from $2$ to $n$, when #k's turn comes, all his coins have already been taken.