vectors_in_intervals.construction

Constructing vectors with components in intervals

The core function of this module is construct_vector(). Most other functions here are auxiliary function but can be used for special cases.

Functions

construct_orthogonal_vector(v, intervals)

Construct a vector, orthogonal to a given vector, with components in specified intervals.

construct_vector(M, intervals[, evs])

Construct a vector of a given vector space with components in given intervals.

multiple_in_intervals(v, intervals)

Return a multiple of a vector that lies in given intervals if possible.

multiple_in_intervals_candidates(v, intervals)

Return the largest interval where the vector, when multiplied with elements of this interval, lies in given intervals.

sign_vectors_in_intervals(intervals[, generator])

Compute all sign vectors that correspond to a vector with components in given intervals.

simplest_vector_in_intervals(intervals)

Return the simplest vector with components in given intervals.

vector_between_sign_vectors(data, lower, upper)

Find a vector in the row space of a matrix that has given signs.

vector_from_sign_vector(data, sv)

Find a vector in the row space of a matrix that has given signs.

vectors_in_intervals.construction.construct_orthogonal_vector(v, intervals: list[sage.sets.real_set.RealSet])

Construct a vector, orthogonal to a given vector, with components in specified intervals.

INPUT:

  • v – a vector of length n

  • intervals – a list of n intervals

OUTPUT:

Return a (rational) vector z such that the scalar product of z and v is zero and each component of z lies in the respective interval of the list intervals. If no such vector exists, raise a ValueError instead.

EXAMPLES:

sage: from vectors_in_intervals import *
sage: I = intervals_from_bounds([0, 1, -1], [1, 2, -1])
sage: I
[[0, 1], [1, 2], {-1}]
sage: v = vector([1, 1, 1])
sage: construct_orthogonal_vector(v, I)
(0, 1, -1)

We define another vector. This time, there is no solution:

sage: v = vector([1, 1, -1])
sage: construct_orthogonal_vector(v, I)
Traceback (most recent call last):
...
ValueError: There is no solution.

Next, we consider open intervals:

sage: I = intervals_from_bounds([0, 1, -1], [1, 2, 1], False, [True, True, False])
sage: I
[(0, 1], (1, 2], (-1, 1)]
sage: v = vector([1, 0, 1])
sage: construct_orthogonal_vector(v, I)
(1/2, 2, -1/2)

We can also work with unbounded intervals:

sage: I = intervals_from_bounds([0, 1, -oo], [oo, 2, -2], False, [True, True, False])
sage: I
[(0, +oo), (1, 2], (-oo, -2)]
sage: v = vector([-1, 1, -1])
sage: construct_orthogonal_vector(v, I)
(5, 2, -3)
vectors_in_intervals.construction.construct_vector(M, intervals: list[sage.sets.real_set.RealSet], evs=None)

Construct a vector of a given vector space with components in given intervals.

INPUT:

  • M – a matrix with m columns

  • intervals – a list of m intervals

  • evs – an optional iterable of elementary vectors

OUTPUT:

Return a vector in the row space of M such that each component lies in the respective interval of the list intervals. If no such vector exists, raises a ValueError instead.

EXAMPLES:

sage: from vectors_in_intervals import *
sage: M = matrix([[1], [1], [0]])
sage: lower_bounds = [2, 5, -1]
sage: upper_bounds = [5, 6, 1]

First, we consider closed intervals:

sage: I = intervals_from_bounds(lower_bounds, upper_bounds)
sage: I
[[2, 5], [5, 6], [-1, 1]]
sage: construct_vector(M, I)
(5)

Next, we take open intervals. This time, there is no solution:

sage: I = intervals_from_bounds(lower_bounds, upper_bounds, False, False)
sage: I
[(2, 5), (5, 6), (-1, 1)]
sage: construct_vector(M, I)
Traceback (most recent call last):
...
ValueError: There is no solution.

Finally, we consider unbounded intervals:

sage: M = matrix([[1, 0, 1, 0], [0, 1, 1, 1]])
sage: lower_bounds = [2, 5, 0, -oo]
sage: upper_bounds = [5, oo, 8, 5]
sage: lower_bounds_closed = [True, True, False, False]
sage: upper_bounds_closed = [False, False, False, True]
sage: I = intervals_from_bounds(lower_bounds, upper_bounds, lower_bounds_closed, upper_bounds_closed)
sage: I
[[2, 5), [5, +oo), (0, 8), (-oo, 5]]
sage: construct_vector(M.T, I)
(2, 5)

TESTS:

This example shows the case rank == 1:

sage: M = matrix([[0, 0, 0, 0, 0, 0], [-1, -1, 0, -1, 1, 0], [-1, 1, 0, -2, -1, -2]])
sage: I = intervals_from_bounds(
....:     [-2, -1/2, -1, -1/4, -1/6, 0],
....:     [3/4, 1, 1, 0, 12, 1],
....:     [False, True, True, True, False, True],
....:     [False, True, False, False, False, True]
....: )
sage: construct_vector(M.T, I)
(0, 1/4, 0)

Other special cases:

sage: M = zero_matrix(QQ, 3, 1)
sage: I = intervals_from_bounds([-1, -1, -1], [1, 1, 1], False, True)
sage: construct_vector(M, I)
(0)
sage: M = matrix([[0, 1], [0, 1]])
sage: I = intervals_from_bounds([0, 0], [1, 1], False, True)
sage: construct_vector(M, I)
(0, 1)
vectors_in_intervals.construction.multiple_in_intervals(v, intervals: list[sage.sets.real_set.RealSet])

Return a multiple of a vector that lies in given intervals if possible.

INPUT:

  • v – a vector

  • intervals – a list of intervals

OUTPUT: Computes a multiple a v that lies in the intervals. The number a is chosen as simple as possible. However, there might exist a simpler multiple lying in the intervals.

EXAMPLES:

sage: from vectors_in_intervals import *
sage: from vectors_in_intervals.construction import *
sage: I = intervals_from_bounds([0, 0, -1/4, -oo], [2, oo, 1/5, 1/9], False, [True, False, False, True])
sage: v = vector([1, 5, -2, 0])
sage: multiple_in_intervals(v, I)
(1/9, 5/9, -2/9, 0)
sage: multiple_in_intervals(zero_vector(4), I)
Traceback (most recent call last):
...
ValueError: There is no multiple in given intervals.
vectors_in_intervals.construction.multiple_in_intervals_candidates(v, intervals: list[sage.sets.real_set.RealSet])

Return the largest interval where the vector, when multiplied with elements of this interval, lies in given intervals.

INPUT:

  • v – a vector

  • intervals – a list of intervals

OUTPUT: Return the largest interval J such that a v lies in given intervals for all a in J.

EXAMPLES:

sage: from vectors_in_intervals import *
sage: from vectors_in_intervals.construction import *
sage: I = intervals_from_bounds([0, 0, -1/4, -oo], [2, oo, 1/5, 1/9], False, [True, False, False, True])
sage: v = vector([1, 5, -2, 0])
sage: multiple_in_intervals_candidates(v, I)
(0, 1/8)
sage: v = vector([0, 5, -2, 0])
sage: multiple_in_intervals_candidates(v, I)
{}
sage: I = intervals_from_bounds([-2, -1/4, -7], [0, 1, 0], [True, False, False], [False, False, True])
sage: v = vector([-2, -2, -1])
sage: multiple_in_intervals_candidates(v, I)
(0, 1/8)
sage: v = vector([0, -2, 1])
sage: I = intervals_from_bounds([-2, 0, -1], [1, 1/3, 0], True, False)
sage: multiple_in_intervals_candidates(v, I)
(-1/6, 0)
vectors_in_intervals.construction.sign_vectors_in_intervals(intervals: list[sage.sets.real_set.RealSet], generator: bool = False)

Compute all sign vectors that correspond to a vector with components in given intervals.

INPUT:

  • intervals – a list of intervals

  • generator – a boolean (default: False)

EXAMPLES:

sage: from vectors_in_intervals import *
sage: intervals = intervals_from_bounds([-1, 1], [0, 1])
sage: sign_vectors_in_intervals(intervals)
[(0+), (-+)]
sage: intervals = intervals_from_bounds([-1, -2], [0, 1])
sage: sign_vectors_in_intervals(intervals)
[(00), (0+), (0-), (-0), (-+), (--)]
sage: intervals = intervals_from_bounds([-1, -1, 0], [0, 5, 0])
sage: sign_vectors_in_intervals(intervals)
[(000), (0+0), (0-0), (-00), (-+0), (--0)]
sage: intervals = intervals_from_bounds([-1, -1, -1], [0, 1, 0], False, False)
sage: sign_vectors_in_intervals(intervals)
[(-0-), (-+-), (---)]
sage: intervals = intervals_from_bounds([-1, 0], [1, 0], False, False)
sage: sign_vectors_in_intervals(intervals)
[]
sage: intervals = intervals_from_bounds([], [])
sage: sign_vectors_in_intervals(intervals)
[]
vectors_in_intervals.construction.simplest_vector_in_intervals(intervals: list[sage.sets.real_set.RealSet])

Return the simplest vector with components in given intervals.

INPUT:

  • intervals – a list of intervals

OUTPUT: A vector with components in the intervals. If possible, each component is the integer with smallest possible absolute value in the corresponding interval. Otherwise, components are rational with smallest possible denominator.

EXAMPLES:

sage: from vectors_in_intervals import *
sage: from vectors_in_intervals.construction import *
sage: lower_bounds = [2, 5, -1]
sage: upper_bounds = [5, 6, 1]
sage: I = intervals_from_bounds(lower_bounds, upper_bounds)
sage: I
[[2, 5], [5, 6], [-1, 1]]
sage: simplest_vector_in_intervals(I)
(2, 5, 0)
sage: I = intervals_from_bounds(lower_bounds, upper_bounds, False, False)
sage: I
[(2, 5), (5, 6), (-1, 1)]
sage: simplest_vector_in_intervals(I)
(3, 11/2, 0)
vectors_in_intervals.construction.vector_between_sign_vectors(data, lower, upper)

Find a vector in the row space of a matrix that has given signs.

The resulting vector v satisfies lower <= sign(v) <= upper.

TESTS:

sage: from vectors_in_intervals import *
sage: from sign_vectors import *
sage: M = matrix([[-3, -8, 0, 0, 1, -1], [10, -1, 2, 1, -7, 0], [1, 0, 0, -1, -3, 3]])
sage: lower = sign_vector('000+00')
sage: lower
(000+00)
sage: upper = sign_vector('++0+0+')
sage: upper
(++0+0+)

We demonstrate that we cannot just use evs with indices in supp X:

sage: M = matrix([[1, 1, 1, 0, 0], [0, 0, 0, 1, 1]])
sage: X = sign_vector("+++00")
sage: vector_between_sign_vectors(M, X, X)
(1, 1, 1, 0, 0)
vectors_in_intervals.construction.vector_from_sign_vector(data, sv)

Find a vector in the row space of a matrix that has given signs.

INPUT:

  • data – either a real matrix with n columns or a list of

    elementary vectors of length n

  • sv – a sign vector of length n

OUTPUT: Return a conformal sum of elementary vectors that lies in the given subspace.

If data is a matrix, the elementary vectors in the kernel of this matrix are used for the result. If data is a list of elementary vectors, those are used.

Note

A ValueError is raised if no solution exists.

EXAMPLES:

sage: from vectors_in_intervals import *
sage: from elementary_vectors import *
sage: from sign_vectors import *
sage: M = matrix([[1, 0, 2, 0], [0, 1, 1, 0], [0, 0, 0, 1]])
sage: vector_from_sign_vector(M, zero_sign_vector(4))
(0, 0, 0, 0)
sage: vector_from_sign_vector(M, sign_vector("+-+0"))
(2, -2, 2, 0)
sage: vector_from_sign_vector(M, sign_vector("+0+0"))
(1, 0, 2, 0)
sage: vector_from_sign_vector(M, sign_vector("+-0+"))
(1, -2, 0, 2)
sage: vector_from_sign_vector(M, sign_vector("+-0+"))
(1, -2, 0, 2)
sage: evs = elementary_vectors(M, kernel=False)
sage: vector_from_sign_vector(evs, sign_vector("+-0+"))
(1, -2, 0, 2)
sage: vector_from_sign_vector(M, sign_vector("+0-0"))
Traceback (most recent call last):
...
ValueError: Cannot find vector corresponding to given sign vector.
sage: vector_from_sign_vector([], zero_sign_vector(4))
(0, 0, 0, 0)