Welcome to MathOverflow

Question

4

1

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?

edited Oct 16 at 17:57

asked Oct 16 at 14:02

Tiffy
87●4

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}$. – Robert Bryant Oct 16 at 16:55

Thanks for your corrections. I hope the precise part is clearer now. – Tiffy Oct 16 at 17:50

1

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. – Alexander Chervov Oct 17 at 6:58

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. – Tiffy Oct 17 at 11:08

Alexander Chervov · Accepted Answer · 2012-10-18 07:53:52Z UTC

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 :-).

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

Most orthogonal lattice basis

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.