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.

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: vectors_in_intervals.intervals.Intervals)

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.

See also

vectors_in_intervals.existence.exists_orthogonal_vector()

EXAMPLES:

sage: from vectors_in_intervals import *
sage: I = Intervals.from_bounds([0, 1, -1], [1, 2, -1])
sage: I
[0, 1] x [1, 2] x {-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] x (1, 2] x (-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) x (1, 2] x (-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: vectors_in_intervals.intervals.Intervals, 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.

See also

vectors_in_intervals.existence.exists_vector()

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] x [5, 6] x [-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) x (5, 6) x (-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) x [5, +oo) x (0, 8) x (-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: vectors_in_intervals.intervals.Intervals)

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: vectors_in_intervals.intervals.Intervals)

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.

See also

multiple_in_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_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: vectors_in_intervals.intervals.Intervals, 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.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.

See also

vector_from_sign_vector()

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, 1)
sage: evs = elementary_vectors(M, dual=False)
sage: vector_from_sign_vector(evs, sign_vector("+-0+"))
(1, -2, 0, 1)
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)