# A matrix diagonalization problem

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

-
I'm having difficulty parsing the question. Do you mean given any $X, Y$ with the normalization (which should read $X 1_m = Y1_m = 1_n$), there is such a $W$ if and only if $X=Y$? Or do you mean is there a $W$ such that for all $X, Y$ with the normalization, $X^TWY$ is diagonal if and only if $Y=X$? –  Robert Israel Mar 30 '12 at 0:02
I meant your second interpretation. Sorry for the confusion. –  silvanmx Apr 2 '12 at 15:54

UPDATE Sorry, previous version was wrong. For $n=m=2$, this computation shows that there is such a matrix. FURHTER UPDATE However, for $m=n=3$, it shows there isn't.

Taking $n=m=2$, we see that $X$ and $Y$ are of the form $\begin{pmatrix} x & 1-x \\ 1-x & x \end{pmatrix}$ and $\begin{pmatrix} y & 1-y \\ 1-y & y \end{pmatrix}$. Set $W = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$ Then $X^T W Y =: \begin{pmatrix} e & f \\ g & h \end{pmatrix}$ with

$$f=c+(a-c)x+(d-c) y+(-a+b+c-d)xy$$ $$g=b+(a-b)x+(d-b) y+(-a+b+c-d)xy$$

Your desire is that we have $f(x,y) = g(x,y) =0$ iff $x=y$. Plugging in $x=y$, we deduce that we must have $b=c=a+d=0$. But then $f$ and $g$ vanish for all $x$ and $y$. And, indeed, $(a,b,c,d) = (1,0,0,-1)$ solves the problem for $m=n=2$.

Now run the same analysis with $m=n=3$, thinking about $X$ and $Y$ of the form $\begin{pmatrix} x & 1-x & 0 \\ 1-x & x & 0 \\ 0 & 0 & 1 \end{pmatrix}$. We deduce that $w_{12} = w_{21}=0$ and $w_{11}=-w_{22}$. Similarly, $w_{22} = - w_{33}$, $w_{11} = - w_{33}$ and $w_{13}=w_{31} = w_{23} = w_{32}=0$. But the only solution to these linear equations is $W=0$..

-
Looks like your answer is right! Thanks. –  silvanmx May 4 '12 at 19:10

The general $n=m$ case: First take $X$ to be the identity, this gives us that $W$ is the diagonal. Then for each pair of entries on the diagonal, look at the set of matrices that are almost entirely the identity, but have a 2$\times$2 block that looks like one of David Speyer's 2$\times$2 matrices and contains those two diagonal entries. Take $X$ and $Y$ be one of those matrices, then his calculations show that these two diagonal entries are minus each other. So if $n\geq 3$ then each pair of entries sum to $0$, so all sum to $0$, but this is also impossible, a contradiction.

The general $n>m$ case. Let $X$ be an $n\times n$ matrix. Consider all matrices $X'$ formed by removing $n-m$ rows, and consider $X'^TWX'$. These must all be diagonal, so if $m\geq 2$ then $X^TWX$, since every off-diagonal entry in it is an off-diagonal entry in one of these matrices. So we reduce to the previous case.

Therefore, $n\geq 3$ and $m\geq 2$ is unsolvable. (building on David Speyer's answer). By an obvious extension of Arthur B's answer, $n>m=1$ is unsolvable. This, combined with David's observation that $n=m=2$ is solvable, answers every case.

-

In general no, take n = m = 1

-
Ok, I am assuming n>>m. Besides, the concept of a diagonal matrix is ambiguous for scalars. –  silvanmx Mar 29 '12 at 20:15
@silvanmx: What is the ambiguity? I would have thought every 1-by-1 matrix is diagonal (unambiguously). –  Andreas Blass Apr 2 '12 at 16:00
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. –  silvanmx Apr 2 '12 at 16:31
I don't see why one could consider a scalar non-diagonal, or why one would want to have any non-diagonal 1-by-1 matrices. A non-diagonal matrix should have a non-zero entry in at least one off-diagonal position, and there are no such positions in a 1-by-1 matrix. –  Andreas Blass Apr 2 '12 at 17:17
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 –  silvanmx May 4 '12 at 19:22

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

-
Yes, but what about other possible values of $Y\neq X$ that would return a diagonal matrix $D_2\neq D$? –  Federico Poloni Apr 2 '12 at 15:55
If $Y\ne X$, then $X^TWX = D(X^TX)^{-1}X^TY$ which is (I'm guessing) non-diagonal. –  silvanmx Apr 2 '12 at 16:16
You are right! That solution gives actually a specific one for a given $X$. It seems Spenser's reasoning above answers the question. –  silvanmx May 4 '12 at 19:08