python - 反规范化单位向量

Question

假设我有单位向量 u。

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

单位向量是具有整数项的矩阵的特征向量。我也知道特征值是整数。因此，单位向量将包含无理小数，当平方时，它们是有理数的小数近似值。

有什么好的方法可以找到最小值 k 使得 ku 的所有条目都是整数？一般来说，k 将是整数的平方根。

一种天真的方法是对向量​​中的每个条目进行平方，然后找到生成整数的最小 k_i。然后，k 将是所有 k_i 的 LCM 的平方根。我希望有比这更好的方法。

---

请注意，这不是 this question 的副本.

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 秒来测试。我不确定时间是否可以改进。