Given the normal vector to an m-plane in R

^{n}(n > m), is there any efficient method to find lattice points (ie: points with integer coordinates) on that plane?

**Moderators:** gmalivuk, Moderators General, Prelates

Hi everybody!

Given the normal vector to an m-plane in R^{n} (n > m), is there any efficient method to find lattice points (ie: points with integer coordinates) on that plane?

Given the normal vector to an m-plane in R

"Ich bin ein Teil von jener Kraft, die stets das Böse will und stets das Gute schafft."

Is this homework? Regardless, I'll throw out what I've thought up really quickly.

So you have a normal vector, n. From this you can define a plane by finding vectors orthogonal to n (and to each other). These m vectors form a basis. Call them b_1, b_2, ..., b_m.

So, any point on the plane can be written as a combination of the basis vectors. Thus, the point (1,0,0,...,0) on the plane can be written as 1/||b_1||*b_1+0*b_2+...+0*b_m. You can proceed with this process for each basis vector, and then it seems as though you can generate integer coordinates from this operation.

Edit: I'm not sure if you want to find points on the plane that correspond to integer coordinates in R^n, or find coordinates in R^n that correspond to integer points on the plane. Either way, it seems like essentially the same process, but I've only given it about 90 seconds worth of thought, so I might be missing something critical.

So you have a normal vector, n. From this you can define a plane by finding vectors orthogonal to n (and to each other). These m vectors form a basis. Call them b_1, b_2, ..., b_m.

So, any point on the plane can be written as a combination of the basis vectors. Thus, the point (1,0,0,...,0) on the plane can be written as 1/||b_1||*b_1+0*b_2+...+0*b_m. You can proceed with this process for each basis vector, and then it seems as though you can generate integer coordinates from this operation.

Edit: I'm not sure if you want to find points on the plane that correspond to integer coordinates in R^n, or find coordinates in R^n that correspond to integer points on the plane. Either way, it seems like essentially the same process, but I've only given it about 90 seconds worth of thought, so I might be missing something critical.

- jestingrabbit
- Factoids are just Datas that haven't grown up yet
**Posts:**5963**Joined:**Tue Nov 28, 2006 9:50 pm UTC**Location:**Sydney

Giallo wrote:Hi everybody!

Given the normal vector to an m-plane in R^{n}(n > m), is there any efficient method to find lattice points (ie: points with integer coordinates) on that plane?

Unless n = m+1, you're going to want more than one normal vector. If you look at { v | v.w = 0} you have an n-1 dimensional vector space. You need n-m linearly independent normal vectors to specify a single subspace.

ameretrifle wrote:Magic space feudalism is therefore a viable idea.

- Proginoskes
**Posts:**313**Joined:**Mon Nov 14, 2011 7:07 am UTC**Location:**Sitting Down

Giallo wrote:Hi everybody!

Given the normal vector to an m-plane in R^{n}(n > m), is there any efficient method to find lattice points (ie: points with integer coordinates) on that plane?

Yes. Google for "linear diophantine equations in three variables". Dr. Math has a good explanation.

It's not homework; @jestingrabbit: you're right, stupid me

Anyway this comes out from the following problem (*): given the equation

[math]\prod_{k = 1}^n a_k^{x_k} = 1[/math]

with a_{k}'s algebraic find a solution where x_{k}'s are in Z.

Taking the logarithm we find the equation:

[math]\sum_{k = 1}^n x_k\log(a_k) = 0[/math]

which corresponds to find the lattice points of the (n-1) dimensional plane with normal vector (a_{1}, ... , a_{n}) in R^{n}.

Only a friend of mine told me that (*) should have an optimal solution which is something like O(2^{n}), and I wanted to check

Anyway this comes out from the following problem (*): given the equation

[math]\prod_{k = 1}^n a_k^{x_k} = 1[/math]

with a

Taking the logarithm we find the equation:

[math]\sum_{k = 1}^n x_k\log(a_k) = 0[/math]

which corresponds to find the lattice points of the (n-1) dimensional plane with normal vector (a

Only a friend of mine told me that (*) should have an optimal solution which is something like O(2

"Ich bin ein Teil von jener Kraft, die stets das Böse will und stets das Gute schafft."

Users browsing this forum: No registered users and 15 guests