Matrix decomposition problem

Question

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$

Answer 1

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).

Answer 2

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.

Answer 3

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.