List manipulation with special requirements

Question

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?

Answer 1

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

Answer 2

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