3
$\begingroup$

I came across an interesting problem in my research (not a mathematician). Here it goes:

Suppose, there is a 2D lattice $\Lambda$ in the X-Y plane with basis vectors $\vec{a}$ and $\vec{b}$, which are not orthogonal to each other. I want to find a rectangle in this lattice, whose area is the minimum of all possible rectangles. So far, this is what I have:

Consider two vectors in the lattice:

$\vec{v_1} = m_1 \vec{a} + n_1 \vec{b}$

$\vec{v_2} = m_2 \vec{a} + n_2 \vec{b}$

If they are orthogonal, then $\vec{v}_1 \cdot \vec{v}_2 = m_1 m_2 \left| \vec{a} \right|^2 + n_1 n_2 \left| \vec{b} \right|^2 + (m_1 n_2 + n_2 m_1) \vec{a} \cdot \vec{b} =0 $

The area subtended by the two vectors is the norm of the cross product, i.e. $\left| \vec{v}_1 \times \vec{v}_2 \right| = \left| \vec{a}_1 \times \vec{b}_2 \right| \left|m_1n_2 - m_2n_1 \right|$

Therefore, the area is minimized if $\left|m_1n_2 - m_2n_1 \right|$ is minimized and greater than zero. And the constraint is:

$m_1 m_2 \left| \vec{a} \right|^2 + n_1 n_2 \left| \vec{b} \right|^2 + (m_1 n_2 + n_2 m_1) \vec{a} \cdot \vec{b} =0$

I am stuck after this! May be some kind of optimization with a constraint using Lagrange multipliers? But there are too many variables and $m_1, m_2, n_1, n_2 \in \mathbb{Z}$. Any suggestions will be greatly appreciated. Thank you for your time.

|cite|improve this question
$\endgroup$
  • $\begingroup$ I will work on it. Note that there is no guarantee of existence without some constraint, essentially that all lattice vectors have squared length rational, better integral...Hmmm; actually the standard condition is that all inner products be integers. $\endgroup$ – Will Jagy Oct 14 '14 at 2:14
  • $\begingroup$ Thank you, Will. I agree that there is no guarantee that a solution exists. I might be able to think of the constraints for existence as I improve my intuition for this problem. Thanks! $\endgroup$ – Srikanth Oct 14 '14 at 2:30
  • $\begingroup$ Sri.. put second answer with a necessary condition. It can be used to prove non-existence of orthogonal vectors in some lattices. $\endgroup$ – Will Jagy Oct 15 '14 at 3:20
  • $\begingroup$ It turns out that the condition I give in my second answer is necessary and sufficient for existence of a pair of orthogonal vectors in your lattice. Calculations put into third answer, with some examples. None guaranteed to be optimal, though, just to exist. $\endgroup$ – Will Jagy Oct 15 '14 at 21:51
  • 1
    $\begingroup$ Thank you for putting in so much effort on this, Will. I didn't even know what a gram matrix is and how it may be useful before this discussion. I think I understand the existence conditions now. I will try this on a few examples and will let you know! Thank you again. $\endgroup$ – Srikanth Oct 17 '14 at 16:28
2
$\begingroup$

There seems to be an answer if the lattice can be rotated and scaled so that all inner products of lattice vectors are integers (positive definite..) and there is no common integer factor of the entries in the gram matrix; $\gcd(A,B,C)=1.$ We also may demand that $A$ be the squared length of the shortest nonzero lattice vector.

http://en.wikipedia.org/wiki/Unimodular_lattice#Definitions

http://en.wikipedia.org/wiki/Gramian_matrix#Gram_determinant

As far as i can tell, in this case, the best answer is a non-primitive lattice, given by identity $$ \left( \begin{array}{rr} 1 & 0 \\ -B & A \end{array} \right) \left( \begin{array}{rr} A & B \\ B & C \end{array} \right) \left( \begin{array}{rr} 1 & -B \\ 0 & A \end{array} \right) = \left( \begin{array}{cc} A & 0 \\ 0 & A (AC - B^2) \end{array} \right) $$ This is a short version of Gauss-Legendre composition for integral binary quadratic forms.

Oh, almost forgot. You actually want the lattice reduced. Furthermore, if $B$ is a multiple of $A,$ then the lattice is already $SL_2 \mathbb Z$ equivalent to a diagonal one.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I will need a little more time to completely understand this! I will accept this as an answer as soon as possible... Thanks, Will. $\endgroup$ – Srikanth Oct 14 '14 at 17:22
  • $\begingroup$ @Srikanth, this is the setting, number theory, where I can give a substantial answer. As an example that does not fit this, take vector $v=(1,0)$ and $w=(-5,\pi).$ There is an evident orthogonal pair, $v, 5v+w,$ but I do not currently know much about this situation...for example, if there is an orthogonal pair, is the shortest vector one of them? Don't know yet. If so, that would give a quick test for existence. $\endgroup$ – Will Jagy Oct 14 '14 at 18:29
  • $\begingroup$ @Srikanth so, look up "binary quadratic form reduction" the concepts are the same. Given a symmetric matrix $G$ and a column vector $X,$ we get a quadratic form from $X^T G X.$ $\endgroup$ – Will Jagy Oct 14 '14 at 18:59
  • $\begingroup$ Thank you for the resources, Will. I get your solution now but I am still not sure about the existence condition. I will take a look at the binary quadratic form reduction. Thank you! $\endgroup$ – Srikanth Oct 15 '14 at 0:59
2
$\begingroup$

THIRD answer: It turns out the condition I gave in my second answer is necessary and sufficient for existence; I can also show a two parameter family, I'm afraid to minimize could be algorithmic but not formulaic. i will have time for that aspect later. Given Gram matrix with $A,B,C$ as before, we have the equation $$ A \alpha \beta + B (\alpha \delta + \beta \gamma) + C \gamma \delta. $$ So need to have $iA + jB + kC = 0,$ with $j^2 - 4ik = w^2.$

So, take integer parameters $s,t,$ then $$ \alpha = 2i s, \; \; \beta = 2 it, \; \; \gamma = (j-w)s, \; \; \delta = (j+w)t. $$ With these values, the vector $( \alpha \beta, \alpha \delta + \beta \gamma, \gamma \delta)$ is a scalar (rational) multiple of $(i,j,k),$ and we have constructed orthogonal vectors in the lattice. It is possible that $\gcd(\alpha, \beta, \gamma,\delta)> 1$ for some values of $(s,t)$ but not others.

Furthermore, minimization of the determinant $|\alpha \delta - \beta \gamma|$ needs work, although it is a multiple of $w$ by construction. Here is a start: $$ \alpha \delta - \beta \gamma = 4iwst. $$ Need to think about what that means, with varying GCD's and the possibility of zero values for $s,t.$ SIGH. Added: no, if one of $s,t$ is zero, one vector in the orthogonal pair is just the zero vector, so we may rule out that possibility. Good. So, it may not be smallest, but $s=t=1$ gives an orthogonal pair.

$$ \left( \begin{array}{rr} 2i & j-w \\ 2i & j+w \end{array} \right) \left( \begin{array}{rr} A & B \\ B & C \end{array} \right) \left( \begin{array}{rr} 2i & 2i \\ j-w & j+w \end{array} \right) = \left( \begin{array}{cc} 4i^2 A + 4i(j-w)B + (j-w)^2C & 0 \\ 0 & 4i^2 A + 4i(j+w)B + (j+w)^2C \end{array} \right) $$ If $i=0,$ thus $jB + kC=0,$ we get

$$ \left( \begin{array}{rr} j & k \\ 0 & 1 \end{array} \right) \left( \begin{array}{rr} A & B \\ B & C \end{array} \right) \left( \begin{array}{rr} j & 0 \\ k & 1 \end{array} \right) = \left( \begin{array}{cc} j^2 A + 2jkB + k^2C & 0 \\ 0 & C \end{array} \right) $$ When $j=0,$ the combination of $\gcd(i,j,k)=1$ and $j^2 - 4 i k = w^2$ allows us to demand, in integers, $$ i = x^2, \; \; \; k = -y^2, \; \; \; w = 2 x y, $$ with $x^2 A - y^2 C = 0.$ Then $$ \left( \begin{array}{rr} x & -y \\ x & y \end{array} \right) \left( \begin{array}{rr} A & B \\ B & C \end{array} \right) \left( \begin{array}{rr} x & x \\ -y & y \end{array} \right) = \left( \begin{array}{cc} A x^2 - 2 B x y + C y^2 & 0 \\ 0 & A x^2 + 2 B x y + C y^2 \end{array} \right) $$

Anyway, these show existence for any explicit $(i,j,k)$ triple of integers such that $iA + j B + k C = 0.$ These also give upper bounds on the determinants of the change of basis matrices, again $|\alpha \delta - \beta \gamma|.$ In the case that the lattice cannot be scaled to an integral lattice, I am not confident about giving an explicit recipe for the smallest determinant that works; I suggest using these as upper bounds for a computer search.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Minimizing a determinant interestingly enough is the same as lattice reduction, at least for two by two. I believe that is the case anyway from my memories of past musings... Think in terms of orthogonalizing the two vectors (so basically swap two elements of one vector, determinant becomes dot product of the two vectors) $\endgroup$ – adam W Oct 15 '14 at 21:13
  • $\begingroup$ @adamW, I know that; the real problem is that we have unpredictable common divisors. We are free to demand $\gcd(i,j,k) = 1,$ but we do not have complete control over the common divisors of the $\alpha, \beta, \gamma, \delta$ I suggest above. $\endgroup$ – Will Jagy Oct 15 '14 at 21:16
1
$\begingroup$

A second answer. This is getting pretty good. Given a lattice with Gram matrix $$ \left( \begin{array}{rr} A & B \\ B & C \end{array} \right), $$ in order for there to be an orthogonal pair of lattice vectors, it is necessary that $A,B,C$ be linearly dependent over $\mathbb Q,$ that is, there are ordinary integers $i,j,k$ such that $$ iA + j B + k C = 0. $$ This is still not quite enough. It is also necessary that there be another ordinary integer $w,$ which is allowed to be zero or nonzero, with $$ j^2 - 4 i k = w^2. $$ This is a pretty strong restriction. However, as mentioned before, it is satisfied by $$ \left( \begin{array}{rr} 1 & 0 \\ 0 & \pi \end{array} \right), $$ in which we are given orthogonal basis vectors but we cannot scale this to an integral lattice; here we can take $i=0, j=1,k=0.$

PROOF, the $i,j,k$ thing: $$ \left( \begin{array}{rr} \alpha & \gamma \\ \beta & \delta \end{array} \right) \left( \begin{array}{rr} A & B \\ B & C \end{array} \right) \left( \begin{array}{rr} \alpha & \beta \\ \gamma & \delta \end{array} \right) = \left( \begin{array}{cc} D & 0 \\ 0 & E \end{array} \right) $$ The zero entries in the product give the equation $$ A \alpha \beta + B (\alpha \delta + \beta \gamma) + C \gamma \delta. $$ So need to have $iA + jB + kC = 0$ with some multiplier $n$ and $$n i = \alpha \beta, \; \; nj = \alpha \delta + \beta \gamma, \; \; nk = \gamma \delta. $$ If you multiply it out, $$ n^2 j^2 - 4nink = n^2(j^2 - 4ik)= (\alpha \delta - \beta \gamma)^2 $$

General comment, given just two irrational numbers, we can find out whether their ratio is rational by getting giant decimal accuracy and writing the continued fraction for the ratio. To find integers $i,j,k$ that solve $iA + jB + kC = 0,$ we use PSLQ with which I have no experience.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ For this problem, one need not look only at the Gram matrix since the orthogonal vectors need not be in the same basis, only in the same lattice. I would guess that you have such a habit of using the Gram matrix from looking at binary quadratic forms. $\endgroup$ – adam W Oct 15 '14 at 2:19
  • $\begingroup$ @adamW, I edited in an example I was thinking of before, which shows that orthogonal lattice vectors does not imply that one can scale to an integral lattice. Anyway, completely new question for me. $\endgroup$ – Will Jagy Oct 15 '14 at 2:29
  • $\begingroup$ My thought is that only $A$ and $B$ need be linearly dependent (or $B$ and $C$) in order to find orthogonal vectors. $\endgroup$ – adam W Oct 15 '14 at 2:38
  • $\begingroup$ @adamW, that would appear to be stronger than my restriction. My dinner is ready, I will type in the proof of necessity after; quite elementary. $\endgroup$ – Will Jagy Oct 15 '14 at 2:46
  • 1
    $\begingroup$ Now I see though that $i$ or $k$ zero is the same thing which you did note. $\endgroup$ – adam W Oct 15 '14 at 2:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.