# Lattice reduction on an orthonormal lattice?

Suppose you are given an inner product on a vector space and given a set of linearly independent vectors, and that you have been promised that the lattice they span has an orthonormal basis. Can you (quickly) figure out what that basis is?

Note that this may be much easier than finding the shortest vector in a general lattice, since (for instance) you know ahead of time exactly how long the shortest vector actually is.

Motivation: Suppose you wanted to use Brauer's induction theorem to compute the character table of a big group. After computing enough induced characters, you can check (by calculating a suitable determinant) that you have a set of representations generating the Grothendieck group. You know ahead of time that the irreducible representations form an orthonormal basis - so it's natural to ask whether you can use this information to quickly figure out what the characters actually are.

-
So, more or less, given a symmetric positive definite matrix $G$ of integers with determinant $1,$ and knowing it to be possible, you want to find an integer matrix $P$ such that $P^T P = G.$ My programs find all such expressions, essentially by finding all possible first columns of $P,$ then all possible second columns, and so on. Then for each first column, I find all second columns giving the correct inner product, continue to the third column when successful. It is fast enough for me. –  Will Jagy Nov 3 '12 at 0:48
That should work, but... I was kind of hoping for some kind of theoretical guarantee about worst-case performance. –  zeb Nov 3 '12 at 0:55
No idea. ${}{}{}$ –  Will Jagy Nov 3 '12 at 1:04

If there is an orthonormal basis, the lattice is $Z^n$ and one can try to find all the $n$ norm 1 vectors up to sign. If $v_j$ is your given basis and $w=\sum x_j v_j, x_j \in Z$ is of norm one and $v_i^*$ is the dual basis ($<v_i^*,v_j>=\delta_{ij}$), then $|x_i|=|<v_i^*,w>| \le |v_i^*|$. If $G_{ij}=<v_i,v_j>$ is the Gram matrix from the given basis, then $G^{-1}=<v_i^*,v_j^*>$ is the Gram for the dual lattice. So one only need to search the finitely many $x \in Z^n$ with $|x_j| \le \sqrt{(G^{-1})_{jj}}$ for all $j$ to solve $x^TGx=1$. This gives a worst-case bound but it is still exponential in $n$.
But I think one should just quickly find a few $w$ and reduce the problem by looking in the orthogonal complement. If $w_1,...w_k$ are norm 1 vectors found generating a sub-$Z^k$,then the orthogonal projection $v_j'$ of any $v_j$ on the orthogonal complement to the space spanned by the $w's$ must be a lattice vector. We now pick $v_j'$ only if the rank of the ortho-complement increased by one until we find a generating set of $n-k$ $v_j'$ and we now have a problem in lower dimension.