4
$\begingroup$

I have a list manipulation problem as follows.

Suppose I have a list $L=\{1,2,3\}$.

All nonempty subsets of $L$ is $SL=\{\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}$.

Now I want to construct an incidence matrix of $SL$ as follows

{{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}} (*This is SL.*)
mat=
{{1,  0,  0,  0,0,  0,0,  0,0,  0,0,0},
 {0,  1,  0,  0,0,  0,0,  0,0,  0,0,0},
 {0,  0,  1,  0,0,  0,0,  0,0,  0,0,0},
 {0,  0,  0,  1,1,  0,0,  0,0,  0,0,0}, (*This is the matrix.*)
 {0,  0,  0,  0,0,  1,1,  0,0,  0,0,0},
 {0,  0,  0,  0,0,  0,0,  1,1,  0,0,0},
 {0,  0,  0,  0,0,  0,0,  0,0,  1,1,1}}

All suggestions are welcome!

$\endgroup$
4
$\begingroup$
sL = Rest[Subsets@Range@3]
 {{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}

You can also use SparseArray + Band:

ClearAll[f]
f = SparseArray[Band[{1, 1}] -> List /@ Unitize@#] &;


f @ sL // MatrixForm // TeXForm

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

Alternatively, a combination of MapThread + RotateRight + PadLeft + Accumulate:

ClearAll[g]
g = Module[{cl = Accumulate[Length /@ #]}, 
  MapThread[RotateRight, {PadLeft[Unitize @ #, {Automatic, Last @ cl}], cl}]] &

g @ sL // MatrixForm // TeXForm

same result

If you wish to use an integer as input, you can modify f as follows:

ClearAll[f2]
f2 = SparseArray[Band[{1, 1}] -> List /@ Unitize @ Rest @ Subsets @ Range @ #] &;

f2 @ 3 // MatrixForm // TeXForm

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

You can modify g similarly.

$\endgroup$
5
$\begingroup$

It isn't quite clear to me what is wanted, but the matrix in the OP can be generated readily, with a little help from an undocumented function:

With[{n = 3}, 
     SparseArray`SparseBlockMatrix[MapIndexed[Join[#2, #2] -> {#1} &,
                                              Unitize[Subsets[Range[n],
                                                              {1, ∞}]]]]] // MatrixForm

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

$\endgroup$
1
  • $\begingroup$ Thank you very much for your answer! But the other answer provides several different ways of generating the desired matrix. $\endgroup$ – hxiao Aug 14 '20 at 3:18
2
$\begingroup$
Clear["Global`*"]

n = 3;

L = Range[n];

SL = Subsets[L, {1, n}]

(* {{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}} *)

Freestanding commas do not make much sense. Perhaps you mean:

(mat = Module[{len = Length@SL},
    Array[ConstantArray[KroneckerDelta@##, Length[SL[[#2]]]] &, {len, 
      len}]]) // MatrixForm

enter image description here

$\endgroup$
3
  • 1
    $\begingroup$ You could do Flatten /@ mat in that case I suppose. $\endgroup$ – flinty Aug 13 '20 at 15:26
  • 1
    $\begingroup$ @flinty - the spacing used in the desired output caused me to interpret the intent as desiring a 7x7 matrix with the elements given by the clusters formed by the spacing. Others interpreted the intent as a 7x12 matrix with the spacing having no significance. Presumably, I guessed wrong. $\endgroup$ – Bob Hanlon Aug 13 '20 at 17:13
  • $\begingroup$ I'm afraid that @flinty is right. It was my expression that misled you. Thank you very much for you answer. $\endgroup$ – hxiao Aug 14 '20 at 3:22

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.