$Euclidean lattices with a metric part 2$

Question

$Euclidean lattices with a metric part 2$

Let $L_1, L_2 \subseteq \mathbb{R}^n$ be full-rank Euclidean lattices with generating matrices $A, B$ respectively (representing Minkowski-reduced bases), and let $d(A,B)< \epsilon$, for some fixed positive real $\epsilon$. Then do there exist $\gamma, \delta \in \mathbb{R}^{+}$ (depending on $A,B, \epsilon$) such that \[\gamma < |Ax_1-Bx_1|< \delta,\]

where $x_1 \in \mathbb{R}^n$ is such that $Ax_1$ is the shortest nonzero vector of $L_1$?

One clue could be that $\gamma, \delta$ somehow depend on the smallest and largest (in absolute value) eigenvalues of $A,B$.

Definition of $d(A,B)$: Given (full rank) lattices $L_1 = (a_{ij}), L_2=(b_{ij}) \in \mathbb{R}^n$ with gen. matrices $A, B$ respectively, we define \[d(L_1,L_2)=\sqrt{\sum_{i=1}^n \sum_{j=1}^n}(a_{ij}-b_{ij})^2.\]

Linear Algebra Algebra Eigenvalues & Eigenvectors

Ribs

98

Report

Answer

The answer is accepted.

Join Matchmaticians Affiliate Marketing Program to earn up to a 50% commission on every question that your affiliated users ask or answer.

Answer 1

Answers can only be viewed under the following conditions:

The questioner was satisfied with and accepted the answer, or
The answer was evaluated as being 100% correct by the judge.

View the answer

There cannot be a positive lower bound in general as the case $B=A$ shows. But there is an upper bound:
$$ |Ax_1 -Bx_1 |^2=|(A-B)x_1 |^2=\sum _{i,j} (a_{ij}-b_{ij})^2 x_{1j}^2 \\ \le |x_1 |^2 \sum _{i,j} (a_{ij}-b_{ij})^2 <\epsilon ^2 |x_1 |^2 :=\delta ^2$$ Now note that as $A$ is full rank $x_1$ is uniquely determined by the the shortest nonzero vector, which itself is determined by $A$. So $\delta$ depends on $A,\epsilon$.

For lower bound: $$ |Ax_1 -Bx_1|=|(A-B)x_1|\ge\sigma_n(A-B)|x_1 |$$ where $\sigma_n$ is the smallest singular value of $A-B$.

Martin

1.6K

Ribs

0

I see, thanks! Can we find a lower bound if we restrict to B not equal to A?
- Martin
  
  0
  
  As long as Ax1=Bx1 we have the same problem. But if they are not equal then their difference has a positive norm obviously, and since x1 is determined by A, then Bx1 is determined by A,B. So assuming Ax1 is not equal to Bx1, then there is a lower bound depending on A,B.
Ribs

0

Alright, thanks! Can we say anything about that lower bound in the latter case, given that the distance between A, B is less than epsilon, for example? Or using eigenvalues somehow?
- Martin
  
  0
  
  You're welcome. The epsilon is not needed for lower bound. But using the smallest singular value of A-B and norm of x1 we can have a more concrete estimate. see this : https://en.wikipedia.org/wiki/Min-max_theorem#Min-max_principle_for_singular_values
- Martin
  
  0
  
  I also added this to the end of the solution.

$Euclidean lattices with a metric part 2$

Answer

Related Questions

Search