1
$\begingroup$

Let $N$ be the ground set. I want to express the coefficients of following linear inequalities with a matrix (actually a list):

$$a_{S,i}-a_{T,i}\geq 0 \text{ for any }S\subseteq T\subseteq N \text{ and any } i\in S.$$

For example, suppose $N=\{1,2,3\}$. I want to construct the coefficient matrix, where all variables are ordered in $$a_{\{1\},1},a_{\{2\},2},a_{\{3\},3},a_{\{1,2\},1},a_{\{1,2\},2},a_{\{1,3\},1},a_{\{1,3\},3},a_{\{2,3\},2},a_{\{2,3\},3},a_{\{1,2,3\},1},a_{\{1,2,3\},2},a_{\{1,2,3\},3}.$$ For simplicity, we only consider linear inequalities involving element $1\in N$ here: $$ a_{\{1\},1}-a_{\{1,2\},1}\geq 0, $$ $$ a_{\{1\},1}-a_{\{1,3\},1}\geq 0, $$ $$ a_{\{1\},1}-a_{\{1,2,3\},1}\geq 0, $$ $$ a_{\{1,2\},1}-a_{\{1,2,3\},1}\geq 0, $$ $$ a_{\{1,3\},1}-a_{\{1,2,3\},1}\geq 0. $$ The corresponding coefficient matrix (list) is as follows

{{1,0,0,-1,0,0,0,0,0,0,0,0}, {1,0,0,0,0,-1,0,0,0,0,0,0}, {1,0,0,0,0,0,0,0,0,-1,0,0}, {0,0,0,1,0,0,0,0,0,-1,0,0}, {0,0,0,0,0,1,0,0,0,-1,0,0}}

To increase the readability of requirements, we may consider the following list before Flatten operation

{{{1},{0},{0},{-1,0},{0,0},{0,0},{0,0,0}}, {{1},{0},{0},{0,0},{-1,0},{0,0},{0,0,0}}, {{1},{0},{0},{0,0},{0,0},{0,0},{-1,0,0}}, {{0},{0},{0},{1,0},{0,0},{0,0},{-1,0,0}}, {{0},{0},{0},{0,0},{1,0},{0,0},{-1,0,0}}}

My question is how to construct the coefficient matrix for a given ground set $N$. Any suggestions?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

Not too hard:

n = 3; id = Select[Tuples[{Subsets[Range[n], {1, ∞}], Range[n]}], Apply[MemberQ]]; pr = Select[Subsets[Select[id, #[[2]] == 1 &], {2}], SubsetQ @@ Reverse[#[[All, 1]]] &]; SparseArray[Flatten[MapIndexed[Thread[PadLeft[#1, {2, 2}, #2] -> {1, -1}] &, Map[Position[id, #][[1]] &, pr, {2}]]], {Length[pr], Length[id]}] // MatrixForm

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ I'm quite new to Mathematica. Hence it may take a while for me to understand all steps. Thank you very much for your solutions for this question and for my last question! $\endgroup$ Commented Aug 14, 2020 at 7:04
1
$\begingroup$

You can also use RelationGraph and IncidenceMatrix as follows:

n = 3; vlist = Join @@ (Thread[{#, #}, List, {2}] & /@ Rest[Subsets @ Range @ n]); relation = #2[[2]] == #[[2]] == 1 && UnsameQ @ ## && SubsetQ[#[[1]], #2[[1]]] &; rg = RelationGraph[relation, vlist, VertexLabels -> "Name", ImageSize -> Large]

enter image description here

im = Transpose @ IncidenceMatrix @ rg

enter image description here

im // MatrixForm // TeXForm

$\left( \begin{array}{cccccccccccc} 1 & 0 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & -1 & 0 & 0 \\ \end{array} \right)$

Improve this answer
$\endgroup$
1
  • $\begingroup$ It is great to know the RelationGraph' function. $\endgroup$ Commented Aug 16, 2020 at 3:52

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.