非规范化单位向量

Question

假设我有单位向量,你.

from numpy import mat
u = mat([[0.9**0.5], [-(0.1)**0.5]])
# [ 0.9486833  -0.31622777]

单位向量是具有整数条目的矩阵的特征向量.我也知道特征值是整数.因此,单位向量将包含无理小数,当平方时,它们是有理数的十进制近似值.

有没有什么好方法可以找到最小值k,使得k u的所有条目都是整数？通常,k将是整数的平方根.

一种天真的方法是对矢量中的每个条目求平方,并找到产生整数的最小k _i.然后,k将是所有k _i的LCM的平方根.我希望有比这更好的方法.

---

请注意,这不是此问题的副本.

Answer 1

我改进了 Christian 提供的方法，以便接受更广泛的分数。诀窍是通过将单位向量除以最小的非零条目来“预归一化”单位向量。这对于指定最大分母的所有分数都可靠。

from fractions import Fraction, gcd

def recover_integer_vector(u, denom=50):
    '''
    For a given vector u, return the smallest vector with all integer entries.
    '''

    # make smallest non-zero entry 1
    u /= min(abs(x) for x in u if x)

    # get the denominators of the fractions
    denoms = (Fraction(x).limit_denominator(denom).denominator for x in u)

    # multiply the scaled u by LCM(denominators)
    lcm = lambda a, b: a * b / gcd(a, b)
    return u * reduce(lcm, denoms)

测试：

以下代码用于确保给定范围内的所有分数都能正确工作。

import numpy as np

from numpy import array
from itertools import combinations_with_replacement


for t in combinations_with_replacement(range(1, 50), 3):
    if reduce(gcd, t) != 1: continue

    v = array(map(float, t))
    u = v / np.linalg.norm(v)

    w = recover_integer_vector(u)

    assert np.allclose(w, v) or np.allclose(w, -v)

从测试时间可以看出，这段代码速度不是很快。我的电脑测试花了大约6秒。我不确定时间是否可以改进。