Let $A$ be an $m \times n$ matrix such that $\mathrm{rank}(A) = n \le m$. Prove, or disprove using a counter example:

Every $m\times n$ matrix $Y$ has a decomposition $Y = AX-C$, where $X$ and $A^TC$ are nonnegative semidefinite symmetric matrices.

I have a feeling this is false, but I can't come up with a good counter example to show this. I've been trying to find a $Y$ such that $X$ would have to be non semidefinite to construct this $Y$.

Is it possible that the statement is true?

This is a problem from a book on semidefinite optimization.

Any insights would be greatly appreciated.


  • $\begingroup$ @MichaelC.Grant: I don't see anything wrong with fixing a matrix and asking if every matrix has a decomposition in terms of the first one and and some others. Is that what was intended, user? $\endgroup$ – Eric Stucky May 16 '13 at 2:37
  • $\begingroup$ My suspicion is that something is missing from the statement. Care to point us to the reference you're talking about? I do semidefinite programming as part of my work, I might be familiar with the text. $\endgroup$ – Michael Grant May 16 '13 at 2:51

Your proposition is false as stated.

Let $A$ be the $n\times n$ identity matrix. Then the decomposition reduces to $X-C$, where both $X$ and $C$ are symmetric. Clearly no asymmetric $Y$ has such a decomposition.

  • $\begingroup$ Thank you so much for your help. I can't believe I didn't see this before $\endgroup$ – user70864 May 16 '13 at 5:26
  • $\begingroup$ That's why I think there's something missing from the statement. I don't think a counterexample this basic would be likely to be missed by the authors. Can you please share the reference? $\endgroup$ – Michael Grant May 16 '13 at 12:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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