# List manipulation with special requirements

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?

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}$$

• 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! Aug 14, 2020 at 7:04

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]


im = Transpose @ IncidenceMatrix @ rg


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)$$

• It is great to know the RelationGraph' function. Aug 16, 2020 at 3:52