1
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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$? $\endgroup$ Mar 30, 2012 at 0:02
  • $\begingroup$ I meant your second interpretation. Sorry for the confusion. $\endgroup$
    – silvanmx
    Apr 2, 2012 at 15:54

4 Answers 4

3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Looks like your answer is right! Thanks. $\endgroup$
    – silvanmx
    May 4, 2012 at 19:10
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

In general no, take n = m = 1

$\endgroup$
5
  • $\begingroup$ Ok, I am assuming n>>m. Besides, the concept of a diagonal matrix is ambiguous for scalars. $\endgroup$
    – silvanmx
    Mar 29, 2012 at 20:15
  • 3
    $\begingroup$ @silvanmx: What is the ambiguity? I would have thought every 1-by-1 matrix is diagonal (unambiguously). $\endgroup$ Apr 2, 2012 at 16:00
  • $\begingroup$ 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. $\endgroup$
    – silvanmx
    Apr 2, 2012 at 16:31
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 2, 2012 at 17:17
  • $\begingroup$ 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 $\endgroup$
    – silvanmx
    May 4, 2012 at 19:22
-1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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