Orthogonal Vectors in a 2D Lattice with minimum area

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.