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

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

  • 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
  • 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

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

  • 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

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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