User silvanmx - MathOverflow

Another matrix diagonalization problem

2012-05-04T19:55:08Z

Given the matrices $X$ and $Y$ in $[0,1]^{n\times m}$, for $n > m > 3$, so that $X1_m=1_m$ and $Y1_m=1_m$, where $1_m$ denotes a $m$-length column vector of ones, find a matrix $Q$ in $R^{m\times m}$ so that $C(X,Y)=Q^TX^TYQ$ satisfies the following tree conditions:

$i$) $C(X,X)$ is diagonal with diagonal elements given by the the sum of rows of $X$

$ii$) The sum of the columns of $C(X,Y)$ equals the sum of rows of $X$

$iii$) The sum of the rows of $C(X,Y)$ equals the sum of rows of $Y$

What can be said about the uniqueness of the matrix $Q$?

A matrix diagonalization problem

2012-03-29T19:40:17Z

For matrices $X,Y\in [0,1]^{n\times m}$, for n > m, is there a square matrix $W\in R^{n\times n}$ so that $X^TWY$ is diagonal if and only if $Y = X$? Furthermore, $X$ and $Y$ are column normalized so that $X1_m = Y1_m = 1_m$, where $1_m$ is the m-length column vector with all entries equal to 1.

I know that if $X$ and $Y$ are binary, then $W=I$.

Answer by silvanmx for A matrix diagonalization problem

2012-04-02T15:51:41Z

Here is a solution: $W = X(X^TX)^{-1}D(X^TX)^{-1}X^T$ for a diagonal matrix $D$. You may verify that $X^TWY = D$ iff $Y = X$.

What is the nonrecursive formula for the following implicit function?

2010-04-14T20:42:05Z

Given $f(0) = 1-c$, what is the non-recursive $f(n)$ that satify the following equation $f(n)-\frac{1}{2}f(n-1)f(n)+f(n-1) = 1$

for n = 1,2,3,...?

Matrix decomposition problem

2010-03-31T19:37:36Z

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$

Comment by silvanmx

2012-05-07T16:30:25Z

Regarding the properties of $Q$, consider this. Let $\Lambda_x = \mathrm{diag}(1_n^T X)$ and $\Lambda_y = \mathrm{diag}(1_n^T Y)$be the diagonal matrices formed with the row sum of $X$ and $Y$, respectively. Then, from ii) and iii), one can get $C 1_m = \Lambda_x 1_m$ and $1_m^TC = 1_m^T\Lambda_y$, for $C=Q^TX^TY^TQ$. These equations imply that the vector $1_m$ is a right eigenvector of $C$ with respect to $\Lambda_x$ and a left eigenvector with respecto to $\Lambda_y$.

Comment by silvanmx

2012-05-07T16:27:45Z

BTW, could not figure out the typo.

Comment by silvanmx

2012-05-07T16:00:21Z

Why is the problem interesting? Its solution will have relevance in land cover change detection. Each row of $X$ and $Y$ represents membership vectors of $m$ land cover types. If $X,Y\in\{1,0\}^{n\times m}$, i.e., are binary matrices with exactly one non-zero element per row, then $C=X^TY$ quantifies the changes among land cover types, and $C$ satisfies all three conditions above ($Q=I$). The problem arises when $X,Y\in[1,0]^{n\times m}$, that is partial memberships are allowed.

Comment by silvanmx

2012-05-04T19:22:53Z

I understand your point. However, for a propper solution of the problem one must be able to discern between diagonal and non-diagonal matrices. So, let's just discard the scalar case. – silvanmx 0 secs ago

Comment by silvanmx

2012-05-04T19:10:10Z

Looks like your answer is right! Thanks.

Comment by silvanmx

2012-05-04T19:08:05Z

You are right! That solution gives actually a specific one for a given $X$. It seems Spenser's reasoning above answers the question.

Comment by silvanmx

2012-04-02T16:31:12Z

Then what would be a non-diagonal 1-by-1 matrix? When I say ambiguous I mean that a scalar can be considered either diagonal or non-diagonal.

Comment by silvanmx

2012-04-02T16:16:35Z

If $Y\ne X$, then $X^TWX = D(X^TX)^{-1}X^TY$ which is (I'm guessing) non-diagonal.

Comment by silvanmx

2012-04-02T15:54:44Z

I meant your second interpretation. Sorry for the confusion.

Comment by silvanmx

2012-03-29T20:15:27Z

Ok, I am assuming n>>m. Besides, the concept of a diagonal matrix is ambiguous for scalars.

Comment by silvanmx

2010-04-15T21:12:04Z

What is CAS by the way?

Comment by silvanmx

2010-04-15T21:11:35Z

Wow! Not tested yet but it looks like this is it. Thank you so much.

Comment by silvanmx

2010-04-07T18:49:33Z

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.

Comment by silvanmx

2010-04-06T15:09:51Z

Sorry, I forgot the nonnegativity constraint. The insigth is very useful though.

Comment by silvanmx

2010-04-06T15:02:28Z

Interesting! It seems my problem now reduces to find an appropriate cost function.