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

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

share|improve this question
1  
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
add comment

4 Answers

up vote 3 down vote accepted

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

share|improve this answer
    
Looks like your answer is right! Thanks. –  silvanmx May 4 '12 at 19:10
add comment

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.

share|improve this answer
add comment

In general no, take n = m = 1

share|improve this answer
    
Ok, I am assuming n>>m. Besides, the concept of a diagonal matrix is ambiguous for scalars. –  silvanmx Mar 29 '12 at 20:15
3  
@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
1  
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
add comment

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

share|improve this answer
1  
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
add comment

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.