6
$\begingroup$

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

$\endgroup$

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks, I'll have a look. Maybe they (or future citations of this paper) have some references for the general case of $ n $. $\endgroup$ Jun 30, 2010 at 18:09
  • $\begingroup$ 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". $\endgroup$ Jul 1, 2010 at 5:45
3
$\begingroup$

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

$\endgroup$
2
  • 3
    $\begingroup$ But your approximation may not be orthogonal, so its inverse may require a lot of bits to store. $\endgroup$ Jun 30, 2010 at 17:45
  • $\begingroup$ 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.) $\endgroup$ Jun 30, 2010 at 18:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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