0
$\begingroup$

Suppose I have a set of inequalities $l \leq Ax \leq r$ for vectors $l,r$ and matrix $A$. I am trying to bound $x$ using a function of $l,r: f(l) \leq x \leq g(r)$ for some $f,g$. When can we invert this system? Alternatively, I want a change of basis from $x$ to an orthogonal basis $x'$ such that $f(l) \leq x' \leq g(r)$.

Concrete example:

I have $6$ integral variables, $m,z,p, m',z',p'$. I have a set of three inequalities:

$$m\leq m' \leq p+m$$ $$m \leq m'-z' \leq p+m$$ $$2p+2m+z \leq 2m'+p'\leq 2p+2m+z$$

Or in matrix format

$ \begin{bmatrix} m \\ m \\ 2m+2p+z \\ \end{bmatrix} \leq \begin{bmatrix} 1 & 0 & 0 \\ 1 & -1 & 0 \\ 2 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} m'\\ z'\\ p'\\ \end{bmatrix} \leq \begin{bmatrix} m+p\\ m+p\\ 2m+2p+z\\ \end{bmatrix} $

I am trying to solve this system to bound $m',z',p'$ individually in terms of $m,z,p$. Meaning, I want an expression as: $ {\bf f}(m,z,p)\leq \begin{bmatrix} m' \\ z' \\ p' \\ \end{bmatrix}\leq {\bf g}(m,z,p) $

Alternatively, I want a change of basis from $m',z',p'$ to an orthogonal basis $r,s,t$ such that $ {\bf f}(m,z,p)\leq \begin{bmatrix} r \\ s \\ t \\ \end{bmatrix}\leq {\bf g}(m,z,p) $

Improve this question
$\endgroup$
6
  • $\begingroup$ I don't think this is possible: the bounds on $m'$ will depend on $z'$ and $p'$, so you can not hope to obtain an equality of the form $f(m,z,p)\leq m'\leq g(m,z,p)$. $\endgroup$
    – Carlo Beenakker
    Commented Feb 24, 2023 at 11:52
  • $\begingroup$ @CarloBeenakker This doesn't rule out that a linear transormation would give such set right? For example, setting $r=m'+z', s=z'+p', t=..$ leading to such set. $\endgroup$
    – AspiringMat
    Commented Feb 24, 2023 at 12:22
  • $\begingroup$ but you want not just any linear transformation, but an orthogonal transformation, right? that will not work in general. $\endgroup$
    – Carlo Beenakker
    Commented Feb 24, 2023 at 13:02
  • $\begingroup$ In "When can we invert this system?", what do you mean by "when"? Do you want a necessary and sufficient condition? If so, in what terms do you want the condition on $A,l,r$ to be stated? $\endgroup$
    – Iosif Pinelis
    Commented Feb 24, 2023 at 14:32
  • $\begingroup$ Also, looking at your $f(l) \le x \le g(r)$, it seems that you want the lower bound on $x$ to depend only on $l$, and the upper bound on $x$ to depend only on $r$. On the other hand, in your "Concrete example", these "depend only on" conditions do not seem to hold. ?? $\endgroup$
    – Iosif Pinelis
    Commented Feb 24, 2023 at 14:43

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .