Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given a pair of distributions $x,y\in(0,1]^{n\times 1}$, so that $1^Tx=1$ and $1^Ty=1$, I want to build a matrix $C$ (change matrix) that satisfy at least the following properties:

i) $C$ is diagonal if and only if $x=y$

ii) $C1 = x$

iii) $C^T1 = y$

iv) $C$ has nonnegative entries

How to build a $C$ that satisfy i)-iv)?

If $\Lambda_x = diag(x)$ and $\Lambda_y = diag(y)$ conditions ii) and iii) can be also written as:

(1) $C\Lambda_y^{-1}y = x$

(2) $C^T\Lambda_x^{-1}x = y$

respectivelly. Replacing (2) in (1) results in:

(3) $C\Lambda_y^{-1}C^T\Lambda_x^{-1}x = x$

And replacing $x$ by $\Lambda_x1$ results the matricial Equation:

(4) $\(C\Lambda_y^{-1}C^T-\Lambda_x\)1 = 0$

or alternativelly (if 1 is replaced in 2),

(5) $\(C^T\Lambda_x^{-1}C-\Lambda_y\)1 = 0$

share|improve this question
    
What's C(x, y)? –  Qiaochu Yuan Mar 31 '10 at 20:10
    
C(x,y) is just to emphasize thet C is a function of x and y. This notation is now dropped. –  silvanmx Mar 31 '10 at 20:22
2  
Can you clarify how the final equation is related to (ii) and (iii)? Is it equivalent, stronger, or weaker? I'm asking because the system of (ii) and (iii) is clear - it has solutions if and only if the sum of coordinates of $x$ equals that of $y$. –  Sergei Ivanov Mar 31 '10 at 21:05
    
Replace vector $1$ by $\Lambda_y^{-1}y$ in ii) and by $\Lambda_x^{-1}x$ in iii) then combine them to get the equation. –  silvanmx Apr 1 '10 at 14:40
    
Note that condition i) can be alternatively expressed as: i) $C$ is diagonal if and only if $x=y$ –  silvanmx Apr 1 '10 at 15:59

3 Answers 3

up vote 5 down vote accepted

This is exactly the measure transportation problem in finite setting. Try to google "optimal measure transportation" for references and various algorithms. (ii) and (iii) are just the definition of transport (one also usually wants the entries of $C$ to be non-negative) and (i) is a very weak requirement of "optimality" that follows from any transport cost minimization requrement usually used (they are many and yield different answers).

share|improve this answer
    
Interesting! It seems my problem now reduces to find an appropriate cost function. –  silvanmx Apr 6 '10 at 15:02
    
Fine. I have three books titled Operations Research. Each calls this the Transportation Problem, while one adds in the adjective "balanced" in your case. Just put in a cost of $(i-j)^2$ at position $i,j$. My $c_{ij} = x_i y_j / M$ gives an initial feasible solution. –  Will Jagy Apr 6 '10 at 18:13
    
Will, your cost function works but I found it hard to justify. A maximal trace has more meaning for my application as it implies a minimum change, etc. So, the problem can be stated as: Maximize $tr(C)$ subject to $C1=1$, $C^T1=1$ and $C>0$. I am just wondering if this problem accepts a unique solution or if there is an analytic solution out there. –  silvanmx Apr 7 '10 at 18:49
    
So put the cost 1 for $i \neq j$ but 0 for $i = j.$ –  Will Jagy Apr 8 '10 at 4:18

As Sergei Ivanov pointed out in his first comment, it is necessary and sufficient, to solve your (ii) and (iii), to have $$ \sum_{i = 1}^{n} x_i = \sum_{i=1}^{n} y_i \; \; .$$ If this is true then take $ M = \sum_{i = 1}^{n} x_i = \sum_{i=1}^{n} y_i \; \; . $ The most natural solution to (ii) and (iii) is the rank-one matrix $C^0$ given by $$ c_{ij}^{0} = \frac{x_i y_j}{M} $$

Now, there is a kernel involved next of dimension $(n-1)^2,$ these being matrices $F$ satisfying $F 1 = 0$ and $F^t 1 = 0.$ One may specify any entries desired in the upper left square $n-1$ by $n-1$ block of $F$, then fill in the final column and row. Any solution of (ii) and (iii) must be of the form $$ C^0 + F \; \; .$$

Progress: for your purpose it is better to specify the matrix $F$ as shown below for $n=4,$ the other entries of $F$ are forced by the condition that all row sums and all column sums are zero. $$ F = \left( \begin{array}{cccc} & r & s & t \\\ & & u & v \\\ a & & & w \\\ b & c & & \end{array} \right). $$ As a result, $C^0 + F$ can be arranged to have all zeroes above the diagonal, then zeroes below a single layer alongside the main diagonal. The result is slightly better than what is called tridiagonal in that the entries above the diagonal are also 0.

http://en.wikipedia.org/wiki/Tridiagonal_matrix

We have arranged $$ C^0 + F = \left( \begin{array}{cccc} a_1 & & & \\\ r_1 & b_1 & & \\\ & s_1 & c_1 & \\\ & & t_1 & d_1 \end{array} \right) .$$

Now that we know that we can insist on this shape, we can just start out with this and a simple scheme involving your (ii) and (iii) defines the values for all the nonzero positions. Furthermore, if in addition $x = y,$ then it follows from (ii) and (iii) that $C^0 + F$ is actually diagonal. Done.

share|improve this answer
1  
Maybe the practical roots of the problem dictate some extra requirements on the solution of (ii) and (iii). E.g., one may want to minimize non-diagonal elements somehow (I am judging by the requirement (i)). And maybe something like this motivates the final equation. Unfortunately, we cannot know what was meant until the OP explains. –  Sergei Ivanov Apr 3 '10 at 16:39
    
Thanks for your comment. Just realized that I overlooked something when combining ii) and iii). The matrix equation has been corrected and the derivation is now shown step by step. In my application the 1-norm of the vectors $x$ and $y$ is always the unit (i.e. $M=1$). As per the invertibility of matrix $C$ , I am still thinking if this should be an additional requirement of the matrix or not. Anyway, your solution $C^0+F$ seems to fulfill (4) but not sure if this also meets condition i). –  silvanmx Apr 5 '10 at 20:59
    
Sergei has made a point about the optimization. Intuitively, I know the off-diagonal elements must be a function of $x-y$ but not sure how to express it in a way that is consisten with my application. –  silvanmx Apr 5 '10 at 21:15
    
Sorry, I forgot the nonnegativity constraint. The insigth is very useful though. –  silvanmx Apr 6 '10 at 15:09

There exists a solution, provided that the vectors x and y satisfy certain constraints. First, one observes that the conditions (ii) and (iii) imply that x(1) = y(1), because this is the (1,1) element of the matrix C. Next observe that the matrix

O = Lambda_x^(-1/2)*C*Lambda_y^(-1/2)

satisfies:

O^(T)*O = I

i.e., it is an orthogonal matrix. The first column and row of O are just the square roots of the elements of vectors x and y. Thus, there is an other constraint namely the sum of the elements of the vectors x and y must be one.

Now we have a problem of finding an orthogonal matrix O given its first row and column. This problem admits many solutions, for example using the Gram-Schmidt orthonormalization procedure, we can choose the second row consisting of only two nonvanishing elements, the third row of three nonvanishing elements etc. and solve the orthonormalization conditions.

share|improve this answer
    
I do not see how you get to $x(1)=y(1)$ . It seems you are confused with the notation. Just to clarify, $C1$ does not mean the first column of $C$, but the multiplication of $C$ by a column of ones. Likewise with $C^T1$. –  silvanmx Apr 1 '10 at 14:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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