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?

  • $\begingroup$ In your definition of $o(g,\nu)$, do you want to require that $i\neq j$? Otherwise, I'm pretty sure that you'll have $o(g,\nu)=1$. Also, you probably want to fix $\nu$ in your infimum, i.e., define $I(\nu)$ instead of $I(n)$, since, otherwise, the answer will be $0$ if you take $\nu$ to be orthonormal. Even then, I think it's highly likely that $I(\nu)=0$, just because, projectively, the set of nonzero elements in a lattice will be dense in $\mathbb{RP}^{n-1}$. $\endgroup$ – Robert Bryant Oct 16 '12 at 16:55
  • $\begingroup$ Thanks for your corrections. I hope the precise part is clearer now. $\endgroup$ – Tiffy Oct 16 '12 at 17:50
  • 1
    $\begingroup$ It seems to me you are asking about lattice reduction en.wikipedia.org/wiki/Lattice_reduction I do not think that there is known "good" algorithm to find "g" which you require. Actually there are several versions of lattice reduction - they are different in giving precise sense to "most" orthogonal. $\endgroup$ – Alexander Chervov Oct 17 '12 at 6:58
  • $\begingroup$ Thank you Alexander. I thought this to be a common problem in other areas of mathematics I am not well acquainted with and was lingering for literature references. $\endgroup$ – Tiffy Oct 17 '12 at 11:08

It seems you are asking about 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).

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, other norms, CVP for reduced latice (some of them asked by me :-).


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 (gray colored area) ( assume that first vector is (1,0)).

  • $\begingroup$ Thank you, Alexander. This is already more or less what I hoped for at this place: A name tag for this particular kind of problem together with some additional hints to further literature. $\endgroup$ – Tiffy Oct 18 '12 at 13:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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