Hello Again,
So did you try out the problems listed at the end of the previous post?
That was fun, right?
Anyway, in case you did not get the solution (or did not try the problem at all) here is the solution.
(Please note that the following material draws heavily from Oded Regev lecture notes)
We will solve the more general problem of determining Base Equivalence first. That is given $2$ bases $B_{1}$ and $B_{2}$ we will determine whether they lead to the same lattice. This will help with the the problem of determining whether the given lattice hits all points in $Z^n$ as well because we know that $I$ hits all points in $Z^n$ and we know the condition when a base $B$ is equivalent to $I$. Actually we know more. We not only know "how to determine whether given $B$" is equivalent to $I$; we also know "how to create such a $B$".
First of all we notice that a given Base $B_{1}$ and another base $B_{2}$ obtained by permutation of its columns are equivalent (why? hint - its too easy).
Any other base $B_{2}$ equivalent to $B_{1}$ will have the same number of "effectively independent vectors". Further, we would expect that the set of vectors is effectively the same - both are clearly integer combinations of each other,
Something tells us that column operations on $B_{2}$ can convert it to the equivalent matrix $B_{1}$.
Further, if $B_{1}$ is full rank so that $det$($B_{1}$$)$ is defined, we hope that $det$($B_{2}$$)$ would be same in magnitude as $det$($B_{1}$$)$. So, that looks like the rule; perhaps both the matrices should have the same determinant in magnitude.
Hmm..So we can say that if $B_{1}$ = $B_{2}$$U$ (and $B_{2}$ = $B_{1}$$V$) for some unimodular matrix $U$ (and Unimodular $V),$ $B_{1}$ and $B_{2}$ are equivalent.
By the way Unimodular matrices are those which have determinant $+1$ or ($-1$) and have all $B_{ij}$'s integral.
But wait. We talked about lattices with full rank bases. What if rank is not full?
Well, you can prove that these rules hold in general.
This helps you see that if you want your Basis to hit $Z^n$, your matrix needs to be a unimodular matrix times $I$; in short your matrix needs to be unimodular itself.
Now lets actually prove the following proposition
Two bases $B_{1}$, $B_{2}$ $\epsilon$ $\RR^{m*n}$ are equivalent if and only if $B_{2}$ = $B_{1}$$U$ for some unimodular matrix $U$.
Subscribe to:
Post Comments (Atom)
Great post. Keep it coming :).
ReplyDeleteLets try to prove the statement above.
$(\Leftarrow)$
Let $x$ be an integral vector. Take $y=Ux$. This $y$ also an integral vector (since $U$ is unimodular). It follows that $B_2x=B_1y$. NOw for $z=U^{-1}x$ ($z$ is clearly integral) we also have $B_1x=B_2z$. Hence $B_1$ and $B_2$ are equivalent.
$(\Rightarrow)$
Suppose $B_1,B_2$ are equivalent. Then there are integer vectors $x_i$ such that
\[B_2e_i=B_1x_i\]
But $B_2e_i$ is exactly the $i$th column of $b_2$. Hence
\[B_2=B_1X\]
where $X$ is the matrix such that its ith column is $x_i$.
By similar argument there is an integer matrix $Y$ such that $B_1=B_2Y$. It follows that
\[B_1=B_1XY\]
Hence $\det(XY)=1$ which implies that $\det(X)=\pm 1$. So $X$ is unimodular.
Nice one watchmath (may i have your name please)
ReplyDeleteAnd thanks a lot for enabling us write blogs with mathematical symbols.
Really great work (and a nice proof!)
I would just like to mention that the readers might want to look up the "fundamental parallelopiped" criterion for a set of n linearly independent vectors to qualify as a basis for a lattice. That too is one of the reasons behind hoping that two equivalent bases must have equal determinants.
ReplyDelete