3
$\begingroup$

I am new to matrices and to systems of inequalities. When I look at a matrix it's difficult to tell where the $1's$, $0's$ and $-1's$ come from. I know they somehow come from the inequality itself, but for some reason I'm not seeing how.

My questions are:

  1. How these inequalities become (get plugged into) these matrices (source): $$ 1 \leq i \leq n : \begin{bmatrix} 1 & 0\\ -1 & 0 \end{bmatrix} \begin{pmatrix} i\\ j \end{pmatrix} + \begin{pmatrix} -1\\ n \end{pmatrix} \geq 0 $$ $$ 1 \leq j \leq n : \begin{bmatrix} 0 & 1\\ 0 & -1 \end{bmatrix} \begin{pmatrix} i\\ j \end{pmatrix} + \begin{pmatrix} -1\\ n \end{pmatrix} \geq 0 $$
  2. Specifically, how $1 \leq i \leq n$ becomes \begin{bmatrix}1 & 0\\-1 & 0\end{bmatrix}
  3. And how $1 \leq i \leq n$ becomes \begin{pmatrix}-1\\n\end{pmatrix}

Now I'll describe the problem I'm having in more detail if that's helpful.

(I assume this equation is from $\textbf{A}\vec{x} + \vec{b} \geq 0$).

Take for example these two parts:

$$ (a):1 \leq i \leq n\ \ \ \ (b):\begin{bmatrix} 1 & 0\\ -1 & 0 \end{bmatrix} $$

I know (a) can be rewritten into a set of two inequalities (though I'm not even sure I'm doing that right):

\begin{align} 0 &\leq -1 + i\\ 0 &\leq -i + n \end{align}

So then in my attempt to figure out how the inequality goes into the matrix, I do this:

\begin{align} 0 &\leq -1 + i \mapsto -1, 1\\ 0 &\leq -i + n \mapsto -1, 1 \end{align}

since $\mathbf{-1} + i$ is like $(\mathbf{-1} + (\mathbf{1} \times i))$ and $\mathbf{-}i + n$ is like $((\mathbf{-1} \times i) + (\mathbf{1} \times n))$. But that would lead to a matrix like this:

$$ \begin{bmatrix} -1 & 1\\ -1 & 1 \end{bmatrix} $$

when it should be

$$ \begin{bmatrix} 1 & 0\\ -1 & 0 \end{bmatrix} $$

So I'm confused how that matrix (b) gets created from the inequality (a). The same goes for the second matrix in the first diagram.

Also, I am not sure where this comes from either:

$$ \begin{pmatrix} -1\\ n \end{pmatrix} $$

The full set of inequalities/matrices (if it's helpful) is below. I'm basically just trying to understand how they got those matrix equations from the inequalities in the diagram:

enter image description here

enter image description here

They got the inequalities out of the for loop if that helps.

Another example is the following diagram. Even though they have the colors showing how they mapped the values, I still don't see how they did it (went from inequality $\to$ matrix).

enter image description here

I would simply like to know how to do it for one of these inequality/matrices pairs, so I can apply it to all of them. Thank you so much for the help.

$\endgroup$

1 Answer 1

1
$\begingroup$

Indeed it is basically breaking $1\leq i\leq n$ into two parts $1\leq i$ and $i\leq n$.

You then make both of them as nonnegativity conditions $i-1\geq 0$ and $-i+n\geq0$ so they are now

$$ \begin{bmatrix}1\\-1\end{bmatrix}i + \begin{bmatrix}-1\\n\end{bmatrix} \geq 0 $$ Since nothing depends on $j$ for these inequalities we can add the dummy constraint $0j\geq 0$ and everything stays the same

$$ \begin{bmatrix}1&0\\-1&0\end{bmatrix}\begin{bmatrix}i\\j\end{bmatrix} + \begin{bmatrix}-1\\n\end{bmatrix} \geq 0 $$

You can do the same for $j$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .