3 edited body

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 - s 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.

2 added 1281 characters in body

Regarding $n>3$, here is a tentative thought, and a reference. I don't know about 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 - s \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$ larger than reflections: $3$.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. 1 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. I don't know about$n$larger than$3\$.