Let $n \in \mathbf{N}$ be a natural number and $v\_1,\cdots,v\_n$ a set of basis vectors in $\mathbb{R}^n$. How does one find the matrix $g \in \mathbf{GL}\_n(\mathbb{Z})$ orthogonalizing these best possible? That is, such that $\max \{|(g v\_i,g v\_j)|/ ||g v\_i|| ||g v\_j|| : i \not= j \in \{1,\cdots,n\}\} \in [0,1]$ is minimal among all $g \in \mathbf{GL}\_n(\mathbb{Z})$. (Here $(.,.)$ denotes the standard euclidean scalar product and $||.||$ its induced norm.)


To turn this into a more precise question: Let $n, v=(v\_1,\dotsc,v\_n)$ and $g$ be as above. Let $o(g,v) = \max \{|(g v\_i,g v\_j)|/ ||g v\_i|| ||g v\_j|| : i \not= j \in \{1,\cdots,n\}\} \in [0,1]$ be the above maximum and put $o(v)=\inf \{o(g,v) : g \in \mathbb{GL}\_n(\mathbf{Z})\}$. Is $I(n)=\sup \{o(v) : v \in \mathbf{GL}\_n(\mathbb{R})\}$ known? If not, what is the lowest known upper bound?



Most orthogonal lattice basis
It seems you are asking about [Lattice reduction](http://en.wikipedia.org/wiki/Lattice_reduction), this subject goes back to 19-th century to Hermite, Minkowski and others, but it is of certain interest up to current days, since it is used in commercial GPS navigation and there is academic research on application to multi antenna receivers (MIMO) (e.g. just week ago [Integer-Forcing Linear Receivers Based on Lattice Reduction Algorithms](http://arxiv.org/abs/1209.6412)).


I do not think the precise answer to your question is known in dimensions higher than 2.
Actually in dimension higher than 2 the criteria of "most orthogonal" is not unique,
I am not sure the criteria you choose is the most natural one and has been researched.


Any way to find "most orthogonal" (in some sense) seems to be hard problem (NP).


There are different versions of lattice reduction which differs in a definition of "most orthogonal" and in ambition how precisely they want to achieve this orthogonality.


One of the most popular ones is LLL-reduction which has polynomial complexity and can achieve quite good approximation of "orthogonality" (estimates are known).


More complex reduction goes back to Korkine, Zolotarev; Hermite and Minkowski,
they have been also investigated recently, you can find reference in the paper cited above or in Wikipedia. 


I am not great expert in the subject, there are actually some questions on MO
which are related to yours [about R^3, R^4](https://mathoverflow.net/questions/61933/lattice-reduction-in-r3-r4-or-what-is-fundamental-domain-for-sl3-z-sl4), [other norms](https://mathoverflow.net/questions/37563/other-norms-for-lattice-reduction-techniques-lll-pslq), [CVP for reduced latice](https://mathoverflow.net/questions/62116/closest-vector-problem-nearest-lattice-point-is-trivial-for-reduced-lattice) (some of them asked by me :-).


PS


I am sure you know this, just for completeness. In dimension 2 everything is fine - you can put any lattice by SL(2,Z)
to the "standard form" - fundamental area of SL(2,Z), see picture [here](http://en.wikipedia.org/wiki/Modular_group#Tessellation_of_the_hyperbolic_plane) (gray colored area) ( assume that first vector is (1,0)). 


