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?

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

$\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$ – hxiao Aug 14 '20 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)$

$\endgroup$
1
  • $\begingroup$ It is great to know the RelationGraph' function. $\endgroup$ – hxiao Aug 16 '20 at 3:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.