Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Assume that $ A $ is a real $ n\times n $ matrix whose rows constitute an orthonormal basis of $ \mathbb R^n $.

Informal statement of question: Assume we want to approximate $ A $ by a rational matrix, such that each entry can be written efficiently (that is, has a small binary encoding), but we require also the inverse of the approximate matrix to have small representation. Is this possible?

Formal statement of question: Let $ p(n) $ be some polynomial in $ n $. For a real number $ r $, we say that $ a/b $ is a polynomial approximation of $ r $, if $ a/b$ is a rational number (that is, $ a,b $ are integers) and both $ a $ and $ b $ are of size at most $p(n) $ (e.g., their binary representation is of logarithmic size in $ n $), such that $ |r-a/b|\le 1/p(n) $.

Question: Does there exist a rational matrix $ B$, such that $ B $ polynomially approximates $ A $ (that is, the entry $ B_{ij} $ in $ B $, is a polynomial approximation of the entry $ A_{ij} $ in $ A $, for all $ 1\le i,j\le n $), and such that $ B^{-1} $ is a rational matrix whose entries are all polynomially-bounded (that is, for any $ 1\le i,j\le n $, $ B^{-1}_{ij}=a/b$, where $ a,b $ are integers of size at most $ p(n) $) ?

share|improve this question
add comment

2 Answers

In $\mathbb{R}^3$, Milenkovic and Milenkovic give an alogrithm for efficiently approximating an orthogonal matrix by a rational orthogonal matrix. As lhf points out, the inverse of an orthogonal matrix is its transpose, so the inverse will also have short entries in this setting.

Regarding $n>3$, here is a tentative thought, and a reference. I haven't put much effort into either :).

Let $v=(v_1, v_2, \ldots, v_n)$ be a nonzero vector. Define a linear operator $$s_v(u) := u - 2 \frac{\langle v,u \rangle}{\langle v,v \rangle} v.$$ This is the orthogonal reflection that negates $v$. Note that, if $v \in \mathbb{Q}^n$, then the entries of the matrix $s_v$ are rational. This is true even if $v$ does not have norm $1$.

Now, any rotation matrix can be written as a product of $\leq n$ reflections: $R=\prod_{i=1}^h s_{v_i}$ for some sequence of vectors $v_i$ in $\mathbb{R}^n$. A potential algorithm, then, is to find such a factorization and then approximate each $v_i$ by a rational vector $w_i$ which is roughly parallel to it. (There are plenty of standard algorithms for rational approximation of a vector.) Then take $\prod s_{w_i}$ as the approximation to $R$.

I got this strategy from a paper of Eric Schmutz. Schmutz follows this strategy, but he forces his approximating vectors $w_i$ to lie on the unit sphere. As far as I can see, this is a waste of effort, since $s_v$ is orthogonal with rational entries even if $v$ is not on the unit sphere. However, Schmutz has exact bounds, which you may find useful.

share|improve this answer
    
Thanks, I'll have a look. Maybe they (or future citations of this paper) have some references for the general case of $ n $. –  Iddo Tzameret Jun 30 '10 at 18:09
    
I haven't followed through on the links, so I don't know which method do they use, but my first reaction to "rational orthogonal matrix" is "Cayley transform". –  Victor Protsak Jul 1 '10 at 5:45
add comment

If A is orthogonal then its inverse is the transpose and so you only need to approximate A.

share|improve this answer
3  
But your approximation may not be orthogonal, so its inverse may require a lot of bits to store. –  David Speyer Jun 30 '10 at 17:45
    
Yes, David is right. (lhf would be right too, if the orthogonalization algorithm (of e.g., Gram-Schmidt) would end up with a matrix in which the entries are polynomially-bounded by the entries in the original matrix. I can't see why this should be true though.) –  Iddo Tzameret Jun 30 '10 at 18:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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