(Integer) Lattices: Proving Hadamard result $det(L) = \prod_{i=1}^n ||b_i||$ if and only if $B$ is a basis of $L$ and an orthogonal basis of $V$

Question

I am studying lattices and I have a question about a proof that cannot find anywhere.

We assume that we know the basics about lattices (definition, basis, dual, determinant, Minkowski 1st and 2nd Theorems, ...)

For introducing the LLL algorithm, I describe the Gram-Schmidt orthogonalization process and immediatly after that I state a result of Hadamard:

For all lattice $L \subseteq \mathbb{R}^n$ and all family $B=\{b_1,\ldots,b_n\} \subseteq L$ where the $b_i$ are linearly independent over $\mathbb{Z}$:

1. $det(L) \leq \prod_{i=1}^n ||b_i||$;

2. $det(L) = \prod_{i=1}^n ||b_i||$ if and only if $B$ is a basis of $L$ and an orthogonal basis of $V$.

The first statement and its proof can be found almost anywhere but the second one is giving me some trouble.

For $\Leftarrow$, since $B$ is an orthogonal basis of $V$, the Gram-Schmidt vectors $b_1^*,\ldots,b_n^*$ satisfy $b_1^*=b_1,\ldots,b_n^*=b_n$. Thus $det(L)=\prod_{i=1}^n||b_i^*||=\prod_{i=1}^n||b_i||$ (the first equalty is a lemma that I proved for the first part).

For $\Rightarrow$, we first have to see that $B$ generates $L$ (the linear independency follows by hypothesis). We take $x \in L$ and $\{l_1,\ldots,l_n\}$ a basis of $L$. We can now write the $b_i$ as linear combination of $l_1,\ldots,l_n$. But here we cannot take the inverses of elements of $\mathbb{Z}$, neither use Steinitz Theorem (because $\mathbb{Z}$ is not a field). This is the first thing I have trouble. For proving that is a basis of $V$, it is in general false that the linear independancy over $\mathbb{Z}$ implies the linear independency over $\mathbb{R}$. Proving that $B$ generates $V$ is the same as the first trouble.

How can I prove $\Rightarrow$?

Answer 1

Let $a_1, \ldots , a_n$ be the basis for $L$. By linear independence of $b_1, \ldots, b_n$ over $\mathbb{Z}$, we have an integer matrix $M$ such that $$ [b_1 \cdots b_n] = [a_1 \cdots a_n] M, \ \ \det M \neq 0. $$

Now, this proves that the vectors $b_1, \ldots , b_n$ are linearly independent. Then, the QR decomposition gives nonsingular upper triangular matrix $R$. In fact $R$ has all $1$'s on diagonal entries.

$$ \begin{bmatrix}{ b_1 \cdots b_n }\end{bmatrix} = \begin{bmatrix}b_1^* \cdots b_n^*\end{bmatrix}\begin{bmatrix} 1&c_{12} & & \cdots & c_{1n} \\ 0 & 1 & c_{22} & \cdots & c_{2n}\\ 0 & 0 &1& \cdots&\vdots \\ 0& \cdots & \cdots &1 & c_{n-1,n}\\ 0& \cdots & \cdots &0 &1\end{bmatrix} $$ This gives $\det [b_1 \cdots b_n] = \det \begin{bmatrix}b_1^* \cdots b_n^*\end{bmatrix}$.

By Pythagorean theorem for inner product space, $$ ||b_1||^2 = ||b_1^*||^2 \geq ||b_1^*||^2, $$ $$ ||b_2||^2 = || c_{12} b_1^*||^2 + ||b_2^*||^2\geq ||b_2^*||^2, $$ $$\cdots $$ $$ ||b_n||^2 = || c_{1n} b_1^*||^2 + ||c_{2n} b_2^*||^2 + \cdots + ||c_{n-1,n} b_{n-1}^*||^2 + ||b_n^*||^2 \geq ||b_n^*||^2.$$

This gives $$ |\det [b_1 \cdots b_n]|^2 =|\det [b_1^* \cdots b_n^*] |^2\leq \prod ||b_i||^2 $$ Note that the inequalities above become equalities if and only if all $c_{ij}$ is zero. By the way that $c_{ij}$ are made through Gram Schmidt process, we indeed have $$\langle b_i, b_j\rangle =0 \ \ \textrm{ for all distinct }i, j.$$

In fact, $\det L = \prod ||b_i||$ gives, $$ |\det [b_1 \cdots b_n ]|^2 = |\det L \det M|^2 = (\prod ||b_i||^2 ) |\det M|^2\leq \prod ||b_i||^2. $$ The inequalities above become equalities if and only if $\det M = \pm 1$. This proves that $b_1, \cdots b_n$ generates $L$ and they are orthogonal basis for $\mathbb{R}^n$.