7
$\begingroup$

I have an application in mind, and I need to do the following analysis, but am having a high degree of difficulty conceptualizing it in terms of syntax. I understand what I want, but cannot seem to pull through in terms of code. I have two n by n matrices, call them matrix A and matrix B. The sum of all the entries in each n by n matrix is defined to be 1 for all n. I want to be able to “convert” matrix A to matrix B. However, I want to do this with the following counter and by rearrangement with the following conditions (pretend here n is 3 but I want to generalize it to any n) :

Moving 1 unit horizontally or 1 unit vertically (no diagonal movement allowed) is equivalent to 1 point cost So for example:

$\begin{matrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{matrix}$ $\qquad$to $\qquad$ $ \begin{matrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 1 & 0 & 0 \\ \end{matrix} $

is 2 points cost because I moved the 1 two units down. Similarly,

$\begin{matrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{matrix}$ $\qquad$to $\qquad$ $ \begin{matrix} 0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \\ \end{matrix} $

is equivalent to 2 points because I had to go 1 unit left and 1 unit down. However,

$\begin{matrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{matrix}$ $\qquad$to $\qquad$ $ \begin{matrix} 0 & 0.8 & 0 \\ 0.2 & 0 & 0 \\ 0 & 0 & 0 \\ \end{matrix} $
Should be equivalent to 1 because you’re leaving 0.2 1 unit away, and 0.8 1 unit away (0.2*1+0.8*1). And then,

$\begin{matrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{matrix}$ $\qquad$to $\qquad$ $ \begin{matrix} 0 & 0 & 0.8 \\ 0.2 & 0 & 0 \\ 0 & 0 & 0 \\ \end{matrix} $
Should be equivalent to 1.8 because you are moving 0.2 1 unit away down and 0.8 2 units away right (0.2*1+0.8*2). However, I may not always have just a “1” that needs to be doled out everywhere, I could have matrices like:

$\begin{matrix} 0.2 & 0.1 & 0.1 \\ 0 & 0.3 & 0 \\ 0.04 & 0.06 & 0.2 \\ \end{matrix}$ $\qquad$to $\qquad$ $ \begin{matrix} 0.1 & 0.42 & 0.1 \\ 0.08 & 0.02 & 0.05 \\ 0.2 & 0 & 0.03 \\ \end{matrix} $

And I will need to optimize in terms of points. Can anyone help me?

$\endgroup$
  • $\begingroup$ Welcome to Mathematica.SE! I hope you will become a regular contributor. To get started, 1) take the introductory Tour now, 2) when you see good questions and answers, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge, 3) remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign, and 4) give help too, by answering questions in your areas of expertise. $\endgroup$ – bbgodfrey Jun 23 '15 at 23:01
  • $\begingroup$ Would you mind sharing the application of this? $\endgroup$ – J. M. will be back soon Jun 23 '15 at 23:02
  • $\begingroup$ Is there a bound for n? Also, neither of your two final examples sum to 1 as claimed in preamble - so what's the story? $\endgroup$ – ciao Jun 23 '15 at 23:05
  • $\begingroup$ @bbgodfrey Thank you for the heads up. I took the tour, and I am excited to be a part of this community. $\endgroup$ – Mike Shawn Jun 23 '15 at 23:09
  • 1
    $\begingroup$ Well, it's not super secret. Because there are academic politics involved, I'll let more cats out of the bag, but not too many. It's just a way of taking multiple probability distributions generated by an engineered machine, and ranking them in terms of similarity based on the "points" it costs. One can imagine that if I have A, B, and C..and A takes 2.3 points to convert to B, but it takes 5.7 points to convert to C, A is more similar than B. I have to use this method though and not other metrics unfortunately. EDIT: How did you get 10^21? $\endgroup$ – Mike Shawn Jun 23 '15 at 23:39
8
$\begingroup$

This is not a complete answer, but it's too long for a comment. It doesn't completely work, but perhaps it might inspire other answers.

The idea is to use graph theory and flows. I shall just look at the 3x3 case. First we construct a graph of 9 source nodes and 9 sink nodes. The source nodes flow costlessly straight into the sink nodes, and the sink nodes can flow around in the grid.

e = {
  1 -> 2, 2 -> 1, 2 -> 3, 3 -> 2,
  1 -> 4, 4 -> 1, 2 -> 5, 5 -> 2, 3 -> 6, 6 -> 3,
  4 -> 5, 5 -> 4, 5 -> 6, 6 -> 5,
  4 -> 7, 7 -> 4, 5 -> 8, 8 -> 5, 6 -> 9, 9 -> 6,
  7 -> 8, 8 -> 7, 8 -> 9, 9 -> 8
  };

g = Graph[Range@18, Table[v -> (9 + v), {v, 9}] ~Join~ (e /. k_Integer :> 9 + k),
  EdgeCost -> (ConstantArray[0, 9]~Join~ConstantArray[1, 24]), VertexLabels -> "Name"]

graph

Now we can do:

FindMinimumCostFlow[g, {
  1, 0, 0,
  0, 0, 0,
  0, 0, 0,

  0, 0, -0.8,
  -0.2, 0, 0,
  0, 0, 0
  }]

1.8

As required. Note how we use positive values for the first matrix and negative values for the second. There are probably other graphs that might do the same job.

If we try the last example:

FindMinimumCostFlow[g, {
   20, 10, 10,
   0, 30, 0,
   4, 6, 20,

   -10, -42, -10,
   -8, -2, -5,
   -20, 0, -3
   }/100]

It fails (just repeats the input). However it we put a slight fudge in there:

FindMinimumCostFlow[g, {
   20, 10, 10,
   0, 30, 0.000001,
   4, 6, 20,

   -10, -42, -10,
   -8, -2, -5,
   -20, 0, -3
   }/100]

0.75

We get an answer. This is on version 9 - maybe it works better on 10? We can also get a graphical representation of it:

FindMinimumCostFlow[g, {
   20, 10, 10,
   0, 30, 0.000001,
   4, 6, 20,

   -10, -42, -10,
   -8, -2, -5,
   -20, 0, -3
   }/100, "FlowGraph"]

flow

$\endgroup$
  • 1
    $\begingroup$ Thank you very much, you are truly phenomenal! $\endgroup$ – Mike Shawn Jun 24 '15 at 4:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.