2 Shorten title

1

# Efficiently-represented approximation of matrix, whose inverse is also efficiently representable

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