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

CC BY-SA 3.0
2012-02-14T07:29:06.900Z
What do you mean by "the complexity of $B$"?
Shir
CC BY-SA 3.0
2012-02-14T09:10:38.827Z
What do you mean by "the complexity of the transformation"?
Jeffε
CC BY-SA 3.0
2012-02-14T11:59:08.853Z
I assume he means the complexity of computing what are $X$ and $Y$.
Shir
CC BY-SA 3.0
2012-02-14T15:29:25.350Z
I think he means the complexity of the representation (that's why he mentions the bitsize of the digits). Maybe he's asking whether the Kolmogorov complexity of $D$ can be (strictly) greater than the Kolmogorov complexity of $B$ for some $X$ and $Y$.
Janoma
CC BY-SA 3.0
2012-02-14T18:30:39.693Z
If $B$ is varying form, then even though it seems like $XBY$ can be done in $O(n^{\omega})$, will the bit complexity of involved operations blow-up (if not, then why not)?
v s
CC BY-SA 3.0
2012-02-15T10:14:06.317Z
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ε
CC BY-SA 3.0
2012-02-16T13:52:33.457Z
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ε
CC BY-SA 3.0
2012-02-16T17:57:49.077Z
@JɛﬀE Your question is more precise. I will also include Shir's question as well since that is an useful extension.
v s
CC BY-SA 3.0
2012-02-17T00:13:30.207Z
Hi @J.D. Could you provide some references on your opinion?
v s
CC BY-SA 3.0
2012-02-17T10:00:52.350Z
The additional comment about approximation error changes the question significantly!  I assumed you were asking about  _exact_ representations.  Are you allowing errors only in the diagonal entries of D, or are you also allowing small non-zero values off the diagonal?
Jeffε
CC BY-SA 3.0
2012-02-17T14:49:11.723Z
@JɛﬀE Two things: 1) I do not know if it is always possible to have exact representations (wouldn't it be possible to artificially cook up an example where the diagonal entries are irrational) 2) What do you mean by off-diagonal entries (the only error I assume here is quantization noise)?
v s
<cc.complexity-theory>
Simple question on complexity models w.r.t linear algebra
v s
# Simple question on complexity models w.r.t linear algebra

(Asked by: username_0 on 2012-02-14)

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

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: What do you mean by "the complexity of $B$"?  
> **username_2**: What do you mean by "the complexity of the transformation"?  
> **username_1**: I assume he means the complexity of computing what are $X$ and $Y$.  
> **username_3**: I think he means the complexity of the representation (that's why he mentions the bitsize of the digits). Maybe he's asking whether the Kolmogorov complexity of $D$ can be (strictly) greater than the Kolmogorov complexity of $B$ for some $X$ and $Y$.  
> **username_0**: If $B$ is varying form, then even though it seems like $XBY$ can be done in $O(n^{\omega})$, will the bit complexity of involved operations blow-up (if not, then why not)?  
> **username_2**: username_1 and username_3 suggest two (or three) natural answers to my question.  Hence my question.  @vs, could you please edit your original question to make it unambiguous?  
> **username_2**: 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$?”  
> **username_0**: @JɛﬀE Your question is more precise. I will also include username_1's question as well since that is an useful extension.  
> **username_0**: Hi @J.D. Could you provide some references on your opinion?  
> **username_2**: The additional comment about approximation error changes the question significantly!  I assumed you were asking about  _exact_ representations.  Are you allowing errors only in the diagonal entries of D, or are you also allowing small non-zero values off the diagonal?  
> **username_0**: @JɛﬀE Two things: 1) I do not know if it is always possible to have exact representations (wouldn't it be possible to artificially cook up an example where the diagonal entries are irrational) 2) What do you mean by off-diagonal entries (the only error I assume here is quantization noise)?  

---

## 0 answers

