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?

Improve this question
$\endgroup$
15
  • $\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$ Commented Jun 23, 2015 at 23:01
  • $\begingroup$ Would you mind sharing the application of this? $\endgroup$ Commented Jun 23, 2015 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$ Commented Jun 23, 2015 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$ Commented Jun 23, 2015 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$ Commented Jun 23, 2015 at 23:39

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thank you very much, you are truly phenomenal! $\endgroup$ Commented Jun 24, 2015 at 4:28

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.