# Simple question on complexity models w.r.t linear algebra

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

• What do you mean by "the complexity of $B$"? – Shir Feb 14 '12 at 7:29
• What do you mean by "the complexity of the transformation"? – Jeffε Feb 14 '12 at 9:10
• I assume he means the complexity of computing what are $X$ and $Y$. – Shir Feb 14 '12 at 11:59
• 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? – Jeffε Feb 15 '12 at 10:14
• 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$?” – Jeffε Feb 16 '12 at 13:52