2
$\begingroup$

For any matrix $B$, there are matrices $X$ and $Y$ such that the product $XBY$ is a diagonal matrix. Suppose $B$ is an $n \times n$ non-singular matrix with $b$-bit integer entries and no repeated eigenvalues. What is the worst-case bit complexity of $X$ and $Y$ as a function of $b$ and $n$ (say when you fix an approximation error for the diagonal matrix as a function of $n$ and $b$)? Also what is the complexity of computing $X$ and $Y$?

$\endgroup$
  • 1
    $\begingroup$ What do you mean by "the complexity of $B$"? $\endgroup$ – Shir Feb 14 '12 at 7:29
  • 3
    $\begingroup$ What do you mean by "the complexity of the transformation"? $\endgroup$ – Jeffε Feb 14 '12 at 9:10
  • $\begingroup$ I assume he means the complexity of computing what are $X$ and $Y$. $\endgroup$ – Shir Feb 14 '12 at 11:59
  • 2
    $\begingroup$ Shir and Janoma suggest two (or three) natural answers to my question. Hence my question. @vs, could you please edit your original question to make it unambiguous? $\endgroup$ – Jeffε Feb 15 '12 at 10:14
  • 1
    $\begingroup$ So do you mean the following? “For any matrix $B$, there are matrices $X$ and $Y$ such that the product $XBY$ is a diagonal matrix. Suppose $B$ is an $n\times n$ non-singular matrix with $b$-bit integer entries and no repeated eigenvalues. What is the worst-case bit complexity of $X$ and $Y$ as a function of $b$ and $n$?” $\endgroup$ – Jeffε Feb 16 '12 at 13:52

Your Answer

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

Browse other questions tagged or ask your own question.